Control logic decompositions

A common pattern in quantum algorithms is characterized by a pair of unitary operators, $U$ and $V$, which are applied in the form of the matrix product $U^\dagger V U$. This describes the circuit

|ψ>: ─U─V─U†─┤

Here, we show a small simplification that exploits a generic algorithm structure to reduce the number of control nodes. The essence is captured in the circuit equality:

|c>: ─╭●──────┤  =  |c>: ─╭●──╭●──╭●──┤  =  |c>: ────╭●─────┤
|ψ>: ─╰(U†VU)─┤     |ψ>: ─╰U──╰V──╰U†─┤     |ψ>: ──U─╰V──U†─┤.

Common examples of this include the block encoding technique PrepSelPrep, which is of the form

0: ─╭PrepSelPrep─┤  =  0: ──|Ψ⟩─╭Select──|Ψ⟩†─┤
1: ─╰PrepSelPrep─┤     1: ──────╰Select───────┤,

with the state preparation playing the role of $U$ and the Select operator playing that of the central operator $V$. Similarly, QSVT circuits contain slices with the structure

0: ─╭QSVT─┤  ⊃  0: ──╭PrepSelPrep──────╭PrepSelPrep†─┤
1: ─╰QSVT─┤     1: ──╰PrepSelPrep──∏_ϕ─╰PrepSelPrep†─┤,

where PrepSelPrep as a whole now acts as $U$, and the projector-controlled phase operator $\Pi_\phi$ (also see qml.PCPhase) acts as $V$. However, there are also small circuit identities taking the form of a compute/uncompute pattern, like

0: ─╭SWAP─┤  =  0: ─╭●─╭X─╭●─┤
1: ─╰SWAP─┤     1: ─╰X─╰●─╰X─┤.

Controlled application of compute/uncompute

If we perform a controlled version of a compute/uncompute pattern, we could naively attach the control nodes to each operator in the pattern. For example, for a single control node with control value $1$, we could write

|c>: ─╭●──────┤  =  |c>: ─╭●──╭●──╭●──┤
|ψ>: ─╰(U†VU)─┤     |ψ>: ─╰U──╰V──╰U†─┤.

However, we may simply drop the control nodes on $U$ and $U^\dagger$ without changing the circuit:

|c>: ─╭●──────┤  =  |c>: ────╭●─────┤
|ψ>: ─╰(U†VU)─┤     |ψ>: ──U─╰V──U†─┤.

We can check that this is equivalent by considering the two possible basis states of the control qubit: in the state $|0\rangle$, the original circuit does not apply any operator. The new circuit applies $U^\dagger U=\mathbb{I}$. In the state $|1\rangle$, the original circuit applies the compute/uncompute pattern $U^\dagger V U$. The new circuit does exactly that.

Note that we can replace the single control qubit by any other control structure. The analysis will remain the same, with $|0\rangle$ ($|1\rangle$) replaced by the sets of states for which the control condition is False (True). For example, a three-qubit control structure on the state $|101\rangle$ may be applied only to the middle operator $V$:

|c0>: ─╭●──────┤     |c0>: ────╭●─────┤
|c1>: ─├○──────┤  =  |c1>: ────├○─────┤
|c2>: ─├●──────┤     |c2>: ────├●─────┤
|ψ>:  ─╰(U†VU)─┤     |ψ>:  ──U─╰V──U†─┤.

Relation to basic control logic properties

To derive this equivalence from basic properties of control logic, we write

|c>: ─╭●──────┤
|ψ>: ─╰(U†VU)─┤
= (expand controls)
|c>: ─╭●──╭●──╭●──┤
|ψ>: ─╰U──╰V──╰U†─┤
= (insert identity)
|c>: ─╭●──╭●──╭●──╭○──╭○──┤
|ψ>: ─╰U──╰V──╰U†─╰U──╰U†─┤
= (commute ctrl(U, 0) with ctrl(U†, 1) and ctrl(V, 1))
|c>: ─╭●──╭○──╭●──╭●──╭○──┤
|ψ>: ─╰U──╰U──╰V──╰U†─╰U†─┤
= (merge complementary controls)
|c>: ────╭●─────┤
|ψ>: ──U─╰V──U†─┤.

Here, we appended an identity at the end of the circuit, used the fact that operators controlled on disjoint states of the control qubits commute, and applied the "lazy Select" rule for a single control,

0: ─╭○──╭●──┤  =  0: ───┤
1: ─╰U──╰U──┤     1: ─U─┤.

For other control structures, the added identity $U^\dagger U$ is simply controlled by the complementary control structure. For example, for the three added controls in the previous example, $U^\dagger U$ would be controlled on all states except for $|101\rangle$.

Concrete example

Consider the following simple quantum program.

def compute_uncompute():
    qml.RX(0.5, 0)
    qml.CNOT([0, 1])
    qml.CNOT([1, 2])
    qml.CNOT([0, 1])
    qml.adjoint(qml.RX)(0.5, 0)

>>> print(qml.draw(compute_uncompute)())
0: ──RX(0.50)─╭●────╭●──RX(0.50)†─┤
1: ───────────╰X─╭●─╰X────────────┤
2: ──────────────╰X───────────────┤

If we want to apply a controlled version qml.ctrl(compute_uncompute, control=["ctrl"]) of this program, we would naively obtain the following decomposition:

def ctrl_compute_uncompute():
    qml.ctrl(qml.RX(0.5, 0), control=["ctrl"])
    qml.Toffoli(["ctrl", 0, 1])
    qml.Toffoli(["ctrl", 1, 2])
    qml.Toffoli(["ctrl", 0, 1])
    qml.ctrl(qml.adjoint(qml.RX)(0.5, 0), control=["ctrl"])

>>> print(qml.draw(ctrl_compute_uncompute, wire_order=[0, 1, 2, "ctrl"])())
   0: ─╭RX(0.50)─╭●────╭●─╭RX(0.50)†─┤
   1: ─│─────────├X─╭●─├X─│──────────┤
   2: ─│─────────│──├X─│──│──────────┤
ctrl: ─╰●────────╰●─╰●─╰●─╰●─────────┤

However, the last two gates uncompute the first two gates. This means that applying them, even if the control qubit "ctrl" is not activated, will not change the computation of the circuit. That is, we can skip the control for all but the middle gate:

def ctrl_compute_uncompute_simple():
    qml.RX(0.5, 0)
    qml.CNOT([0, 1])
    qml.Toffoli(["ctrl", 1, 2])
    qml.CNOT([0, 1])
    qml.adjoint(qml.RX)(0.5, 0)

>>> print(qml.draw(ctrl_compute_uncompute_simple, wire_order=[0, 1, 2, "ctrl"])())
   0: ──RX(0.50)─╭●────╭●──RX(0.50)†─┤
   1: ───────────╰X─╭●─╰X────────────┤
   2: ──────────────├X───────────────┤
ctrl: ──────────────╰●───────────────┤