Quantum Computing

The Deutsch-Jozsa Algorithm

1985. David Deutsch publishes 'Quantum theory, the Church-Turing principle and the universal quantum computer'. The first algorithm demonstrating that a quantum computer can solve a problem faster than any classical machine. One oracle query instead of $2^{n-1}+1$. At $n=100$: a factor of $6 \times 10^{29}$ - more than the number of atoms in the observable universe.

IBM Quantum Network: D-J is used as a benchmark for NISQ devices - verifying the quality of H gates and oracle implementations on real hardware
Google Sycamore: the quantum supremacy demonstration (2019) uses the same superposition and interference principles in random circuit sampling
Shor's algorithm (integer factorization): uses the same building blocks - input superposition via H + oracle + inverse QFT; D-J is a simplified model of this idea
QML (Quantum Machine Learning): variational quantum circuits use H gates for feature encoding - the same input-space superposition concept as in D-J

Deutsch's algorithm: 1 qubit, 2 queries vs 1

**1985. David Deutsch publishes 'Quantum theory, the Church-Turing principle and the universal quantum computer'. The first algorithm proving a quantum computer can solve a problem faster than any classical machine.** The task: given a function $f: \{0,1\} \to \{0,1\}$, determine whether it is constant ($f(0)=f(1)$) or balanced ($f(0) \neq f(1)$). There are four possible functions total - two constant, two balanced. Classical minimum: two queries. Deutsch's algorithm: one.

**The trick:** feed the oracle the state $|+\rangle|-\rangle = \frac{|0\rangle+|1\rangle}{\sqrt{2}} \otimes \frac{|0\rangle-|1\rangle}{\sqrt{2}}$. The oracle $U_f$ acts on both simultaneously. If constant - the first qubit after $H$ collapses to $|0\rangle$. If balanced - to $|1\rangle$. One measurement, one query.

In Deutsch's algorithm, the ancilla qubit starts in $|1\rangle$ and passes through $H$, becoming $|-\rangle$. What role does this $|-\rangle$ state play?

Generalization to n qubits: exponential advantage

**A classical deterministic algorithm needs $2^{n-1}+1$ queries in the worst case. The quantum algorithm needs one. At $n=100$: a factor of $6 \times 10^{29}$ difference.** Deutsch-Jozsa generalizes the problem: given $f: \{0,1\}^n \to \{0,1\}$ with a promise - either constant (all outputs identical) or balanced (exactly half the inputs map to 0, half to 1) - determine which. No middle ground; the promise is guaranteed.

**Deutsch-Jozsa algorithm steps:** 1. Prepare $|0\rangle^{\otimes n}|1\rangle$ 2. Apply $H^{\otimes n}$ to the first $n$ qubits and $H$ to the ancilla: superposition over all $2^n$ inputs simultaneously 3. Apply oracle $U_f$: phase kickback writes $(-1)^{f(x)}$ into the amplitudes 4. Apply $H^{\otimes n}$ again to the first $n$ qubits 5. Measure: all zeros - constant, any nonzero bit - balanced

In Deutsch-Jozsa with $n=3$, the measurement result is $|010\rangle$. What does this indicate?

Quantum oracle and phase kickback

**The oracle is a black box implementing function $f$.** In the quantum setting, the oracle is a unitary matrix $U_f$ defined as $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$, where $\oplus$ is XOR. This is reversible: applying $U_f$ twice returns the original state ($U_f^2 = I$). Writing the classical output XOR into the ancilla - rather than overwriting the input - is the only way to implement an arbitrary function unitarily.

**Phase kickback:** if the ancilla is $|-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$, then $U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$. The phase $(-1)^{f(x)}$ transfers from the ancilla to the input register. The ancilla is unchanged. This enables a single call to $U_f$ to encode information about all $2^n$ inputs through phase rather than amplitude.

