What is a quantum binary comparator?
A binary comparator is a digital circuit which evaluates whether a certain bit sequence is greater than, equal to, or smaller than another bit sequence.
In classical digital circuits, binary comparators have the following logic gates configurations:
Here, a and b are the input bits. This circuit has three output bits based on the comparison results of a and b.
The digital circuit above has the following truth table:
|
|
|
| a < b
| a > b
| a == b
|
0 | 1 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 1 | 0 | 0 |
1 | 0 | 0 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 0 | 0 | 1 |
Binary comparator in quantum computing
The motivation behind building a binary comparator in quantum computing is the same, that is, comparing two qubit sequences. However, as quantum technology is fundamentally different from classical digital technology, the implementation of binary comparator in a quantum circuit will be different.
Let’s say we have two qubits, a and b and we want to compare them. The following is the quantum circuit of the binary comparator above:
In this circuit we have 4 outputs, a and b are the same as the input, and x and y are to determine the comparison output. Consider the following truth table:
|
|
|
|
0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 0 |
We can see that x = 1 and y = 0 represent a > b, x = 0, and y = 1 represent a < b, and x = y = 0 represents a = b.
This circuit can be extended to multiple qubits using the CCNOT gates. The output of the higher significant qubit circuit is used as input of the CCNOT gates to dominate the lower significant qubit circuit, and the output of the lower significant qubit circuit as the input of the CCNOT gates C2 and C3 to decide the output. Consider the following configuration for a two-qubit comparison:
In comparator circuits the comparison is done bit-wise from the most significant qubit to the least significant qubit. In the circuit above, the first 2 qubits a1 and b1 are compared. If a1 and b1 are the same, the Toffoli gate C1 will transfer the domination to the second qubit.
Code example
Let’s implement the 1-qubit quantum binary comparator in Cirq.
import cirqcircuit = cirq.Circuit()qubits = cirq.LineQubit.range(4)circuit.append(cirq.H(qubits[1]))circuit.append(cirq.X(qubits[1]))circuit.append(cirq.CCX(qubits[0], qubits[1], qubits[2]))circuit.append(cirq.X(qubits[1]))circuit.append(cirq.X(qubits[0]))circuit.append(cirq.CCX(qubits[0], qubits[1], qubits[3]))circuit.append(cirq.X(qubits[0]))circuit.append(cirq.measure(qubits[2], qubits[3], key='result'))print(circuit)# Initialize the simulators = cirq.Simulator()# Sample the circuitsamples = s.run(circuit, repetitions=1024)counts = samples.histogram(key='result')print(counts)
Code explanation
In the code above:
- Lines 3–4: We create the skeletal quantum circuit with 4 qubits.
- Lines 5–12: We add suitable quantum gates to the quantum circuit.
- Lines 22–24: We simulate the circuit and print the results.
In a similar way, we can extend this quantum circuit to compare qubit sequences with more than one qubits.
Free Resources