- Compilation/
Control logic decompositions
Control logic decompositions
The quantum singular value transform (QSVT) is a widely used routine in quantum algorithms. For an introduction to the QSVT and to see the QSVT in practice, please refer to our dedicated demos. Here, we show a small trick that applies to a linear combination of QSVT circuits that is implemented directly in a quantum circuit. Such a linear combination, in particular the one involving exactly two QSVTs, is frequently needed if the desired singular value transform has both odd-degree and even-degree polynomial contributions. This arises because a single QSVT can only ever apply a polynomial transformation of a definite parity. We will not go into detail about QSVT nor about linear combinations of unitaries (LCUs) in general, but simply note their respective structure and then demonstrate the simplification.
For a simple example, the simplification discussed here is captured by the following circuit diagram:
aux: ──H─╭○─────╭○────────────╭○─────╭○─────────────╭○──────╭●─────╭●────────────╭●─────H─┤↗₀│ c: ────╰∏_ϕ_0─├BlockEncode0─╰∏_ϕ_1─├BlockEncode0†─╰∏_ϕ_2──╰∏_τ_0─├BlockEncode0─╰∏_τ_1─────────┤ t: ───────────╰BlockEncode0────────╰BlockEncode0†────────────────╰BlockEncode0────────────────┤. = aux: ──H─────╭●─────────────────────────╭●─────╭○─────────────╭○─────H─┤↗₀│ c: ──∏_ϕ_0─╰∏_θ_0─╭BlockEncode0─∏_ϕ_1─╰∏_θ_1─├BlockEncode0†─╰∏_ϕ_2────────┤ t: ───────────────╰BlockEncode0──────────────╰BlockEncode0†───────────────┤.
Linear combination of unitaries
A simple technique to implement the sum of two unitary operators U_0 and U_1 in a quantum circuit is to initialize an auxiliary qubit in the |+\rangle state, apply U_k controlled on the |k\rangle state of that qubit, followed by a Hadamard gate on the auxiliary qubit, and measure the auxiliary qubit. This procedure is similar to a Hadamard test but we additionally need to postselect on the measurement outcome of the auxiliary qubit. By postselecting on the measurement outcome 0, we can ensure that \tfrac{1}{\sqrt{2}}(U_0 + U_1) is effectively applied to the original target qubits. In a circuit, this is represented as:
0: ──H─╭○──╭●──H─┤↗₀│ 1: ────├U0─├U1────────┤ 2: ────├U0─├U1────────┤ 3: ────╰U0─╰U1────────┤.
Note that measuring a 1 implies that the procedure failed, and the operation has to be restarted. Despite this failure possibility, LCUs are commonly used in quantum algorithms, as long as the failure probability can be kept low enough.
Similarly, a linear combination c_0 U_0 + c_1 U_1 for |c_0|^2+|c_1|^2=1 can be implemented
by replacing the Hadamard gates with a partial qml.RY
rotation, and/or applying a phase gate or
qml.RZ
rotation somewhere between those RY
rotations; its position is inconsequential
because the RZ
commutes with the control nodes.
More generally, a linear combination of K unitaries, given as \sum_{k=1}^K c_k U_k with
c\in\mathbb{R}^K, \|c\|_2=1, can be implemented by preparing the state c on the first K
basis states on \lceil \log_2 K\rceil control qubits, Select
-applying the operators \{U_k\}
over these basis states, and unpreparing the state again. Additional relative phases can be added
by applying phase gates between preparation and unpreparation. See our
demo on LCU for block encodings
and the seminal paper on Hamiltonian simulation via LCUs
by Childs and Wiebe.
Quantum singular-value transformation
We will defer to the literature (e.g. Gilyén et al., Martyn et al.) and our demos (such as intro to QSVT or QSVT in practice) for an introduction to QSVT. For our current purposes, we just need to know that this subroutine usually takes the following form:
c: ──∏_ϕ_0─╭BlockEncode0──∏_ϕ_1─╭BlockEncode0†──∏_ϕ_2─╭BlockEncode0──∏_ϕ_3─┤ t: ────────╰BlockEncode0────────╰BlockEncode0†────────╰BlockEncode0────────┤.
Here, c
denotes some control qubits and t
denotes target qubits.
BlockEncode is some
block encoding subroutine, such as
PrepSelPrep and the
∏_ϕ_i
are PCPhase
operators that apply relative phase shifts ϕ_i
between the block encoded subspace and the
remaining subspace.
More generally, the QSVT of a matrix A with angles \vec{\phi} can be written as
if the implemented singular value transform has even degree d. Here U(A) denotes the block encoding of A and \Pi_{\phi_i} are the projector-controlled phase shifts. Note that the matrix product is in reverse order compared to the circuit drawing. For odd degree d, the operator instead reads
In both cases, the number of needed phase shifts is d+1 for a degree-d polynomial. Accordingly, the block encoding U(A) or its adjoint is applied d times.
Simplifying an LCU(QSVT)
As mentioned in the beginning, an important case is the LCU of two QSVT circuits that
implement an odd and even polynomial, respectively, but use the same block encoding of an
operator of interest. In this scenario, the degree of the two polynomials usually differs by
one, because a mixed-parity polynomial (like \exp) is desired and the even and odd parts
of this polynomial (\cos and \sin) are truncated with the same threshold D to obtain a
certain approximation error. Accordingly, the number of PCPhase
and BlockEncode
operators
in the two QSVTs differs by just one.
As an example, consider the case D=4, so that the even (odd) part is truncated to degree d_{\text{even}}=4 with phases \{\phi_i\}_{i=0}^3 (d_{\text{odd}}=3 with phases \{\tau_i\}_{i=0}^2). The overall circuit to compute a simple LCU of the resulting QSVT circuits then consists of the following two parts:
aux: ──H─╭○─────╭○────────────╭○─────╭○─────────────╭○─────╭○────────────╭○──────... c: ────╰∏_ϕ_0─├BlockEncode0─╰∏_ϕ_1─├BlockEncode0†─╰∏_ϕ_2─├BlockEncode0─╰∏_ϕ_3──... t: ───────────╰BlockEncode0────────╰BlockEncode0†────────╰BlockEncode0─────────... ... ──╭●─────╭●────────────╭●─────╭●─────────────╭●─────H─┤↗₀│ ... ──╰∏_τ_0─├BlockEncode0─╰∏_τ_1─├BlockEncode0†─╰∏_τ_2─────────┤ ... ─────────╰BlockEncode0────────╰BlockEncode0†────────────────┤.
Now, to simplify this circuit, we may use the fact that operators controlled on disjoint control
states commute with each other. Rearranging the components allows us to pair up block encodings
and PCPhase
operators for the even and odd degree QSVTs, controlled on the |0\rangle and
|1\rangle state of the auxiliary qubit, respectively.
Then, we can use the "lazy Select" rule (also see p.9 in Shende et al.) for operators controlled on complementary control states:
aux: ─╭○──╭●──┤ = aux: ────╭●─────┤ b: ─╰A──╰B──┤ b: ──A─╰(BA†)─┤.
For the PCPhase
operators, this means that we can skip the first control node if we change the
phase of the second operator to the difference of the second and first phase.
For the block encodings, the lazy Select rule simplifies further because the same operator is applied for both control states:
aux: ─╭○──╭●──┤ = aux: ─────╭●─────┤ = aux: ───┤ b: ─╰U──╰U──┤ b: ──U──╰(UU†)─┤ b: ─U─┤.
This allows us to merge the pairs of BlockEncode
operators into a single, non-controlled
BlockEncode
.
Applying the reordering and the two simplifications to the pairs of block encodings and PCPhase
operators, we arrive at the reduced LCU(QSVT) circuit
aux: ──H─────╭●─────────────────────────╭●──────────────────────────╭●─────╭○────────────╭○─────H─┤↗₀│ c: ──∏_ϕ_0─╰∏_θ_0─╭BlockEncode0─∏_ϕ_1─╰∏_θ_1─╭BlockEncode0†─∏_ϕ_2─╰∏_θ_2─├BlockEncode0─╰∏_ϕ_3────────┤ t: ───────────────╰BlockEncode0──────────────╰BlockEncode0†──────────────╰BlockEncode0───────────────┤,
where \theta_i = \tau_i-\phi_i. More generally, the first
2\min(d_{\text{even}}, d_{\text{odd}})+1 components of both controlled QSVT blocks can be merged
pairwise, either into a single block encoding, or into two PCPhase
operators of which only one
is controlled.
Note that an alternative optimization to an LCU of QSVTs would be the controlled compute/uncompute simplification. While it allows to skip control nodes of the block encoding routines, it does not allow us to merge them together for the two QSVT subroutines as we did here.