**Compiling a classical function into a quantum oracle:** any classical computation can be translated into a reversible circuit using Toffoli gates (CCX), then embedded into a quantum circuit. The cost is proportional to the classical circuit complexity. The oracle is not free: building it already requires knowing the function.

The oracle $U_f$ is applied to state $|x\rangle|-\rangle$. What is the result when $f(x) = 1$?

What Deutsch-Jozsa actually proves: the oracle model

**Deutsch-Jozsa is practically useless - nobody asks 'constant or balanced function'. But the algorithm did something fundamental: it proved a principle.** The speedup exists not for arbitrary problems, but in the oracle model - where complexity is measured by the number of queries to a black box. In this model, D-J achieves an exponential speedup over deterministic classical algorithms. This is exact, mathematically rigorous - not an approximation, not a heuristic.

**Genealogy of quantum algorithms descending from D-J:** - Bernstein-Vazirani (1993): find hidden string $s$ in $f(x) = s \cdot x \bmod 2$ - one quantum query vs $n$ classical - Simon (1994): find a hidden period - exponential speedup, direct precursor to Shor's algorithm - Shor (1994): integer factorization - uses quantum Fourier transform (QFT) as a generalization of oracle parallelism - Grover (1996): unstructured search in $O(\sqrt{N})$ instead of $O(N)$

**QML and oracle assumptions:** many Quantum ML speedup claims assume oracle access to data - $O(1)$ or $O(\log N)$ per element read. On real data, loading alone costs $O(N)$ (the QRAM problem). Quantum speedup in QML often exists only under this unrealistic assumption. D-J's lesson applies directly: oracle model speedups do not automatically transfer to concrete input models.

Quantum parallelism means the quantum computer evaluates all $2^n$ inputs simultaneously and retrieves all outputs at once

The quantum computer creates a superposition of all inputs and makes one oracle call, but measurement yields a single classical result. The algorithm uses interference - constructive for the desired answer, destructive for all others. Without interference, superposition is useless.

After the oracle call, the state $\sum_x (-1)^{f(x)}|x\rangle$ encodes information about all inputs simultaneously - but that information cannot be fully extracted. The algorithm deliberately constructs interference so that exactly the needed global property (constant vs balanced) can be read out deterministically from a single measurement. This is phase engineering, not parallelism.

D-J gives an exponential speedup over deterministic classical algorithms. Why does this not imply quantum computers are exponentially faster at all problems?

Deutsch-Jozsa: key takeaways

D-J determines 'constant or balanced function' in one oracle query; a deterministic classical algorithm needs $2^{n-1}+1$ in the worst case
Mechanism: prepare superposition $H^{\otimes n}|0\rangle^n$, phase kickback via ancilla $|-\rangle$, second $H^{\otimes n}$, measure - $|0\rangle^n$ means constant, anything else means balanced
Phase kickback is the core trick: ancilla $|-\rangle$ converts the XOR oracle into a phase oracle $(-1)^{f(x)}$ that interference can detect globally in one step
D-J proved the principle of quantum speedup; practically useless on its own, but laid the mathematical foundation for Bernstein-Vazirani, Simon, and Shor

Вопросы для размышления

The D-J algorithm works only with a promise: the function is either strictly constant or strictly balanced. What happens if the promise is violated - for example, 60% zeros and 40% ones? Is the measurement result meaningful?
Phase kickback transfers information about the function from the ancilla into the phase of the input register. Why can't that information be extracted by simply measuring the ancilla after the oracle?
D-J gives an exponential speedup over deterministic classical algorithms, but a randomized classical algorithm solves the task in 2 queries with 75% confidence. What does this say about the practical value of exponential quantum speedups?

Связанные уроки

qc-04 — H gates, phases, measurement - the building blocks used throughout this algorithm
qc-06 — Grover's algorithm reuses the same techniques: input superposition, interference, single measurement
alg-01-big-o — Query complexity is the oracle-model analog of time complexity
crypto-05-information-theory — Information-theoretic lower bounds explain why classical algorithms need exponentially many queries
alg-10-binary-search