The Deutsch algorithm decides whether a function \(f : \{0, 1\} \rightarrow \{0, 1\}\) is constant (\(f(0) = f(1)\)) or balanced (for this problem, \(f(0) \ne f(1)\), but see also the Deutsch–Jozsa algorithm).
There are four possible functions, \(f_i\), as follows:
| Function | \(f_i(0)\) | \(f_i(1)\) | Type |
|---|---|---|---|
| \(f_0\) | 0 | 0 | Constant |
| \(f_1\) | 0 | 1 | Balanced |
| \(f_2\) | 1 | 0 | Balanced |
| \(f_3\) | 1 | 1 | Constant |
Classically, we would need to query \(f\) twice to decide whether an unknown function is constant or balanced. The quantum algorithm uses superposition to get the answer in one query.
I worked through the sums and circuit notation in this post. Below, circuits for running the algorithm for each of the four functions on one of IBM Quantum‘s quantum computers, ibmq_quito. I ran each 1,000 times to see how often an actual quantum computer(!) gets the right answer. I’ve also pasted in the Python code, which was generated automatically, and can be used to setup the circuits again.
The measurement outcome should be 1 for a constant function and 0 for a balanced function. As you can see, the modal answer across runs is correct, but there is a bit of noise.
f0 (constant)
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit from numpy import pi qreg_q = QuantumRegister(2, 'q') creg_c = ClassicalRegister(1, 'c') circuit = QuantumCircuit(qreg_q, creg_c) circuit.reset(qreg_q[0]) circuit.reset(qreg_q[1]) circuit.x(qreg_q[0]) circuit.x(qreg_q[1]) circuit.h(qreg_q[0]) circuit.h(qreg_q[1]) circuit.h(qreg_q[0]) circuit.measure(qreg_q[0], creg_c[0]) # @columns [0,0,1,1,2,2,3,4]
f1 (balanced)
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit from numpy import pi qreg_q = QuantumRegister(2, 'q') creg_c = ClassicalRegister(1, 'c') circuit = QuantumCircuit(qreg_q, creg_c) circuit.reset(qreg_q[0]) circuit.reset(qreg_q[1]) circuit.x(qreg_q[0]) circuit.x(qreg_q[1]) circuit.h(qreg_q[0]) circuit.h(qreg_q[1]) circuit.cx(qreg_q[0], qreg_q[1]) circuit.h(qreg_q[0]) circuit.measure(qreg_q[0], creg_c[0]) # @columns [0,0,1,1,2,2,3,4,5]
f2 (balanced)
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit from numpy import pi qreg_q = QuantumRegister(2, 'q') creg_c = ClassicalRegister(1, 'c') circuit = QuantumCircuit(qreg_q, creg_c) circuit.reset(qreg_q[0]) circuit.reset(qreg_q[1]) circuit.x(qreg_q[0]) circuit.x(qreg_q[1]) circuit.h(qreg_q[0]) circuit.h(qreg_q[1]) circuit.x(qreg_q[1]) circuit.cx(qreg_q[0], qreg_q[1]) circuit.h(qreg_q[0]) circuit.measure(qreg_q[0], creg_c[0]) # @columns [0,0,1,1,2,2,3,4,5,6]
f3 (balanced)
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit from numpy import pi qreg_q = QuantumRegister(2, 'q') creg_c = ClassicalRegister(1, 'c') circuit = QuantumCircuit(qreg_q, creg_c) circuit.reset(qreg_q[0]) circuit.reset(qreg_q[1]) circuit.x(qreg_q[0]) circuit.x(qreg_q[1]) circuit.h(qreg_q[0]) circuit.h(qreg_q[1]) circuit.x(qreg_q[1]) circuit.h(qreg_q[0]) circuit.measure(qreg_q[0], creg_c[0]) # @columns [0,0,1,1,2,2,3,4,5]