The quantum advantage

Published on Sep 6, 2026 in Quantum Computing

As promised (after a break of a few months from creating content), here is an article presenting a quantum circuit that does more than just rotate qubits but which produces a real deterministic result.

If you missed my series on quantum computing, I recommend starting at the beginning with:

The simplest quantum algorithm, which provides a solution to a non-quantum problem, is the Deutsch’s algorithm. This algorithm makes it possible to determine whether a boolean function with one input and one output is constant or balanced. If the function is constant (output always 0 or always 1), the algorithm returns 0. If the function is balanced (output 0 half the time and 1 the other half), the algorithm returns 1.

To implement this algorithm:

We need a 2-qubit circuit and a classical bit to measure qubit 0 at the output.
Initialize the qubits to the states |0⟩ and |1⟩.
Superposition: Apply a Hadamard gate to each qubit.
Oracle: Apply the quantum function that encodes the operation via the phase kickback phenomenon (I.E. the effect of a controlled operation modifies the phase of the control qubit rather than that of the target qubit).
Interference: Apply a Hadamard gate to the first qubit again.
Measurement: Measure the first qubit. If it is 0, the function is constant. If it is 1, it is balanced.

python

from qiskit import QuantumCircuit, transpile
from qiskit_aer import Aer

def deutsch(oracle: QuantumCircuit):
    # The oracle must implement U_f: |x>|y> -> |x>|y xor f(x)> on 2 qubits.
    # Qubit 0 is the input x, qubit 1 is the work/target qubit y.
    qc = QuantumCircuit(2, 1) # One classical bit is enough: we only read qubit 0.
    # Initialize the state to |0>|1>.
    qc.x(1)
    # Create superposition on both qubits.
    # Putting y in |-> = (|0>-|1>)/sqrt(2) enables phase kickback of f(x) onto x.
    qc.h(0); qc.h(1)
    # Apply the oracle once, then interfere x with a final Hadamard.
    qc.append(oracle.to_gate(), [0,1])
    qc.h(0)
    # Measure only x:
    # - result 0 => f is constant
    # - result 1 => f is balanced
    qc.measure(0, 0)
    sim = Aer.get_backend("aer_simulator")
    tqc = transpile(qc, sim)
    job = sim.run(tqc, shots=1000)
    counts = job.result().get_counts()
    print(qc.draw())
    return counts

# Oracle examples
# 1) Constant oracle: f(x)=0 -> identity on target
oracle_const0 = QuantumCircuit(2)
# 2) Constant oracle: f(x)=1 -> flip target
oracle_const1 = QuantumCircuit(2)
oracle_const1.x(1)
# 3) Balanced oracle: f(x)=x -> CNOT (target ^= control)
oracle_bal_x = QuantumCircuit(2)
oracle_bal_x.cx(0,1)
# 4) Balanced oracle: f(x)=1^x (NOT x) -> CNOT then X on target
oracle_bal_notx = QuantumCircuit(2)
oracle_bal_notx.cx(0,1)
oracle_bal_notx.x(1)

# Test each oracle with Deutsch's algorithm.
print("const0:", deutsch(oracle_const0))
print("const1:", deutsch(oracle_const1))
print("balanced x:", deutsch(oracle_bal_x))
print("balanced not x:", deutsch(oracle_bal_notx))

The program runs 1,000 iterations just for demonstration purposes. However, as you can see, the result is the same for every iteration.

We certainly agree, the problem solved by the Deutsch algorithm is nothing extraordinary. However, solving the problem in the classical way requires two iterations to test the different inputs, whereas Deutsch’s algorithm allows it to be solved in just one thanks to the superposition of qubits.

You might say that this represents a very modest quantum advantage. However, the Deutsch-Jozsa algorithm proposes a solution for the generalized problem to n inputs. The algorithmic complexity is exponential. It takes 2^(n-1) + 1 iterations (half the possible inputs plus one) to solve the problem using the classical approach. And the Deutsch-Jozsa algorithm, running on an (n + 1)-qubit computer, is capable of solving it in a single iteration.

Let’s assume that n = 100 and that we are capable of performing one million iterations per second on a conventional computer. With 2^99 + 1 iterations, it would take 20,098,468 billion years to solve the problem, whereas a 101-qubit quantum computer can solve the same problem in a single iteration.

The problem is that building a quantum computer is very complicated, because quantum states are fragile and highly sensitive to quantum noise and quantum decoherence. Due to the mechanisms required for error correction, many physical qubits are needed to obtain a few logical qubits.

This is an area where improvements are being made. In 2026, the company QuEra Computing announced a quantum computer with 96 logical qubits from 448 physical qubits. It is a technical feat, but it is far from the millions of qubits needed to run Shor’s algorithm on RSA keys (Shor’s algorithm is a quantum algorithm for factoring an integer into prime factors).

Don’t miss my upcoming posts — hit the follow button on my LinkedIn profile