T Complexity Of Comparison Gates#
May 2023
Abstract#
Quantum comparison gates can be split into two categories: quantum-classical when comparing a quantum number to a classical number and quantum-quantum when comparing two quantum numbers (i.e. quantum registers).
Comparison gates are an important building block for quantum algorithms, yet they are always relegated to the appendices usually with figures showing how they work only on a small number of qubits. This leads to cases where researchers potentially waste time reinventing already existing methods. This notebook intends to serve as a documentary of the current state of the art for comparison gates while explaining how they work both algorithmically and programmatically.
Note: Most of the ideas explained here are built into qualtran.
Introduction#
The current optimal implementation of a reversible oracle for comparing two quantum numbers of \(n\) qubits each is \(4n + \mathcal{O}(1)\) T operations. This is done by reducing the problem to subtraction which takes \(4n + \mathcal{O}(1)\) (see. Gidney, 2018).
This way while optimal in terms of T count has linear depth. The question of whether we can trade some T operations in order to reduce the depth of the circuit is interesting and turns out to have multiple answers. In this notebook, we consider the problem of doing a comparison at a depth logarithmic in the number of qubits \(\mathcal{O}(\log{n})\). The current best way to do this is given in the supplementary materials of Berry et al., 2018 and leverages the divide and conquer technique.
When this decomposition is applied to the case where one input is a list of qubits and the other is a classical number (i.e. a string of bits) this decomposition gives a \(6n + \mathcal{O}(1)\) T complexity.
In what follows I will explain the current T optimal ways for comparison in all cases. Our focus on T count is because T count is the bottleneck when running quantum circuits in a fault-tolerant way using surface code (see. Litinski et al., 2018)
Equality as a special case#
Before we proceed to the comparison oracle we take a look at the equality oracle actually as a special case with a T complexity of only \(4n + \mathcal{O}(1)\), as it can be implemented as a qubit-wise And operation. This qubit-wise And operation itself can be done using only \(4n + \mathcal{O}(1)\) as per Babbush et al., 2018 and Craig Gidney.
Quantum-Classical Case#
In the quantum-classical case, all we need to do is to compute qubit/bit-wise equality
In cirq-ft this can be accomplished using the And gate as And(cv=bits) where bits are the bits of the classical number.
Quantum-Quantum Case#
In the quantum-quantum case the equality is still bitwise
This is the same as the and
Where \(\oplus\) is the binary xor operation. This allows us to use qualtran’s And on the result of the xor.
from typing import Sequence
import cirq
from qualtran.cirq_interop.t_complexity_protocol import t_complexity_compat
from qualtran.bloqs.mcmt import And, MultiAnd
def equality_oracle_quantum_classical(B: int, A: Sequence[cirq.Qid], z: cirq.Qid) -> cirq.OP_TREE:
# Returns a decomposition of the oracle O_B |A>|z> = |A>|z^(A == B)> in only 4n T operations.
bits = list(reversed([(B >> i) & 1 for i in range(len(A))]))
ancilla = cirq.NamedQubit.range(len(bits) - 1, prefix='ancilla')
yield MultiAnd(cvs=bits).on(
*A, *ancilla
) # `ancilla[-1]` now has the result of equality. uses 4n T operations.
yield cirq.CNOT(ancilla[-1], z) # update result qubit.
yield MultiAnd(cvs=bits).adjoint().on(
*A, *ancilla
) # Restore the qubits to their original states.
As an example, we construct the equality gate for checking if a 3-qubit register is equal to 5. First, we print the decomposition of the gate followed by the result of running the gate on each of the 8 possibilities individually and finally the result of running the gate on the uniform superposition of all 8 possibilities.
classical_number = 5 # Classical Number to compare with.
quantum_number = cirq.NamedQubit.range(3, prefix='qn') # The qubit that will hold quantum numbers.
z = cirq.NamedQubit('z') # The qubit that will hold the comparison result.
equality_circuit = cirq.Circuit(
equality_oracle_quantum_classical(classical_number, quantum_number, z)
)
equality_circuit
ancilla0: ───junk[0]───────#4───────────────
│ │
ancilla1: ───∧─────────@───#5───────────────
│ │ │
qn0: ────────@─────────┼───MultiAnd(n=3)†───
│ │ │
qn1: ────────(0)───────┼───#2───────────────
│ │ │
qn2: ────────@─────────┼───#3───────────────
│
z: ────────────────────X────────────────────# This should have T count of 4*(3 qubits) - 4 = 8
t_complexity_compat(equality_circuit)
TComplexity(t=8, clifford=31, rotations=0)
# This cell contains helper code to visualize the output.
# You can safely skip it.
def format_dirac(s: str, n: int, m: int, quantum_classical: bool = False) -> str:
"""Reformats a dirac vector on as |input qubits|ancilla qubits|result qubit>"""
if quantum_classical:
return s[: n + 1] + '|' + s[n + 1 : -m - 1] + '|' + s[-m - 1 :]
return s[: n + 1] + '|' + s[n + 1 : 2 * n + 1] + '|' + s[2 * n + 1 : -m - 1] + '|' + s[-m - 1 :]
def check_each_possibility(
c, data_qubits, target_qubits, quantum_classical=True, qn: int = classical_number
):
sim = cirq.Simulator()
qubit_order = list(data_qubits)
not_ancilla = set(data_qubits + target_qubits)
qubit_order += [q for q in c.all_qubits() if q not in not_ancilla]
qubit_order += target_qubits
n_qubits = len(data_qubits)
if not quantum_classical:
n_qubits >>= 1
for v in range(1 << len(data_qubits)):
bits = [(v >> i) & 1 for i in range(len(data_qubits) - 1, -1, -1)]
bits += (len(qubit_order) - len(data_qubits)) * [0]
result = sim.simulate(c, qubit_order=qubit_order, initial_state=bits)
s = f'final state vector of {v} compared to {qn}'
if not quantum_classical:
msk = (1 << n_qubits) - 1
s = f'final state vector of {v >> n_qubits} compared to {v & msk}'
print(
s,
format_dirac(result.dirac_notation(), n_qubits, len(target_qubits), quantum_classical),
)
check_each_possibility(equality_circuit, quantum_number, [z])
final state vector of 0 compared to 5 |000|00|0⟩
final state vector of 1 compared to 5 |001|00|0⟩
final state vector of 2 compared to 5 |010|00|0⟩
final state vector of 3 compared to 5 |011|00|0⟩
final state vector of 4 compared to 5 |100|00|0⟩
final state vector of 5 compared to 5 |101|00|1⟩
final state vector of 6 compared to 5 |110|00|0⟩
final state vector of 7 compared to 5 |111|00|0⟩
As this is a quantum circuit, it’s important to check that it works with superpositions as well. This is why we will check the uniform superposition.
# This cell contains helper code to visualize the output.
# You can safely skip it.
def check_uniform_superposition(c, data_qubits, target_qubits, quantum_classical: bool = True):
if quantum_classical:
n_qubits = len(data_qubits)
else:
n_qubits = len(data_qubits) // 2
c = cirq.Circuit(cirq.H.on_each(data_qubits) + [c])
sim = cirq.Simulator()
qubit_order = list(data_qubits)
qubit_order += [q for q in c.all_qubits() if q not in qubit_order + target_qubits]
qubit_order += target_qubits
result = sim.simulate(c, qubit_order=qubit_order)
result = result.dirac_notation()
final = []
for s in result.split('|'):
if '⟩' not in s:
final.append(s)
continue
parts = s.split('⟩')
parts[0] = format_dirac(
'|' + parts[0] + '⟩', n_qubits, len(target_qubits), quantum_classical
)
final.append(''.join(parts))
print('Acting on the uniform superposition of all states we get:')
print('\t', ''.join(final))
check_uniform_superposition(equality_circuit, quantum_number, [z])
Acting on the uniform superposition of all states we get:
0.35|000|00|0⟩ + 0.35|001|00|0⟩ + 0.35|010|00|0⟩ + 0.35|011|00|0⟩ + 0.35|100|00|0⟩ + 0.35|101|00|1⟩ + 0.35|110|00|0⟩ + 0.35|111|00|0⟩
And for the quantum-quantum case, we have.
def equality_oracle_quantum_quantum(
A: Sequence[cirq.Qid], B: Sequence[cirq.Qid], z: cirq.Qid
) -> cirq.OP_TREE:
# Returns a decomposition of the oracle O |A>|B>|z> = |A>|B>|z^(A == B)> in only 4n T operations.
ancilla = cirq.NamedQubit.range(len(A) - 1, prefix='ancilla')
yield cirq.CNOT.on_each(zip(A, B)) # Store the bitwise xor in B.
assert len(B) >= 2
andop = MultiAnd(cvs=(0,) * len(B)) if len(B) >= 3 else And(0, 0)
yield andop.on( *B, *ancilla) # `ancilla[-1]` now has the result of equality. uses 4n T operations.
yield cirq.CNOT(ancilla[-1], z) # update result qubit.
yield andop.adjoint().on(*B, *ancilla) # Reverse the And operation.
yield cirq.CNOT.on_each(zip(A, B)) # Restore the qubits to their original states.
As we did before we construct the gate to compare two 2-qubit numbers. First, we print the decomposition of the gate followed by the result of running the gate on each of the 16 possibilities individually and finally the result of running the gate on the uniform superposition of all 16 possibilities.
first_quantum_number = cirq.NamedQubit.range(
2, prefix='P'
) # The qubit that will hold quantum numbers.
second_quantum_number = cirq.NamedQubit.range(
2, prefix='Q'
) # The qubit that will hold quantum numbers.
quantum_quantum_equality = cirq.Circuit(
equality_oracle_quantum_quantum(first_quantum_number, second_quantum_number, z)
)
quantum_quantum_equality
┌──┐ ┌──┐
P0: ──────────@───────────────────────@─────
│ │
P1: ──────────┼@──────────────────────┼@────
││ ││
Q0: ──────────X┼────(0)───────(0)─────X┼────
│ │ │ │
Q1: ───────────X────(0)───────(0)──────X────
│ │
ancilla0: ──────────And───@───And†──────────
│
z: ───────────────────────X─────────────────
└──┘ └──┘# This should have T count of 4*(2 qubits) - 4 = 4
t_complexity_compat(quantum_quantum_equality)
TComplexity(t=4, clifford=26, rotations=0)
# Now we check individual possibilities.
check_each_possibility(
quantum_quantum_equality,
first_quantum_number + second_quantum_number,
[z],
quantum_classical=False,
)
final state vector of 0 compared to 0 |00|00|0|1⟩
final state vector of 0 compared to 1 |00|01|0|0⟩
final state vector of 0 compared to 2 |00|10|0|0⟩
final state vector of 0 compared to 3 |00|11|0|0⟩
final state vector of 1 compared to 0 |01|00|0|0⟩
final state vector of 1 compared to 1 |01|01|0|1⟩
final state vector of 1 compared to 2 |01|10|0|0⟩
final state vector of 1 compared to 3 |01|11|0|0⟩
final state vector of 2 compared to 0 |10|00|0|0⟩
final state vector of 2 compared to 1 |10|01|0|0⟩
final state vector of 2 compared to 2 |10|10|0|1⟩
final state vector of 2 compared to 3 |10|11|0|0⟩
final state vector of 3 compared to 0 |11|00|0|0⟩
final state vector of 3 compared to 1 |11|01|0|0⟩
final state vector of 3 compared to 2 |11|10|0|0⟩
final state vector of 3 compared to 3 |11|11|0|1⟩
# Finally we check the uniform superposition.
check_uniform_superposition(
quantum_quantum_equality,
first_quantum_number + second_quantum_number,
[z],
quantum_classical=False,
)
Acting on the uniform superposition of all states we get:
0.25|00|00|0|1⟩ + 0.25|00|01|0|0⟩ + 0.25|00|10|0|0⟩ + 0.25|00|11|0|0⟩ + 0.25|01|00|0|0⟩ + 0.25|01|01|0|1⟩ + 0.25|01|10|0|0⟩ + 0.25|01|11|0|0⟩ + 0.25|10|00|0|0⟩ + 0.25|10|01|0|0⟩ + 0.25|10|10|0|1⟩ + 0.25|10|11|0|0⟩ + 0.25|11|00|0|0⟩ + 0.25|11|01|0|0⟩ + 0.25|11|10|0|0⟩ + 0.25|11|11|0|1⟩
Notice that the ancilla qubit are always clean at the end of execution and that the input qubits are not affected
Definition of the Comparison Operator#
Before we proceed let’s formally define the the operator we want to implement. The operator is the less-than-operator. We chose to focus on this case since the \(\leq\) and greater than cases differ by only Clifford operations.
There are two versions of this operator. The first is the quantum-quantum case where we compare two-qubit register \(\ket{p}\) and \(\ket{q}\) and store the result in qubit \(z\).
The second is the quantum-classical case, where we compare a quantum register \(\ket{p}\) to classical number \(v\) (i.e. string of bits)
The Quantum-Quantum Comparator \(8n + \mathcal{O}(1)\) T gates#
For this case, the optimal decomposition in T count with logarithmic depth was proposed by Berry et al., 2018 and has \(8n + \mathcal{O}(1)\) T complexity. This decomposition leverages the divide and conquer technique and builds a binary tree of depth \(\log_2{(n)}\) whose leaves are the qubits of the numbers with intermediate values stored in \(\mathcal{O}(n)\) ancillas. Each non-leaf node uses two CSWAP operations and the value of the comparison is computed from the root node using one Toffoli.
Before we get into the implementation detail of this gate we will discuss two special cases \(n=1\) and \(n=2\) because as we will see later the general case is built out of these cases.
\(n = 1\) Case#
Given 2 qubits, we would like a way to represent the three cases of equality, less than, greater than in a reversible way. This can be done using two extra qubits less_than and greater_than which will hold the less than and greater than while equality will be held in the second operand (qubit). In other words implementing the operator
Note that this is different from our original goal to compute
CNOT with its control being the first ancilla and its target being qubit \(z\).
def single_qubit_compare(
p: cirq.Qid, q: cirq.Qid, lz: cirq.Qid, less_than: cirq.Qid, greater_than: cirq.Qid
) -> cirq.OP_TREE:
anc = cirq.NamedQubit.range(2, prefix='anc')
# The case p < q happens only when
# p=0 and y=1 so it's simply a controlled-controlled-not.
yield cirq.X(p) # Flip p
yield cirq.CCNOT(p, q, anc[0])
yield cirq.X(p) # Restore p
# The case p = q happens only when the xor sum is zero.
yield cirq.CNOT(p, q) # Store xor sum in q.
yield cirq.X(q) # Flip q.
# The case p > q can be done in the same manner as the first case,
# however we don't need to since it's simply not equality and
# not less than. This saves us the cost of one CCNOT gate (i.e. Toffoli gate = 4 T gates)
yield cirq.X(anc[1]) # Initial belief is that p > q
yield cirq.CNOT(q, anc[1]) # But not if p=q
yield cirq.CNOT(anc[0], anc[1]) # OR if p < q.
yield cirq.CNOT(anc[0], less_than)
yield cirq.CNOT(q, z)
yield cirq.CNOT(anc[1], greater_than)
# Undo changes done the data and ancilla qubits.
yield cirq.CNOT(anc[0], anc[1])
yield cirq.CNOT(q, anc[1])
yield cirq.X(anc[1])
yield cirq.X(q)
yield cirq.CNOT(p, q)
yield cirq.X(p)
yield cirq.CCNOT(p, q, anc[0])
yield cirq.X(p)
less_than = cirq.NamedQubit('less_than')
greater_than = cirq.NamedQubit('greater_than')
single_qubit_compare_circuit = cirq.Circuit(
single_qubit_compare(
first_quantum_number[0], second_quantum_number[0], z, less_than, greater_than
)
)
single_qubit_compare_circuit
┌──┐ ┌──┐
P0: ─────────────X───@───X───@─────────────────────────────────────@───X───@───X───
│ │ │ │
Q0: ─────────────────@───────X───X───@─────@───────────────@───X───X───────@───────
│ │ │ │ │
anc0: ───────────────X───────────────┼────@┼─────@─────@───┼───────────────X───────
│ ││ │ │ │
anc1: ───────────X───────────────────X────X┼─────┼@────X───X───X───────────────────
│ ││
greater_than: ─────────────────────────────┼─────┼X────────────────────────────────
│ │
less_than: ────────────────────────────────┼─────X─────────────────────────────────
│
z: ────────────────────────────────────────X───────────────────────────────────────
└──┘ └──┘# Now we check individual possibilities.
# The output for this and the following circuits
# will be three qubits in the order [less_than, equal, greater_than]
check_each_possibility(
single_qubit_compare_circuit,
[first_quantum_number[0], second_quantum_number[0]],
[less_than, z, greater_than],
quantum_classical=False,
)
final state vector of 0 compared to 0 |0|0|00|010⟩
final state vector of 0 compared to 1 |0|1|00|100⟩
final state vector of 1 compared to 0 |1|0|00|001⟩
final state vector of 1 compared to 1 |1|1|00|010⟩
check_uniform_superposition(
single_qubit_compare_circuit,
[first_quantum_number[0], second_quantum_number[0]],
[less_than, z, greater_than],
quantum_classical=False,
)
Acting on the uniform superposition of all states we get:
0.5|0|0|00|010⟩ + 0.5|0|1|00|100⟩ + 0.5|1|0|00|001⟩ + 0.5|1|1|00|010⟩
A slightly different circuit is given in the paper which we implemented in qualtran as SingleQubitCompare and has a cost of only one CCNOT (i.e. Toffoli = 4T).
SingleQubitCompare is implemented using measurement-based uncomputation so that its adjoint has a T count of zero.
\(n=2\) Case#
In this case the two qubit numbers \(P\) and \(Q\) can be written as
We will do this in two steps. First we update qubits such that \(\mathrm{sign}(P - Q) = \mathrm{sign}(p_0^f - q_0^f)\) where \(p_0^f\) and \(q_0^f\) are the final values of \(p_0\) and \(q_0\) respectively. This way the comparison result between the two numbers can be extracted using SingleQubitCompare applied on \(p_0^f\) and \(q_0^f\).
Notice that if \(p_1 = q_1\) then we don’t need to do anything since \(p_0\) and \(q_0\) are already in the required state, but when \(p_1 \neq q_1\) then all we need to do is to swap the qubits of each number since the result of comparing \(P\) and \(Q\) is the same as comparing \(p_1\) and \(q_1\).
def bi_qubit_mixer(P, Q) -> cirq.OP_TREE:
p_1, p_0 = P
q_1, q_0 = Q
ancilla = cirq.NamedQubit('anc')
yield cirq.CNOT(p_1, ancilla)
yield cirq.CNOT(q_1, ancilla) # Now ancilla has p_1 != q_1
# SWAP iff p_1 != q_1 => ancilla = 1.
yield cirq.CSWAP(ancilla, p_1, p_0)
yield cirq.CSWAP(ancilla, q_1, q_0)
In Berry et al., 2018 the circuit that does the first step is called COMPARE2 (FIG. 1 in the supplementary materials) and we implemented it in qualtran as BiQubitsMixer. This circuit is different from the simple circuit above. Yet both are equivalent as we will see below with this circuit having a smaller number of Clifford operations.
Each of the CSWAP operations has a T count of 4. We again utilized measurement-based uncomputation so that the adjoint of BiQubitsMixer has zero T count.
from qualtran.bloqs.arithmetic import SingleQubitCompare, BiQubitsMixer
def compare_two(
P: Sequence[cirq.Qid], Q: Sequence[cirq.Qid], equal, less_than, greater_than
) -> cirq.OP_TREE:
# Put the qubits in little-endian order.
P = P[::-1]
Q = Q[::-1]
xor = cirq.NamedQubit('xor')
yield cirq.CNOT(P[1], xor)
yield cirq.CNOT(Q[1], xor) # Has the p_1^q_1 which is 1 iff p_1 != q_1.
# SWAP iff p_1 != q_1 => xor = 1.
yield cirq.CSWAP(xor, *P)
yield cirq.CSWAP(xor, *Q)
anc = cirq.NamedQubit.range(2, prefix='anc')
yield SingleQubitCompare()(P[0], Q[0], *anc)
yield cirq.CNOT(anc[0], less_than)
yield cirq.CNOT(Q[0], equal)
yield cirq.CNOT(anc[1], greater_than)
# Undo changes made to the data qubits.
yield SingleQubitCompare().adjoint().on(P[0], Q[0], *anc)
yield cirq.CSWAP(xor, *Q)
yield cirq.CSWAP(xor, *P)
yield cirq.CNOT(Q[1], xor)
yield cirq.CNOT(P[1], xor)
compare_two_circuit = cirq.Circuit(
compare_two(first_quantum_number, second_quantum_number, z, less_than, greater_than)
)
compare_two_circuit
┌───┐
P0: ─────────────@───────×─────────────────────────────────────────────────────────────×───────@───
│ │ │ │
P1: ─────────────┼───────×───────SingleQubitCompare───────────SingleQubitCompare───────×───────┼───
│ │ │ │ │ │
Q0: ─────────────┼───@───┼───×───┼────────────────────────────┼────────────────────×───┼───@───┼───
│ │ │ │ │ │ │ │ │ │
Q1: ─────────────┼───┼───┼───×───b──────────────────────@─────b────────────────────×───┼───┼───┼───
│ │ │ │ │ │ │ │ │ │ │
anc0: ───────────┼───┼───┼───┼───less_than─────────────@┼─────less_than────────────┼───┼───┼───┼───
│ │ │ │ │ ││ │ │ │ │ │
anc1: ───────────┼───┼───┼───┼───greater_than──────────┼┼@────greater_than─────────┼───┼───┼───┼───
│ │ │ │ │││ │ │ │ │
greater_than: ───┼───┼───┼───┼─────────────────────────┼┼X─────────────────────────┼───┼───┼───┼───
│ │ │ │ ││ │ │ │ │
less_than: ──────┼───┼───┼───┼─────────────────────────X┼──────────────────────────┼───┼───┼───┼───
│ │ │ │ │ │ │ │ │
xor: ────────────X───X───@───@──────────────────────────┼──────────────────────────@───@───X───X───
│
z: ─────────────────────────────────────────────────────X──────────────────────────────────────────
└───┘# Now we check individual possibilities.
check_each_possibility(
compare_two_circuit,
first_quantum_number + second_quantum_number,
[less_than, z, greater_than],
quantum_classical=False,
)
final state vector of 0 compared to 0 |00|00|000|010⟩
final state vector of 0 compared to 1 |00|01|000|100⟩
final state vector of 0 compared to 2 |00|10|000|100⟩
final state vector of 0 compared to 3 |00|11|000|100⟩
final state vector of 1 compared to 0 |01|00|000|001⟩
final state vector of 1 compared to 1 |01|01|000|010⟩
final state vector of 1 compared to 2 |01|10|000|100⟩
final state vector of 1 compared to 3 |01|11|000|100⟩
final state vector of 2 compared to 0 |10|00|000|001⟩
final state vector of 2 compared to 1 |10|01|000|001⟩
final state vector of 2 compared to 2 |10|10|000|010⟩
final state vector of 2 compared to 3 |10|11|000|100⟩
final state vector of 3 compared to 0 |11|00|000|001⟩
final state vector of 3 compared to 1 |11|01|000|001⟩
final state vector of 3 compared to 2 |11|10|000|001⟩
final state vector of 3 compared to 3 |11|11|000|010⟩
check_uniform_superposition(
compare_two_circuit,
first_quantum_number + second_quantum_number,
[less_than, z, greater_than],
quantum_classical=False,
)
Acting on the uniform superposition of all states we get:
0.25|00|00|000|010⟩ + 0.25|00|01|000|100⟩ + 0.25|00|10|000|100⟩ + 0.25|00|11|000|100⟩ + 0.25|01|00|000|001⟩ + 0.25|01|01|000|010⟩ + 0.25|01|10|000|100⟩ + 0.25|01|11|000|100⟩ + 0.25|10|00|000|001⟩ + 0.25|10|01|000|001⟩ + 0.25|10|10|000|010⟩ + 0.25|10|11|000|100⟩ + 0.25|11|00|000|001⟩ + 0.25|11|01|000|001⟩ + 0.25|11|10|000|001⟩ + 0.25|11|11|000|010⟩
Now notice that for \(n > 2\) we can group the qubits in \(\frac{n}{2}\) pairs and use our COMPARE2 circuit to compare them, in other words:
The comparison result of the original sequences \(P\) and \(Q\) of length \(n\) is preserved in this \(\frac{n}{2}\) sequence.
Doing this \(\log_2{n}\) times gives a circuit that has a tree structure (FIG. 2 of the supplementary materials of Berry et al., 2018) of depth \(\log_2{n}\) where each layer/depth contains independent operations. So the circuit has logarithmic depth.
Note that as in the case of 2 qubits, we still need a final SingleQubitCompare operation to extract the result.
def quantum_quantum_comparator(
A: Sequence[cirq.Qid],
B: Sequence[cirq.Qid],
z: cirq.Qid,
less_than: cirq.Qid,
greater_than: cirq.Qid,
):
adjoint = []
anc_cnt = 0
def build_tree(A: Sequence[cirq.Qid], B: Sequence[cirq.Qid]) -> cirq.OP_TREE:
nonlocal adjoint, anc_cnt
if len(A) <= 1:
return
if len(A) == 2:
anc = [cirq.NamedQubit(f'anc_{i+anc_cnt}') for i in range(3)]
anc_cnt += 3
op = BiQubitsMixer().on_registers(x=A, y=B, ancilla=anc)
yield op
adjoint.append(op**-1)
return
m = len(A) >> 1
yield from build_tree(A[:m], B[:m])
yield from build_tree(A[m:], B[m:])
anc = [cirq.NamedQubit(f'anc_{i+anc_cnt}') for i in range(3)]
anc_cnt += 3
op = BiQubitsMixer().on_registers(
x=(A[m - 1], A[-1]), y=(B[m - 1], B[-1]), ancilla=anc
)
yield op
adjoint.append(op**-1)
# Build Tree
yield from build_tree(A, B)
# Add the final SingleQubitCompare
anc = [cirq.NamedQubit(f'anc_{i+anc_cnt}') for i in range(2)]
anc_cnt += 2
op = SingleQubitCompare()(A[-1], B[-1], *anc)
yield op
# Update result qubits.
yield cirq.CNOT(anc[0], less_than)
yield cirq.CNOT(B[-1], z)
yield cirq.CNOT(anc[1], greater_than)
# Undo changes made to data and ancilla qubits.
yield op**-1
yield from reversed(adjoint)
P = cirq.NamedQubit.range(3, prefix='p_')
Q = cirq.NamedQubit.range(3, prefix='q_')
quantum_compare = cirq.Circuit(quantum_quantum_comparator(P, Q, z, less_than, greater_than))
quantum_compare
┌──┐
anc_0: ──────────ancilla──────────────────────────────────────────────────────────────────────────────────────────ancilla─────────
│ │
anc_1: ──────────ancilla──────────────────────────────────────────────────────────────────────────────────────────ancilla─────────
│ │
anc_2: ──────────ancilla──────────────────────────────────────────────────────────────────────────────────────────ancilla─────────
│ │
anc_3: ──────────┼───────────────ancilla──────────────────────────────────────────────────────────ancilla─────────┼───────────────
│ │ │ │
anc_4: ──────────┼───────────────ancilla──────────────────────────────────────────────────────────ancilla─────────┼───────────────
│ │ │ │
anc_5: ──────────┼───────────────ancilla──────────────────────────────────────────────────────────ancilla─────────┼───────────────
│ │ │ │
anc_6: ──────────┼───────────────┼───────────────less_than─────────────@─────less_than────────────┼───────────────┼───────────────
│ │ │ │ │ │ │
anc_7: ──────────┼───────────────┼───────────────greater_than──────────┼@────greater_than─────────┼───────────────┼───────────────
│ │ │ ││ │ │ │
greater_than: ───┼───────────────┼───────────────┼─────────────────────┼X────┼────────────────────┼───────────────┼───────────────
│ │ │ │ │ │ │
less_than: ──────┼───────────────┼───────────────┼─────────────────────X─────┼────────────────────┼───────────────┼───────────────
│ │ │ │ │ │
p_0: ────────────┼───────────────BiQubitsMixer───┼───────────────────────────┼────────────────────BiQubitsMixer───┼───────────────
│ │ │ │ │ │
p_1: ────────────BiQubitsMixer───┼───────────────┼───────────────────────────┼────────────────────┼───────────────BiQubitsMixer───
│ │ │ │ │ │
p_2: ────────────x───────────────x───────────────SingleQubitCompare──────────SingleQubitCompare───x───────────────x───────────────
│ │ │ │ │ │
q_0: ────────────┼───────────────y───────────────┼───────────────────────────┼────────────────────y───────────────┼───────────────
│ │ │ │ │ │
q_1: ────────────y───────────────┼───────────────┼───────────────────────────┼────────────────────┼───────────────y───────────────
│ │ │ │ │ │
q_2: ────────────y───────────────y───────────────b─────────────────────@─────b────────────────────y───────────────y───────────────
│
z: ────────────────────────────────────────────────────────────────────X──────────────────────────────────────────────────────────
└──┘# This should have T count of 8*(3 qubits) - 4 = 20
t_complexity_compat(quantum_compare)
TComplexity(t=20, clifford=122, rotations=0)
# Now we check individual possibilities.
# Note it's a bit slow to simulate the 64 possibilities.
run_check = False # Change this to True to run the check.
if run_check:
check_each_possibility(
quantum_compare, P + Q, [less_than, z, greater_than], quantum_classical=False
)
check_uniform_superposition(
quantum_compare, P + Q, [less_than, z, greater_than], quantum_classical=False
)
Acting on the uniform superposition of all states we get:
0.12|000|000|00000000|010⟩ + 0.12|000|001|00000000|100⟩ + 0.12|000|010|00000000|100⟩ + 0.12|000|011|00000000|100⟩ + 0.12|000|100|00000000|100⟩ + 0.12|000|101|00000000|100⟩ + 0.12|000|110|00000000|100⟩ + 0.12|000|111|00000000|100⟩ + 0.12|001|000|00000000|001⟩ + 0.12|001|001|00000000|010⟩ + 0.12|001|010|00000000|100⟩ + 0.12|001|011|00000000|100⟩ + 0.12|001|100|00000000|100⟩ + 0.12|001|101|00000000|100⟩ + 0.12|001|110|00000000|100⟩ + 0.12|001|111|00000000|100⟩ + 0.12|010|000|00000000|001⟩ + 0.12|010|001|00000000|001⟩ + 0.12|010|010|00000000|010⟩ + 0.12|010|011|00000000|100⟩ + 0.12|010|100|00000000|100⟩ + 0.12|010|101|00000000|100⟩ + 0.12|010|110|00000000|100⟩ + 0.12|010|111|00000000|100⟩ + 0.12|011|000|00000000|001⟩ + 0.12|011|001|00000000|001⟩ + 0.12|011|010|00000000|001⟩ + 0.12|011|011|00000000|010⟩ + 0.12|011|100|00000000|100⟩ + 0.12|011|101|00000000|100⟩ + 0.12|011|110|00000000|100⟩ + 0.12|011|111|00000000|100⟩ + 0.12|100|000|00000000|001⟩ + 0.12|100|001|00000000|001⟩ + 0.12|100|010|00000000|001⟩ + 0.12|100|011|00000000|001⟩ + 0.12|100|100|00000000|010⟩ + 0.12|100|101|00000000|100⟩ + 0.12|100|110|00000000|100⟩ + 0.12|100|111|00000000|100⟩ + 0.12|101|000|00000000|001⟩ + 0.12|101|001|00000000|001⟩ + 0.12|101|010|00000000|001⟩ + 0.12|101|011|00000000|001⟩ + 0.12|101|100|00000000|001⟩ + 0.12|101|101|00000000|010⟩ + 0.12|101|110|00000000|100⟩ + 0.12|101|111|00000000|100⟩ + 0.12|110|000|00000000|001⟩ + 0.12|110|001|00000000|001⟩ + 0.12|110|010|00000000|001⟩ + 0.12|110|011|00000000|001⟩ + 0.12|110|100|00000000|001⟩ + 0.12|110|101|00000000|001⟩ + 0.12|110|110|00000000|010⟩ + 0.12|110|111|00000000|100⟩ + 0.12|111|000|00000000|001⟩ + 0.12|111|001|00000000|001⟩ + 0.12|111|010|00000000|001⟩ + 0.12|111|011|00000000|001⟩ + 0.12|111|100|00000000|001⟩ + 0.12|111|101|00000000|001⟩ + 0.12|111|110|00000000|001⟩ + 0.12|111|111|00000000|010⟩
T Complexity Analysis#
The tree from above has \(n-1\) nodes. Each of these nodes does a BiQubitsMixer and its adjoint gives a T count of \(8 + 0 = 8\) per node. The final step is a SingleQubitCompare which has a T count of \(4 + 0 = 4\). This gives a total of \(8(n-1) + 4 = 8n-4\) T operations.
Note that the adjoints of SingleQubitCompare and BiQubitsMixer have zero T count as discussed above.
\(\mathcal{O}(6n)\) Quantum-Classical Comparator with logarithmic depth#
We can use the tree structure we have for this case to achieve the desired depth. However, we need a new version of BiQubitsMixer that expects just one quantum number with the other being classical. This new version will have the advantage of processing a classical number so it can tweak its structure to reduce its T count.
Notice that our original BiQubitsMixer has two CSWAP operations with one of them swapping the two qubits of \(Q\) but in our case, \(Q\) is just a classical number and the CSWAP operation degenerates into either identity when the two bits of the numbers are equal (e.g. \(Q \in \{0, 3\}\)) or a CNOT when they are different (e.g. \(Q \in \{1, 2\}\)). This reduces the T count by half going from 8 to 4.
def quantum_classical_mixer(P: Sequence[cirq.Qid], Q: int):
P = P[::-1]
ancilla = cirq.NamedQubit('ancilla')
# Create the qubit that will represent Q.
qubit_for_q = cirq.NamedQubit('q')
operations = []
q_0 = Q & 1 # The 0th bit of Q.
q_1 = (Q >> 1) & 1 # The 1s bit of Q.
# Copy q_0 to `qubit_for_q`
if q_0:
operations.append(cirq.X(qubit_for_q))
# Store the xor of p_1 and q_1 into ancilla
operations.append(cirq.CNOT(P[1], ancilla))
if q_1:
operations.append(cirq.X(ancilla))
# Do CSWAP on `P`
cswap_ancilla = cirq.NamedQubit('cswap_ancilla')
operations.append(cirq.CNOT(*P))
operations.append(And()(ancilla, P[1], cswap_ancilla))
operations.append(cirq.CNOT(cswap_ancilla, P[0]))
operations.append(cirq.CNOT(*P))
# Second CSWAP collapses to either identity or CNOT.
if q_0 != q_1:
operations.append(cirq.CNOT(ancilla, qubit_for_q))
return operations, qubit_for_q
# For example when Q = 2 this is what the circuit looks like.
circuit, q = quantum_classical_mixer(first_quantum_number, 2)
circuit = cirq.Circuit(circuit)
circuit
┌──┐
P0: ──────────────@───X───@────────────X───
│ │ │ │
P1: ──────────────┼───@───┼──────X─────@───
│ │ │
ancilla: ─────────X───X───@──────┼@────────
│ ││
cswap_ancilla: ───────────And────@┼────────
│
q: ───────────────────────────────X────────
└──┘# Now let's add SingleQubitCompare and build the full comparator.
def quantum_classical_comparator_logn(
P: Sequence[cirq.Qid], Q: int, z: cirq.Qid, less_than: cirq.Qid, greater_than: cirq.Qid
):
mixer, q = quantum_classical_mixer(P, Q)
yield mixer
anc = cirq.NamedQubit.range(2, prefix='anc')
yield SingleQubitCompare()(P[1], q, *anc)
yield cirq.CNOT(anc[0], less_than)
yield cirq.CNOT(q, z)
yield cirq.CNOT(anc[-1], greater_than)
yield SingleQubitCompare().adjoint().on(P[1], q, *anc)
yield from reversed([op**-1 for op in mixer])
q_n = 2
circuit = cirq.Circuit(
quantum_classical_comparator_logn(first_quantum_number, q_n, z, less_than, greater_than)
)
circuit
┌──┐ ┌──┐
P0: ──────────────@───X───@────────────X────────────────────────────────────────────────────X───────@──────X───@───
│ │ │ │ │ │ │ │
P1: ──────────────┼───@───┼──────X─────@───SingleQubitCompare──────────SingleQubitCompare───@───X───┼──────@───┼───
│ │ │ │ │ │ │ │
anc0: ────────────┼───────┼──────┼─────────less_than─────────────@─────less_than────────────────┼───┼──────────┼───
│ │ │ │ │ │ │ │ │
anc1: ────────────┼───────┼──────┼─────────greater_than──────────┼@────greater_than─────────────┼───┼──────────┼───
│ │ │ │ ││ │ │ │ │
ancilla: ─────────X───X───@──────┼@────────┼─────────────────────┼┼────┼────────────────────@───┼───@──────X───X───
│ ││ │ ││ │ │ │ │
cswap_ancilla: ───────────And────@┼────────┼─────────────────────┼┼────┼────────────────────┼───@───And†───────────
│ │ ││ │ │
greater_than: ────────────────────┼────────┼─────────────────────┼X────┼────────────────────┼──────────────────────
│ │ │ │ │
less_than: ───────────────────────┼────────┼─────────────────────X─────┼────────────────────┼──────────────────────
│ │ │ │
q: ───────────────────────────────X────────b─────────────────────@─────b────────────────────X──────────────────────
│
z: ──────────────────────────────────────────────────────────────X─────────────────────────────────────────────────
└──┘ └──┘# This should have T complexity of 6*(2 qubits) + O(1)
t_complexity_compat(circuit)
TComplexity(t=8, clifford=55, rotations=0)
# Now we check individual possibilities.
check_each_possibility(circuit, first_quantum_number, [less_than, z, greater_than], qn=q_n)
final state vector of 0 compared to 2 |00|00000|100⟩
final state vector of 1 compared to 2 |01|00000|100⟩
final state vector of 2 compared to 2 |10|00000|010⟩
final state vector of 3 compared to 2 |11|00000|001⟩
check_uniform_superposition(circuit, first_quantum_number, [less_than, z, greater_than])
Acting on the uniform superposition of all states we get:
0.5|00|00000|100⟩ + 0.5|01|00000|100⟩ + 0.5|10|00000|010⟩ + 0.5|11|00000|001⟩
T Complexity Analysis#
Now that we have our quantum_classical_mixer we can use it in our tree. However, we can’t use it except at the last layer of the tree (leaf nodes), since that’s the only layer that sees the classical number. This means that only this layer can benefit from the classical information. The number of nodes in this layer is \(\frac{n-1}{2}\) since this is a binary tree with \(n-1\) nodes.
Putting all of it together we get 4T for the \(\frac{n-1}{2}\) leaf nodes, 8T for the \(\frac{n-1}{2}\) internal nodes, 4T for the final SingleQubitCompare or
Where the constant (\(\approx -2\)) depends only on the parity of \(n\).
Bonus: The quantum-classical comparator with \(4n + \mathcal{O}(1)\) T gates and linear depth#
Inspiration#
Berry et al., 2019 reduced the problem to subtraction, we however take a different approach. Note that comparing two numbers of equal size is the same finding which of them is lexicographically smaller. This problem is usually solved sequentially and is essentially a finite state machine of \(n + 3\) states each having two transitions. The result is an almost identical decomposition (up to Clifford operations) with the same T complexity.
More concretely, consider how C/C++ std::strcmp compares two sequences \(A\) and \(B\) of equal length \(n\). The function scans the sequences from left to right until the first index \(i^*\) where they differ and returns \(A_{i^*} < B_{i^*}\).
Implicitly this algorithm has \(n + 3\) states \(\{e_0, \ldots, e_n\} \cup \{L, R\}\) where being in the \(e_k\) state means the prefixes of length \(k\) are equal. with transitions being the states governed by:
When the result of comparison between individual indices becomes probabilistic these states form a Markov decision process with three terminal states \(\{L, e_n, R\}\). This gives us inspiration for a new implementation.
Algorithm#
We start by allocating \(n+1\) qubits representing the \(e_0, \ldots, e_n\) states and then scan the qubit register and number from left to right.
if the current bit is zero then we only need to compute the \(e_k \rightarrow e_{k+1}\) transition since the qubit can’t be less than zero. otherwise, we need to compute the transition as well as the \(e_k → L\) transition.
def less_than(B: int, A: Sequence[cirq.Qid], z: cirq.Qid) -> cirq.OP_TREE:
# Returns a decomposition of the oracle O_B |A>z> = |A>|z^(A < B)> in only 4n T operations.
bits = [(B >> i) & 1 for i in range(len(A) - 1, -1, -1)]
adjoint = []
es = cirq.NamedQubit.range(len(A) + 1, prefix='e_')
ek = es.pop(0)
# Initially we believe that the numbers are equal.
yield cirq.X(ek)
adjoint.append(cirq.X(ek))
for q, b, ekp1 in zip(A, bits, es):
if b:
yield cirq.X(q)
adjoint.append(cirq.X(q))
# Temporarily hold e_k and not q
yield And().on(q, ek, ekp1)
adjoint.append(And().adjoint().on(q, ek, ekp1))
# e_{k+1} currently has are_equal so far and (q != b)
# which is equivalent to: Is the current prefix of the qubits < the prefix of B and the previous prefix equal?
yield cirq.CNOT(ekp1, z)
yield cirq.CNOT(ek, ekp1) # Now e_{k+1} has the prefix equality.
adjoint.append(cirq.CNOT(ek, ekp1))
else:
# e_{k+1} = e_k and not q
yield And(1, 0).on(ek, q, ekp1)
adjoint.append(And(1, 0).adjoint().on(ek, q, ekp1))
ek = ekp1
yield from reversed(adjoint)
As we did before we construct the less than gate for checking if a 3 registers are less than 5. First, we print the decomposition of the gate followed by the result of running the gate on each of 8 possiblities individually and finally the result of running the gate on the uniform superposition of all 8 possibilities.
less_than_circuit = cirq.Circuit(less_than(classical_number, quantum_number, z))
less_than_circuit
e_0: ───X───@─────────@─────────────────────────────────────────@───@──────X───
│ │ │ │
e_1: ───────And───@───X───@──────────────────────────────@──────X───And†───────
│ │ │ │ │
e_2: ───────┼─────┼───────And───@─────────@───@───@──────And†───────┼──────────
│ │ │ │ │ │ │ │ │
e_3: ───────┼─────┼───────┼─────And───@───X───X───And†───┼──────────┼──────────
│ │ │ │ │ │ │ │
qn0: ───X───@─────┼───────┼─────┼─────┼───────────┼──────┼──────────@──────X───
│ │ │ │ │ │
qn1: ─────────────┼───────(0)───┼─────┼───────────┼──────(0)───────────────────
│ │ │ │
qn2: ───X─────────┼─────────────@─────┼───────────@──────X─────────────────────
│ │
z: ───────────────X───────────────────X────────────────────────────────────────# T count should be 4*(3 qubits) = 12
t_complexity_compat(less_than_circuit)
TComplexity(t=12, clifford=55, rotations=0)
# Now we check individual possibilities.
check_each_possibility(less_than_circuit, quantum_number, [z])
final state vector of 0 compared to 5 |000|0000|1⟩
final state vector of 1 compared to 5 |001|0000|1⟩
final state vector of 2 compared to 5 |010|0000|1⟩
final state vector of 3 compared to 5 |011|0000|1⟩
final state vector of 4 compared to 5 |100|0000|1⟩
final state vector of 5 compared to 5 |101|0000|0⟩
final state vector of 6 compared to 5 |110|0000|0⟩
final state vector of 7 compared to 5 |111|0000|0⟩
# Finally we check the uniform superposition.
check_uniform_superposition(less_than_circuit, quantum_number, [z])
Acting on the uniform superposition of all states we get:
0.35|000|0000|1⟩ + 0.35|001|0000|1⟩ + 0.35|010|0000|1⟩ + 0.35|011|0000|1⟩ + 0.35|100|0000|1⟩ + 0.35|101|0000|0⟩ + 0.35|110|0000|0⟩ + 0.35|111|0000|0⟩
And as before, notice that the ancilla qubits are always clean at the end of execution and that the input qubits are not affected.
Improving the constant#
The implementation above has a T complexity of exactly \(4n\) since there are exactly \(n\) And gates each uses \(4\) Ts. Note however that the first of them is not needed since one of its inputs is in the \(\ket{1}\) state so it collapses to either identity or cirq.X depending on the most significant bit of \(B\). This gives a T complexity of \(4(n-1) = 4n - 4\).
Citation#
@article{Noureldin_2023,
doi = {10.5281/zenodo.8384491},
url = {https://doi.org/10.5281/zenodo.8384491},
year = 2023,
author = {Noureldin Yosri},
title = {T Complexity Of Comparison Gates},
}