Chapter 12: The Deutsch-Jozsa and Bernstein-Vazirani Algorithms — Simple Problems, Exponential Speedup, and the First Taste of Quantum Advantage

"With one query, the quantum computer learns what a classical computer would need exponentially many queries to discover. This is not a trick — it is a fundamental consequence of quantum mechanics."

Learning Objectives

After completing this chapter, you will be able to:

• State the Deutsch-Jozsa problem precisely and explain why it is hard classically
• Derive the Deutsch-Jozsa algorithm step by step, including the $n$-qubit generalization
• Prove the exponential separation between quantum and classical query complexity
• Explain the Bernstein-Vazirani problem and its relationship to the Deutsch-Jozsa problem
• Implement both algorithms in Qiskit with arbitrary oracles
• Construct oracles for constant, balanced, and hidden-string functions
• Analyze the role of the Hadamard transform as a Fourier transform over $\mathbb{Z}_2^n$
• Understand the inner product structure that makes Bernstein-Vazirani work
• Evaluate the practical significance and limitations of these algorithms
• Distinguish between promise-problem speedups and general-problem speedups

12.1 The Deutsch-Jozsa Problem: Setting the Stage

In 1992, David Deutsch and Richard Jozsa generalized Deutsch's 1-qubit algorithm to $n$ qubits, establishing the first example of an exponential quantum speedup. The problem is deliberately artificial — but it demonstrates a principle that recurs throughout quantum algorithm design.

The Deutsch-Jozsa Problem: You are given a black-box function $f: \{0,1\}^n \to \{0,1\}$ with the promise that $f$ is either:

• Constant: $f(x) = 0$ for all $x$, or $f(x) = 1$ for all $x$.
• Balanced: $f(x) = 0$ for exactly half the inputs and $f(x) = 1$ for the other half.

Your task: determine whether $f$ is constant or balanced.

Classical query complexity: In the worst case, a deterministic classical algorithm must query $f$ on $2^{n-1} + 1$ inputs. Why? Suppose you query $2^{n-1}$ inputs and they all return 0. The function could still be balanced (the remaining $2^{n-1}$ inputs all return 1) or constant (all inputs return 0). You need one more query to distinguish these cases.

Even a randomized classical algorithm with bounded error requires $\Omega(1)$ queries — but the deterministic quantum algorithm solves it with exactly 1 query, regardless of $n$.

Common Misconception: "The Deutsch-Jozsa problem proves quantum computers are exponentially faster than classical computers"

This is misleading for two reasons. First, the Deutsch-Jozsa problem is a promise problem — the algorithm only works under the promise that $f$ is either constant or balanced. If $f$ is neither, the algorithm may give an arbitrary answer. Second, a randomized classical algorithm can solve Deutsch-Jozsa with high probability using only $O(1)$ queries (just pick a few random inputs and check if all outputs are the same). The exponential separation is only between quantum and deterministic classical algorithms. The practical significance of Deutsch-Jozsa is conceptual, not practical: it shows that quantum algorithms can extract global properties of a function using exponentially fewer queries than deterministic classical algorithms.

Historical Context: The Deutsch-Jozsa algorithm was the first demonstration of an exponential quantum speedup, even if for an artificial problem. It appeared at a time (early 1990s) when quantum computing was primarily a theoretical curiosity. The significance was not in solving a practical problem, but in proving that exponential quantum speedups exist in principle. This paved the way for Shor's algorithm (1994), which showed an exponential speedup for the practically important problem of integer factorization.

12.1.1 Why the Promise Matters

The promise that $f$ is either constant or balanced is essential. Without it, the Deutsch-Jozsa algorithm fails. Consider a function that returns 0 on 75% of inputs and 1 on 25%. The algorithm would still output "constant" or "balanced" based on the measurement, but neither answer is correct.

Formally, the Deutsch-Jozsa algorithm solves a promise problem: it is only required to give the correct answer when the promise is satisfied. The quantum advantage comes from the fact that the promise (constant or balanced) creates a very specific structure in the function's phase pattern $(-1)^{f(x)}$, which the Hadamard transform can detect with a single query.

What happens if we run the algorithm on a non-promise function? Suppose $f(x) = 1$ for a fraction $p$ of the $N = 2^n$ inputs. The amplitude of the $|0\rangle^{\otimes n}$ measurement outcome is:

$$\alpha_{0^n} = \frac{1}{2^n} \sum_x (-1)^{f(x)} = \frac{1}{2^n} \left((1-p) \cdot 2^n + p \cdot 2^n \cdot (-1)\right) = 1 - 2p$$

The probability of measuring $|0\rangle^{\otimes n}$ (which would indicate "constant") is:

$$P(|0\rangle^{\otimes n}) = |1 - 2p|^2$$

• If $f$ is constant ($p = 0$ or $p = 1$): $P = 1$ (always measures $|0\rangle^{\otimes n}$).
• If $f$ is balanced ($p = 1/2$): $P = 0$ (never measures $|0\rangle^{\otimes n}$).
• If $p = 1/4$: $P = |1/2|^2 = 1/4$.
• If $p = 3/4$: $P = |1/2|^2 = 1/4$.

So for functions that are "close to constant" ($p$ near 0 or 1), the algorithm is likely to output "constant," and for functions "close to balanced" ($p$ near 1/2), it's likely to output "balanced," but the answer is not reliable.

12.1.2 The Classical Lower Bound: A Careful Proof

Theorem. Any deterministic classical algorithm for the Deutsch-Jozsa problem requires at least $2^{n-1} + 1$ queries in the worst case.

Proof. Consider an adversary that answers queries adaptively. The algorithm queries the oracle on inputs $x_1, x_2, \ldots, x_k$ and receives answers $f(x_1), f(x_2), \ldots, f(x_k)$. After $k$ queries, the algorithm's state of knowledge is:

• If all answers are the same (all 0 or all 1), the function could still be constant or balanced.
• The adversary can always choose a constant function or a balanced function consistent with all answers given so far, as long as $k < 2^{n-1} + 1$.

Specifically, after $k \leq 2^{n-1}$ queries that all return 0, the adversary can still define: - A constant function $f \equiv 0$ (consistent with all answers). - A balanced function $f(x) = 0$ for all queried $x$ and $f(x) = 1$ for all unqueried $x$ (also consistent).

These two functions cannot be distinguished by any algorithm that has made only $2^{n-1}$ queries. Only after $2^{n-1} + 1$ queries can the algorithm be certain.

For a randomized algorithm with error probability $\epsilon$, the expected number of queries is $O(1/\epsilon)$: just pick a few random inputs and check. If any two inputs give different values, $f$ is balanced. The probability that $k$ random inputs all give the same value when $f$ is balanced is at most $2^{1-k}$. So with $k = O(\log(1/\epsilon))$ queries, a randomized algorithm achieves error $\epsilon$.

This illustrates an important point: the exponential gap is between quantum and deterministic classical, not between quantum and randomized classical. The real power of the Deutsch-Jozsa algorithm is conceptual — it shows that quantum computers can extract global structural information (constant vs. balanced) in a single query.

12.2 The Deutsch-Jozsa Algorithm: Full Derivation

The circuit for $n$ qubits:

q_0: |0> ---[H]---+---[U_f]---+---[H]---[Measure]
                     |           |
q_1: |0> ---[H]---+---[U_f]---+---[H]---[Measure]
                     |           |
...                 |           |
q_{n-1}: |0> -[H]--+---[U_f]---+---[H]---[Measure]
                     |           
q_n: |1> ---[H]----+---[U_f]---------------
                    input       output

We have $n$ qubits for the input register and 1 qubit for the output register. The output qubit is initialized to $|1\rangle$.

Step 1 — Initial state: $$|\psi_0\rangle = |0\rangle^{\otimes n} \otimes |1\rangle$$

Step 2 — Apply Hadamard to all $n+1$ qubits: $$|\psi_1\rangle = H^{\otimes n}|0\rangle^{\otimes n} \otimes H|1\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle \otimes |-\rangle$$

where $|-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$.

This step creates the uniform superposition over all $2^n$ inputs. Each input $|x\rangle$ appears with equal amplitude $\frac{1}{\sqrt{2^n}}$, and the output qubit is in the $|-\rangle$ state, ready for phase kickback.

Step 3 — Apply the oracle $U_f$. Using phase kickback (Section 11.10):

$$|\psi_2\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} (-1)^{f(x)} |x\rangle \otimes |-\rangle$$

The output qubit factors out and is never used again. The input register now holds a superposition where each basis state $|x\rangle$ has amplitude $\frac{(-1)^{f(x)}}{\sqrt{2^n}}$.

Let us pause to understand what has happened. The oracle has encoded the entire function $f$ into a phase pattern. If we could somehow "read" all the phases, we would know $f(x)$ for every input. But we can't — measurement gives us one random $x$. The key insight is that we don't need to know $f(x)$ for every $x$ individually; we only need to know whether $f$ is constant or balanced. This global property is encoded in the sum of the phases, which the Hadamard transform will extract.

Step 4 — Apply $H^{\otimes n}$ to the input register. This is the crucial interference step. Recall the action of the Hadamard transform on a basis state:

$$H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle$$

where $x \cdot y = \sum_{i=1}^n x_i y_i \pmod{2}$ is the bitwise inner product.

Applying this to our superposition:

$$|\psi_3\rangle = H^{\otimes n} \left( \frac{1}{\sqrt{2^n}} \sum_{x} (-1)^{f(x)} |x\rangle \right) \otimes |-\rangle$$

$$= \frac{1}{2^n} \sum_{x} \sum_{y} (-1)^{f(x) + x \cdot y} |y\rangle \otimes |-\rangle$$

$$= \frac{1}{2^n} \sum_{y} \left( \sum_{x} (-1)^{f(x) + x \cdot y} \right) |y\rangle \otimes |-\rangle$$

The amplitude of each output state $|y\rangle$ is a sum over all $2^n$ inputs, weighted by the phase pattern $(-1)^{f(x) + x \cdot y}$. Whether the amplitude is large or small depends on how the phases align — this is quantum interference.

Step 5 — Measure the input register. The probability of measuring $|y\rangle = |0\rangle^{\otimes n}$ is:

$$P(|0\rangle^{\otimes n}) = \left| \frac{1}{2^n} \sum_{x} (-1)^{f(x)} \right|^2$$

Now we analyze the two cases:

• If $f$ is constant: $(-1)^{f(x)} = +1$ for all $x$ (if $f \equiv 0$) or $-1$ for all $x$ (if $f \equiv 1$). In either case, all terms have the same sign:

$$\left| \frac{1}{2^n} \sum_{x} (-1)^{f(x)} \right|^2 = \left| \frac{1}{2^n} \cdot (\pm 2^n) \right|^2 = 1$$

We measure $|0\rangle^{\otimes n}$ with probability 1.

• If $f$ is balanced: Exactly half the inputs give $f(x) = 0$ and half give $f(x) = 1$. The sum $\sum_x (-1)^{f(x)}$ has $2^{n-1}$ terms of $+1$ and $2^{n-1}$ terms of $-1$, so:

$$\sum_{x} (-1)^{f(x)} = 2^{n-1}(+1) + 2^{n-1}(-1) = 0$$

$$P(|0\rangle^{\otimes n}) = 0$$

We never measure $|0\rangle^{\otimes n}$. Any other result indicates a balanced function.

Conclusion: One query to $U_f$, followed by $O(n)$ Hadamard gates, determines with certainty whether $f$ is constant or balanced. The classical algorithm requires $O(2^n)$ queries.

Why This Matters: The Deutsch-Jozsa algorithm works because of a specific algebraic property: for constant functions, the sum $\sum_x (-1)^{f(x)}$ is $+2^n$ or $-2^n$, while for balanced functions, it is exactly 0. The Hadamard transform converts this sum into a measurable quantity. This is a template that recurs throughout quantum algorithm design: encode a global property into a phase pattern, then use interference to extract it.

12.2.1 Detailed Worked Example: Deutsch-Jozsa with n=2

Let us trace through the Deutsch-Jozsa algorithm for $n = 2$ with two different oracles.

Oracle 1: Constant function $f(x) = 0$

Step 1: $|\psi_0\rangle = |00\rangle|1\rangle$

Step 2: After Hadamard:

$$|\psi_1\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle) \otimes |-\rangle$$

Step 3: After oracle (constant-0, no phase changes):

$$|\psi_2\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle) \otimes |-\rangle$$

Step 4: After $H^{\otimes 2}$ on input register:

$$H^{\otimes 2} \cdot \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle) = H^{\otimes 2} \cdot H^{\otimes 2}|00\rangle = |00\rangle$$

(using $H^{\otimes 2} H^{\otimes 2} = I$, since all amplitudes have the same sign).

Step 5: Measurement gives $|00\rangle$ with probability 1. Conclusion: constant. Correct.

Oracle 2: Balanced function $f(x) = x_1$ (first bit)

The truth table is: $f(00) = 0, f(01) = 0, f(10) = 1, f(11) = 1$ (wait, actually $f(x) = x_1$ means the first bit, so $f(00) = 0, f(10) = 1$, etc.)

Let me be more careful. For $x = (x_1, x_2)$ with $x_1$ the most significant bit: - $f(00) = 0, f(01) = 0, f(10) = 1, f(11) = 1$

Wait, that's only balanced if we're using $x_1$ as the first bit. Let me use $f(x) = x_1$ where $x_1$ is the most significant bit. Then: - $f(00) = 0, f(01) = 0, f(10) = 1, f(11) = 1$

This gives 2 zeros and 2 ones — balanced.

Step 3: After oracle:

$$|\psi_2\rangle = \frac{1}{2}((+1)|00\rangle + (+1)|01\rangle + (-1)|10\rangle + (-1)|11\rangle) \otimes |-\rangle$$

Step 4: Apply $H^{\otimes 2}$:

For each basis state $|y\rangle$, compute $\beta_y = \frac{1}{4} \sum_x (-1)^{f(x) + x \cdot y}$:

$\beta_{00} = \frac{1}{4}(1 + 1 - 1 - 1) = 0$

$\beta_{01} = \frac{1}{4}(1 + (-1) - 1 + 1)$...

Let me be more careful. $x \cdot y$ is the inner product mod 2.

$x \cdot 00 = 0$ for all $x$: $\beta_{00} = \frac{1}{4}(1 + 1 - 1 - 1) = 0$

$x \cdot 01 = x_2$: $\beta_{01} = \frac{1}{4}((-1)^{0+0} + (-1)^{0+1} + (-1)^{1+0} + (-1)^{1+1})$ $= \frac{1}{4}(1 \cdot 1 + 1 \cdot 1 + (-1) \cdot 1 + (-1) \cdot 1)$

Hmm, let me use the direct formula. We need:

$$\beta_y = \frac{1}{2^n} \sum_x (-1)^{f(x)} (-1)^{x \cdot y}$$

For $y = 00$: $\sum_x (-1)^{f(x)} = 1 + 1 - 1 - 1 = 0$, so $\beta_{00} = 0$.

This confirms: the probability of measuring $|00\rangle$ is 0, indicating a balanced function. Any other outcome indicates balanced.

12.3 Oracle Construction for Deutsch-Jozsa

To implement the Deutsch-Jozsa algorithm, we need to construct oracles for specific functions. The oracle $U_f$ must act as:

$$U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$$

Constant-0 oracle: $U_f = I$ (do nothing). This is the simplest possible oracle.

Constant-1 oracle: Apply $X$ to the output qubit: $U_f = I^{\otimes n} \otimes X$. This flips the output regardless of the input.

Balanced oracles: We need $f(x)$ to be 0 on exactly half the inputs. Several natural constructions:

1. First-bit oracle: $f(x) = x_0$ (the first bit of $x$). Implemented with a single CNOT from qubit 0 to the output.

2. Parity oracle: $f(x) = x_0 \oplus x_1 \oplus \cdots \oplus x_{n-1}$ (XOR of all bits). Implemented with CNOTs from each input qubit to the output.

3. Inner product oracle: $f(x) = s \cdot x$ for some fixed string $s \in \{0,1\}^n$. This is the Bernstein-Vazirani oracle (Section 12.5).

ASCII Circuit — Balanced Oracle $f(x) = x_0 \oplus x_1$:

q_0: ---[●]---------------
         |
q_1: ---[●]---------------
         |
q_2: ---+---+--- (unused)
         |
q_out: -[⊕]---------------

This requires two CNOT gates from $q_0$ and $q_1$ to the output qubit. Each CNOT toggles the output when its control is $|1\rangle$, implementing XOR.

ASCII Circuit — Constant-0 Oracle:

q_0: --------------------

q_1: --------------------

q_out: -------------------
       (identity — no gates)

ASCII Circuit — Constant-1 Oracle:

q_0: --------------------

q_1: --------------------

q_out: ----[X]------------
       (flip output regardless)

12.3.1 Phase Oracle Construction

For algorithms that use phase kickback, we can also implement the oracle directly as a phase oracle:

$$U_f^{\text{phase}}|x\rangle = (-1)^{f(x)}|x\rangle$$

This is a diagonal unitary with entries $\pm 1$ on the diagonal. For small $n$, we can construct it by applying multi-controlled-Z gates:

• For each $x$ where $f(x) = 1$, apply a multi-controlled-Z that flips the phase of $|x\rangle$ and leaves all other states unchanged.
• This requires $X$ gates to set up the control conditions, a multi-controlled-Z, and then $X$ gates to uncompute.

Example — Phase oracle for $f(x) = x_0$ on 2 qubits:

The function $f(00) = 0, f(01) = 0, f(10) = 1, f(11) = 1$ means we flip the phase of $|10\rangle$ and $|11\rangle$.

Since both marked states have $x_0 = 1$, we can implement this with a controlled-Z on qubit 0:

$$U_f^{\text{phase}} = I \otimes |0\rangle\langle 0| + Z \otimes |1\rangle\langle 1|$$

Wait, that's not quite right. Let me think again. We want $(-1)^{f(x)}|x\rangle$ where $f(x) = x_0$. So we flip the phase when $x_0 = 1$, regardless of $x_1$. This is simply a Z gate on qubit 0:

$$Z \otimes I = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -1 \end{pmatrix}$$

This flips the phase of $|10\rangle$ and $|11\rangle$ (the states where qubit 0 is $|1\rangle$). Much simpler than the bit-flip oracle!

The phase oracle and the bit-flip oracle (with ancilla in $|-\rangle$) are equivalent — they produce the same phase pattern on the input register.

12.4 Qiskit Implementation: Deutsch-Jozsa Algorithm

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
import numpy as np

def deutsch_jozsa_circuit(n_qubits, oracle_type='constant_0'):
    """
    Constructs the Deutsch-Jozsa circuit for n_qubits input register.
    oracle_type: 'constant_0', 'constant_1', 'balanced_parity', 'balanced_first_bit'
    """
    qr_input = QuantumRegister(n_qubits, 'input')
    qr_output = QuantumRegister(1, 'output')
    cr = ClassicalRegister(n_qubits, 'c')
    qc = QuantumCircuit(qr_input, qr_output, cr)

    # Step 1: Initialize output qubit to |1⟩
    qc.x(qr_output)

    # Step 2: Apply Hadamard to all qubits
    for i in range(n_qubits):
        qc.h(qr_input[i])
    qc.h(qr_output)

    # Step 3: Oracle
    if oracle_type == 'constant_0':
        pass
    elif oracle_type == 'constant_1':
        qc.x(qr_output)
    elif oracle_type == 'balanced_first_bit':
        qc.cx(qr_input[0], qr_output)
    elif oracle_type == 'balanced_parity':
        for i in range(n_qubits):
            qc.cx(qr_input[i], qr_output)
    elif oracle_type == 'balanced_majority':
        # f(x) = 1 if majority of bits are 1
        # Implemented via multi-controlled gates
        majority = n_qubits // 2 + 1
        # For simplicity, use a pattern: f(x) = x_0 AND x_1 (balanced for n>=2)
        qc.ccx(qr_input[0], qr_input[1], qr_output)

    # Step 4: Apply Hadamard to input register
    for i in range(n_qubits):
        qc.h(qr_input[i])

    # Step 5: Measure input register
    qc.measure(qr_input, cr)

    return qc

def run_deutsch_jozsa(n_qubits=3):
    """Run Deutsch-Jozsa for various oracles and verify results."""
    simulator = AerSimulator()

    test_cases = [
        ('constant_0', True),
        ('constant_1', True),
        ('balanced_first_bit', False),
        ('balanced_parity', False),
    ]

    print(f"Deutsch-Jozsa Algorithm (n={n_qubits}):\n")
    for oracle_type, is_constant in test_cases:
        qc = deutsch_jozsa_circuit(n_qubits, oracle_type)
        result = simulator.run(qc, shots=1024).result()
        counts = result.get_counts()

        all_zero_count = counts.get('0' * n_qubits, 0)
        if is_constant:
            success = (all_zero_count == 1024)
        else:
            success = (all_zero_count == 0)

        status = "PASS" if success else "FAIL"
        print(f"  {oracle_type:25s}: all-zero count = {all_zero_count:4d}/1024  [{status}]")

    return counts

run_deutsch_jozsa(n_qubits=3)

Expected output:

Deutsch-Jozsa Algorithm (n=3):

  constant_0              : all-zero count = 1024/1024  [PASS]
  constant_1              : all-zero count = 1024/1024  [PASS]
  balanced_first_bit      : all-zero count =    0/1024  [PASS]
  balanced_parity         : all-zero count =    0/1024  [PASS]

12.4.1 Qiskit: Verifying with Statevector Simulation

To see the interference explicitly, we can use the statevector simulator:

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector
import numpy as np

def deutsch_jozsa_statevector(n_qubits, oracle_type='balanced_parity'):
    """Trace the statevector through Deutsch-Jozsa step by step."""
    qr_input = list(range(n_qubits))
    qr_output = n_qubits

    qc = QuantumCircuit(n_qubits + 1)

    # Initialize
    qc.x(qr_output)
    state = Statevector(qc)
    print(f"After init:        {np.round(state, 3)}")

    # Hadamard on all
    for i in range(n_qubits + 1):
        qc.h(i)
    state = Statevector(qc)
    print(f"After H^⊗(n+1):   amplitude range [{np.min(np.abs(state)):.4f}, {np.max(np.abs(state)):.4f}]")

    # Oracle
    if oracle_type == 'balanced_parity':
        for i in range(n_qubits):
            qc.cx(i, qr_output)
    elif oracle_type == 'constant_0':
        pass

    state = Statevector(qc)
    print(f"After oracle:      amplitude range [{np.min(np.abs(state)):.4f}, {np.max(np.abs(state)):.4f}]")

    # Final Hadamard on input
    for i in range(n_qubits):
        qc.h(i)
    state = Statevector(qc)
    probs = np.abs(np.array(state)) ** 2
    print(f"After final H:     P(|0^n⟩) = {probs[0]:.6f}")

    # Show top probabilities
    print(f"  Top outcomes:")
    for idx in np.argsort(-probs)[:5]:
        binary = format(idx, f'0{n_qubits+1}b')
        print(f"    |{binary}⟩: {probs[idx]:.6f}")

deutsch_jozsa_statevector(3, 'balanced_parity')
print()
deutsch_jozsa_statevector(3, 'constant_0')

12.4.2 Qiskit: Arbitrary Oracle from Truth Table

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator

def build_oracle_from_truth_table(n_qubits, truth_table):
    """
    Build a Deutsch-Jozsa oracle from a truth table.
    truth_table: list of 0/1 values, truth_table[i] = f(i)
    """
    qr_input = QuantumRegister(n_qubits, 'input')
    qr_output = QuantumRegister(1, 'output')
    oracle = QuantumCircuit(qr_input, qr_output)

    for x, fx in enumerate(truth_table):
        if fx == 1:
            binary = format(x, f'0{n_qubits}b')
            for i, bit in enumerate(binary):
                if bit == '0':
                    oracle.x(qr_input[i])
            oracle.mcx(qr_input, qr_output)
            for i, bit in enumerate(binary):
                if bit == '0':
                    oracle.x(qr_input[i])

    return oracle

def deutsch_jozsa_with_oracle(n_qubits, oracle_circuit):
    """Run Deutsch-Jozsa with a custom oracle."""
    qr_input = QuantumRegister(n_qubits, 'input')
    qr_output = QuantumRegister(1, 'output')
    cr = ClassicalRegister(n_qubits, 'c')
    qc = QuantumCircuit(qr_input, qr_output, cr)

    qc.x(qr_output)
    for i in range(n_qubits):
        qc.h(qr_input[i])
    qc.h(qr_output)

    qc.compose(oracle_circuit, inplace=True)

    for i in range(n_qubits):
        qc.h(qr_input[i])

    qc.measure(qr_input, cr)
    return qc

# Example: n=3, balanced function with truth table [0,1,0,1,1,0,1,0]
truth_table_balanced = [0, 1, 0, 1, 1, 0, 1, 0]
oracle = build_oracle_from_truth_table(3, truth_table_balanced)
qc = deutsch_jozsa_with_oracle(3, oracle)

simulator = AerSimulator()
result = simulator.run(qc, shots=1024).result()
counts = result.get_counts()
all_zero = counts.get('000', 0)
print(f"Balanced oracle: all-zero count = {all_zero}/1024")
print(f"Result: {'CONSTANT' if all_zero == 1024 else 'BALANCED'}")
print(f"Full counts: {counts}")

12.5 The Bernstein-Vazirani Problem: Learning a Hidden String

In 1993, Ethan Bernstein and Umesh Vazirani designed a problem that sharpens the Deutsch-Jozsa result. The problem is:

Given: A function $f: \{0,1\}^n \to \{0,1\}$ defined by $f(x) = s \cdot x = \bigoplus_{i=1}^n s_i x_i$ (the bitwise inner product modulo 2), where $s \in \{0,1\}^n$ is a hidden string.

Task: Determine $s$.

Classical query complexity: A classical algorithm needs $n$ queries in the worst case. Each query $f(x)$ reveals one linear equation about $s$. You need $n$ linearly independent equations to determine $s$ uniquely. (You can do slightly better with a randomized algorithm, but still $\Omega(n)$ queries.)

To see this concretely, suppose $n = 3$ and $s = 101$. Each query gives us one linear equation: - Query $x = 100$: $f(100) = s \cdot 100 = s_1 = 1$ → we learn $s_1 = 1$ - Query $x = 010$: $f(010) = s \cdot 010 = s_2 = 0$ → we learn $s_2 = 0$ - Query $x = 001$: $f(001) = s \cdot 001 = s_3 = 1$ → we learn $s_3 = 1$

After 3 queries, we know $s = 101$. But with fewer than 3 queries, we cannot determine $s$ — there are always at least two strings consistent with the observations.

Quantum solution: The Bernstein-Vazirani algorithm determines $s$ with exactly 1 query, regardless of $n$.

Why This Matters: Unlike Deutsch-Jozsa, the Bernstein-Vazirani problem is not a promise problem — it asks for the value of a specific $n$-bit string, not just a binary classification. The speedup is from $n$ to 1, which is polynomial (not exponential), but it applies to a non-promise problem. This was the first demonstration of a quantum speedup for a concrete, non-promise problem.

12.6 The Bernstein-Vazirani Algorithm: Derivation

The circuit is identical to Deutsch-Jozsa, but the analysis reveals the hidden string.

Circuit:

q_0: |0> ---[H]---+---[U_f]---+---[H]---[Measure] → s_0
                     |           |
q_1: |0> ---[H]---+---[U_f]---+---[H]---[Measure] → s_1
                     |           |
...                 |           |
q_{n-1}: |0> -[H]--+---[U_f]---+---[H]---[Measure] → s_{n-1}
                     |           
q_n: |1> ---[H]----+---[U_f]---------------

Step 1–2: Same as Deutsch-Jozsa. After Hadamard gates:

$$|\psi_1\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle \otimes |-\rangle$$

Step 3 — Oracle with $f(x) = s \cdot x$. Using phase kickback:

$$|\psi_2\rangle = \frac{1}{\sqrt{2^n}} \sum_{x} (-1)^{s \cdot x} |x\rangle \otimes |-\rangle$$

This is the key step. The oracle has encoded the hidden string $s$ into a phase pattern: each basis state $|x\rangle$ has phase $(-1)^{s \cdot x}$, which depends on the inner product of $x$ with $s$. This phase pattern is a character of the group $\mathbb{Z}_2^n$ — a function $\chi_s(x) = (-1)^{s \cdot x}$ that is a group homomorphism from $\mathbb{Z}_2^n$ to $\{-1, +1\}$.

Step 4 — Apply $H^{\otimes n}$ to the input register:

$$|\psi_3\rangle = \frac{1}{2^n} \sum_{x} \sum_{y} (-1)^{s \cdot x + x \cdot y} |y\rangle \otimes |-\rangle$$

$$= \frac{1}{2^n} \sum_{y} \left( \sum_{x} (-1)^{x \cdot (s \oplus y)} \right) |y\rangle \otimes |-\rangle$$

Now we use a fundamental identity of the Hadamard transform:

$$\sum_{x \in \{0,1\}^n} (-1)^{x \cdot z} = \begin{cases} 2^n & \text{if } z = 0^{\otimes n} \\ 0 & \text{otherwise} \end{cases}$$

Proof: If $z = 0^{\otimes n}$, then $x \cdot z = 0$ for all $x$, and the sum is $2^n$. If $z \neq 0^{\otimes n}$, then for exactly half the $x$ values, $x \cdot z = 0$, and for the other half, $x \cdot z = 1$. The $+1$ and $-1$ terms cancel perfectly.

Detailed proof of the orthogonality relation: Let $z \neq 0^{\otimes n}$. Then there exists some bit position $i$ where $z_i = 1$. We can partition $\{0,1\}^n$ into pairs $(x, x \oplus e_i)$ where $e_i$ is the unit vector with a 1 in position $i$. For each such pair:

$$(-1)^{x \cdot z} + (-1)^{(x \oplus e_i) \cdot z} = (-1)^{x \cdot z}(1 + (-1)^{e_i \cdot z}) = (-1)^{x \cdot z}(1 + (-1)^{z_i}) = 0$$

since $z_i = 1$ implies $(-1)^{z_i} = -1$. Every pair contributes 0 to the sum, so the total sum is 0.

Applying this identity with $z = s \oplus y$:

$$\sum_{x} (-1)^{x \cdot (s \oplus y)} = \begin{cases} 2^n & \text{if } s \oplus y = 0^{\otimes n} \text{ (i.e., } y = s\text{)} \\ 0 & \text{otherwise} \end{cases}$$

Therefore:

$$|\psi_3\rangle = |s\rangle \otimes |-\rangle$$

Step 5 — Measure the input register. We obtain $s$ with probability 1. One query reveals the entire $n$-bit hidden string.

Try It Yourself: Trace through the Bernstein-Vazirani algorithm for $n = 3$ and $s = 101$. Compute the state after each step. Verify that the final measurement yields $|101\rangle$ with certainty.

12.6.1 Detailed Worked Example: Bernstein-Vazirani with n=3, s=101

Step 1: $|\psi_0\rangle = |000\rangle|1\rangle$

Step 2: After Hadamard:

$$|\psi_1\rangle = \frac{1}{\sqrt{8}}(|000\rangle + |001\rangle + |010\rangle + |011\rangle + |100\rangle + |101\rangle + |110\rangle + |111\rangle) \otimes |-\rangle$$

Step 3: After oracle with $f(x) = s \cdot x$ where $s = 101$:

Compute $s \cdot x$ for each $x$: - $s \cdot 000 = 0$, $s \cdot 001 = 1$, $s \cdot 010 = 0$, $s \cdot 011 = 1$ - $s \cdot 100 = 1$, $s \cdot 101 = 0$, $s \cdot 110 = 1$, $s \cdot 111 = 0$

Wait, let me recompute. $s = 101$, so $s_1 = 1, s_2 = 0, s_3 = 1$.

$s \cdot x = s_1 x_1 \oplus s_2 x_2 \oplus s_3 x_3 = x_1 \oplus x_3$

• $s \cdot 000 = 0 \oplus 0 = 0$
• $s \cdot 001 = 0 \oplus 1 = 1$
• $s \cdot 010 = 0 \oplus 0 = 0$
• $s \cdot 011 = 0 \oplus 1 = 1$
• $s \cdot 100 = 1 \oplus 0 = 1$
• $s \cdot 101 = 1 \oplus 1 = 0$
• $s \cdot 110 = 1 \oplus 0 = 1$
• $s \cdot 111 = 1 \oplus 1 = 0$

After phase kickback:

$$|\psi_2\rangle = \frac{1}{\sqrt{8}}(|000\rangle - |001\rangle + |010\rangle - |011\rangle - |100\rangle + |101\rangle - |110\rangle + |111\rangle) \otimes |-\rangle$$

Step 4: Apply $H^{\otimes 3}$. Using the orthogonality relation, only the term with $y = s = 101$ survives:

$$|\psi_3\rangle = |101\rangle \otimes |-\rangle$$

Step 5: Measurement yields $s = 101$ with probability 1.

12.7 Qiskit Implementation: Bernstein-Vazirani Algorithm

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
import numpy as np

def bernstein_vazirani_circuit(n_qubits, hidden_string):
    """
    Constructs the Bernstein-Vazirani circuit.
    hidden_string: binary string of length n_qubits (e.g., '10110')
    """
    qr_input = QuantumRegister(n_qubits, 'input')
    qr_output = QuantumRegister(1, 'output')
    cr = ClassicalRegister(n_qubits, 'c')
    qc = QuantumCircuit(qr_input, qr_output, cr)

    # Step 1: Initialize output to |1⟩
    qc.x(qr_output)

    # Step 2: Hadamard on all qubits
    for i in range(n_qubits):
        qc.h(qr_input[i])
    qc.h(qr_output)

    # Step 3: Oracle implementing f(x) = s · x
    # For each bit i where s_i = 1, apply CNOT from input[i] to output
    for i, bit in enumerate(hidden_string):
        if bit == '1':
            qc.cx(qr_input[i], qr_output)

    # Step 4: Hadamard on input register
    for i in range(n_qubits):
        qc.h(qr_input[i])

    # Step 5: Measure
    qc.measure(qr_input, cr)

    return qc

def run_bernstein_vazirani(n_qubits=5, trials=10):
    """Test Bernstein-Vazirani with random hidden strings."""
    simulator = AerSimulator()
    rng = np.random.default_rng(42)

    print(f"Bernstein-Vazirani Algorithm (n={n_qubits}):\n")
    successes = 0

    for trial in range(trials):
        # Generate random hidden string
        s = ''.join(str(rng.integers(2)) for _ in range(n_qubits))
        qc = bernstein_vazirani_circuit(n_qubits, s)
        result = simulator.run(qc, shots=1024).result()
        counts = result.get_counts()
        measured = max(counts, key=counts.get)

        success = (measured == s)
        successes += success
        status = "PASS" if success else "FAIL"
        print(f"  Trial {trial+1:2d}: hidden={s}, measured={measured} [{status}]")

    print(f"\n  Success rate: {successes}/{trials}")

run_bernstein_vazirani(n_qubits=5, trials=10)

Expected output:

Bernstein-Vazirani Algorithm (n=5):

  Trial  1: hidden=01101, measured=01101 [PASS]
  Trial  2: hidden=10011, measured=10011 [PASS]
  ...
  Success rate: 10/10

12.7.1 Qiskit: Bernstein-Vazirani with Large n

def bv_large_n():
    """Demonstrate Bernstein-Vazirani with increasingly large n."""
    simulator = AerSimulator()

    for n in [4, 8, 12, 16]:
        s = ''.join(['1' if i % 3 == 0 else '0' for i in range(n)])
        qc = bernstein_vazirani_circuit(n, s)
        result = simulator.run(qc, shots=100).result()
        counts = result.get_counts()
        measured = max(counts, key=counts.get)
        success_rate = counts.get(s, 0) / 100

        print(f"n={n:2d}: hidden={s}, measured={measured}, "
              f"success={success_rate:.2f}, "
              f"classical queries needed={n}")

bv_large_n()

Expected output:

n= 4: hidden=1001..., measured=1001..., success=1.00, classical queries needed=4
n= 8: hidden=10010010..., measured=10010010, success=1.00, classical queries needed=8
n=12: hidden=100100100100, measured=100100100100, success=1.00, classical queries needed=12
n=16: hidden=1001001001001001, measured=1001001001001001, success=1.00, classical queries needed=16

Notice that the quantum algorithm uses exactly 1 query regardless of $n$, while the classical algorithm needs $n$ queries.

12.8 The Hadamard Transform as a Fourier Transform Over $\mathbb{Z}_2^n$

There is a deeper mathematical structure at work. The Hadamard transform $H^{\otimes n}$ is precisely the Fourier transform over the group $\mathbb{Z}_2^n$.

For a function $g: \{0,1\}^n \to \mathbb{C}$, its Fourier transform $\hat{g}: \{0,1\}^n \to \mathbb{C}$ is:

$$\hat{g}(y) = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} (-1)^{x \cdot y} \, g(x)$$

The characters of the group $\mathbb{Z}_2^n$ are the functions $\chi_y(x) = (-1)^{x \cdot y}$. These are group homomorphisms from $\mathbb{Z}_2^n$ to $\{-1, +1\}$ (the multiplicative group of order 2).

Key properties of the characters: 1. Orthogonality: $\sum_{x \in \{0,1\}^n} \chi_y(x) \chi_{y'}(x) = 2^n \delta_{y,y'}$ 2. Completeness: $\sum_{y \in \{0,1\}^n} \chi_y(x) \chi_y(x') = 2^n \delta_{x,x'}$ 3. Product: $\chi_y(x) \chi_{y'}(x) = \chi_{y \oplus y'}(x)$ (characters multiply by XOR of their labels)

The Hadamard transform converts between the "position" representation (amplitudes in the computational basis) and the "frequency" representation (amplitudes in the Hadamard basis).

In the Deutsch-Jozsa algorithm: - The state after the oracle is $\sum_x (-1)^{f(x)}|x\rangle$ (up to normalization). - The Hadamard transform computes the Fourier transform of the function $g(x) = (-1)^{f(x)}$. - The zero-frequency component $\hat{g}(0)$ is proportional to $\sum_x (-1)^{f(x)}$, which is zero exactly when $f$ is balanced.

In the Bernstein-Vazirani algorithm: - The state after the oracle is $\sum_x (-1)^{s \cdot x}|x\rangle$. - This is already a character $\chi_s(x)$ in the position representation. - The Fourier transform of a character is a delta function: $\hat{\chi}_s(y) = \delta_{y,s}$. - Hence measurement yields $s$ with certainty.

This Fourier perspective unifies these algorithms and foreshadows the Quantum Fourier Transform (Chapter 14), which generalizes this idea to the cyclic group $\mathbb{Z}_N$.

12.8.1 The Fourier Structure of Bernstein-Vazirani

The Bernstein-Vazirani algorithm is particularly elegant from the Fourier perspective. The key identity is:

$$H^{\otimes n} \chi_s = \sqrt{2^n} |s\rangle$$

where $\chi_s = \sum_x (-1)^{s \cdot x} |x\rangle / \sqrt{2^n}$ is the character corresponding to $s$. This is exactly the quantum Fourier transform over $\mathbb{Z}_2^n$ applied to $\chi_s$, yielding the computational basis state $|s\rangle$.

In signal processing terms, $\chi_s$ is a "pure tone" at frequency $s$ in the $\mathbb{Z}_2^n$ domain. The Hadamard transform decomposes this tone into a single delta function at frequency $s$ — just as the classical Fourier transform of a pure sinusoid $e^{2\pi i s x / N}$ yields a delta function at frequency $s$.

The quantum advantage arises because the oracle creates the character $\chi_s$ with a single query (via phase kickback), and the Hadamard transform reads out the frequency $s$ in a single measurement. Classically, you would need $n$ queries to identify the frequency $s$ because you can only measure $\chi_s$ at individual points.

Recurring Theme — Quantum is Linear Algebra, Not Magic: The Bernstein-Vazirani algorithm is pure linear algebra. The oracle applies a linear transformation (a diagonal matrix with entries $(-1)^{s \cdot x}$), the Hadamard transform applies another linear transformation (the Fourier transform over $\mathbb{Z}_2^n$), and the composition of these two linear transformations maps $|0\rangle^{\otimes n}$ to $|s\rangle$. There is nothing "magical" happening — just the structure of the group characters being exploited by a clever choice of linear transformation.

12.9 Oracle Construction: A Systematic Approach

Constructing oracles is a practical skill. Here we present a systematic method for building an oracle $U_f$ for any Boolean function $f: \{0,1\}^n \to \{0,1\}$.

Method 1: CNOT cascade (for linear functions). If $f(x) = a \cdot x$ for some $a \in \{0,1\}^n$, the oracle is simply a CNOT from each qubit $i$ where $a_i = 1$ to the output qubit.

Example: f(x) = x₁ ⊕ x₃ (a = 101)

q₀: ----●----
       |
q₁: ----|----
       |
q₂: ----●----
       |
out: --[⊕]---

Method 2: Truth table synthesis. For small $n$, we can synthesize the oracle from the truth table using multi-controlled gates:

def build_oracle_from_truth_table(n_qubits, truth_table, qr_input, qr_output, qc):
    """
    Builds an oracle U_f from a truth table.
    truth_table: dict mapping binary strings to {0,1}
    """
    for x, fx in truth_table.items():
        if fx == 1:
            # Apply X to flip bits that are 0, so we target |11...1⟩
            for i, bit in enumerate(x):
                if bit == '0':
                    qc.x(qr_input[i])
            # Multi-controlled X on output
            qc.mcx(list(range(n_qubits)), qr_output)
            # Uncompute the X flips
            for i, bit in enumerate(x):
                if bit == '0':
                    qc.x(qr_input[i])

Method 3: Phase oracle (for algorithms using phase kickback). If we only need the phase-kickback version, we can implement the oracle directly as a diagonal unitary:

$$U_f^{\text{phase}}|x\rangle = (-1)^{f(x)}|x\rangle$$

This is implemented by applying a $Z$ gate (or multi-controlled-$Z$) to mark each $x$ where $f(x) = 1$.

Method 4: Computation-Uncomputation (for complex functions). For arbitrary Boolean functions, we can use the computation-uncomputation pattern:

1. Compute $f(x)$ into an ancilla qubit using standard gates.
2. Use the ancilla for phase kickback.
3. Uncompute $f(x)$ by running the computation circuit in reverse.

This is the most general method and works for any efficiently computable $f$.

q₀: ----[compute f]---[●]---[uncompute f]----
                        |
q₁: ----[compute f]---[●]---[uncompute f]----
                        |
anc: --|0⟩--[compute f]-[⊕]--[uncompute f]-|0⟩
                          |
phase: ---------------[Z]--------------------

The ancilla starts and ends in $|0\rangle$ (or $|-\rangle$ for phase kickback), so it is effectively "borrowed" and returned.

12.9.1 Oracle Complexity

The number of gates required to implement an oracle depends on the complexity of the function $f$:

• Linear functions ($f(x) = a \cdot x$): $O(n)$ CNOT gates.
• Quadratic functions ($f(x) = x_1 x_2 \oplus \cdots$): $O(n^2)$ gates using Toffoli gates.
• Arbitrary functions: Up to $O(2^n)$ multi-controlled gates in the worst case.

The oracle complexity is typically not counted in the query complexity of quantum algorithms, since the oracle is treated as a black box. However, for practical implementations, the oracle cost must be considered.

Recurring Theme — Noise is the Enemy: In practice, the oracle is often the most expensive part of a quantum algorithm in terms of gate count. A complex oracle can require many multi-controlled gates, each of which must be decomposed into elementary gates and is susceptible to noise. For near-term quantum computers, the oracle overhead can dominate the total circuit depth and render the algorithm impractical.

12.10 Complexity Analysis: Exponential Separation

Let us formalize the query complexity separation.

Theorem (Deutsch-Jozsa). The deterministic quantum query complexity of the Deutsch-Jozsa problem is 1. The deterministic classical query complexity is $2^{n-1} + 1$.

Proof (classical lower bound). Consider any deterministic classical algorithm that makes $k$ queries. The algorithm can be represented as a decision tree. An adversary can answer queries adaptively to force the algorithm to make many queries. Specifically, the adversary maintains the set of inputs consistent with all answers given so far. As long as this set contains both a constant function and a balanced function, the algorithm cannot output a definitive answer. Initially, all $2^{2^n}$ possible functions are consistent. After $k$ queries, if all answers have been 0, the constant-0 function is consistent, and any balanced function that is 0 on the queried inputs is also consistent — as long as $k \leq 2^{n-1}$. The adversary can therefore force $2^{n-1} + 1$ queries.

Theorem (Bernstein-Vazirani). The deterministic quantum query complexity of the Bernstein-Vazirani problem is 1. The deterministic classical query complexity is $n$.

Proof (classical lower bound). Each classical query $f(x) = s \cdot x$ reveals one linear equation $\sum_i s_i x_i = f(x) \pmod{2}$. To determine $s$ uniquely, we need $n$ linearly independent equations. With $k < n$ queries, the system is underdetermined, and at least two different values of $s$ are consistent with all answers.

12.10.1 Randomized Classical Complexity

For Deutsch-Jozsa, a randomized classical algorithm can solve the problem with bounded error using only 2 queries: 1. Query $f$ on a random input $x_1$. 2. Query $f$ on a random input $x_2$ (different from $x_1$). 3. If $f(x_1) \neq f(x_2)$, output "balanced." 4. If $f(x_1) = f(x_2)$, query more inputs until you find a different value or are confident the function is constant.

More precisely, if the function is balanced and we query $k$ random inputs, the probability that all outputs are the same is at most $2/2^k$. So with $k = O(\log(1/\epsilon))$ queries, we can achieve error probability $\epsilon$.

This means the exponential gap in Deutsch-Jozsa is between deterministic classical and quantum, not between randomized classical and quantum. The quantum advantage for Deutsch-Jozsa is in the setting of zero-error (exact) computation.

For Bernstein-Vazirani, even a randomized classical algorithm needs $\Omega(n)$ queries (specifically, $n$ queries are needed to uniquely determine $s$), so the quantum advantage is more robust — it holds against randomized classical algorithms as well.

12.10.2 Query Complexity Hierarchy

Let us place these results in the broader context of quantum query complexity:

Recurring Theme — Quantum Advantage is Problem-Specific: The speedup depends critically on the problem structure. Deutsch-Jozsa exploits the promise structure. Bernstein-Vazirani exploits the linearity of $f$. Grover's search works for any black-box function but only gives a quadratic speedup. Shor's algorithm exploits the periodic structure of modular exponentiation. There is no "universal" quantum speedup.

12.11 The Inner Product Structure and Its Significance

The Bernstein-Vazirani algorithm relies on a key algebraic identity: the inner product structure of $\mathbb{Z}_2^n$. Let us explore this in more depth.

12.11.1 The Orthogonality of Characters

The characters $\chi_s(x) = (-1)^{s \cdot x}$ satisfy the orthogonality relation:

$$\sum_{x \in \{0,1\}^n} \chi_s(x) \chi_{s'}(x) = \sum_x (-1)^{(s \oplus s') \cdot x} = 2^n \delta_{s,s'}$$

This means the characters form an orthonormal basis (after normalization) for the vector space of functions $f: \{0,1\}^n \to \mathbb{C}$. Any such function can be written as a linear combination of characters:

$$f(x) = \frac{1}{2^n} \sum_{s} \hat{f}(s) (-1)^{s \cdot x}$$

where $\hat{f}(s) = \sum_x f(x) (-1)^{s \cdot x}$ is the Fourier transform of $f$ over $\mathbb{Z}_2^n$.

12.11.2 Connection to the Quantum Fourier Transform

The Quantum Fourier Transform (QFT) over $\mathbb{Z}_N$ (Chapter 14) is a generalization of the Hadamard transform to arbitrary cyclic groups. The key identity:

$$\sum_{x=0}^{N-1} e^{2\pi i x(y-s)/N} = N \delta_{y,s}$$

generalizes the orthogonality relation $\sum_x (-1)^{x \cdot (s \oplus y)} = 2^n \delta_{s,y}$. The Hadamard transform is the QFT over $\mathbb{Z}_2^n$ (where $e^{2\pi i x \cdot y / 2} = (-1)^{x \cdot y}$), and the full QFT uses $e^{2\pi i / N}$ as the root of unity instead of $e^{2\pi i / 2} = -1$.

This connection explains why the same algorithmic pattern — oracle query followed by Fourier transform — appears in both Bernstein-Vazirani and Shor's algorithm. The only difference is the group over which the Fourier transform is computed.

12.12 Beyond Deutsch-Jozsa and Bernstein-Vazirani: Limitations and Generalizations

12.12.1 Limitations

The Deutsch-Jozsa and Bernstein-Vazirani algorithms demonstrate quantum speedups, but they have important limitations:

1. Deutsch-Jozsa is a promise problem. The algorithm only works under the promise that $f$ is constant or balanced. Without this promise, the algorithm may give misleading results.

2. Deutsch-Jozsa has no practical advantage over randomized classical algorithms. A randomized classical algorithm can solve Deutsch-Jozsa with high probability in $O(1)$ queries.

3. Bernstein-Vazirani is restricted to linear functions. The function must be of the form $f(x) = s \cdot x$. For more general functions, the algorithm doesn't apply directly.

4. The oracle must be a quantum oracle. The algorithm assumes access to a unitary $U_f$ that computes $f$ in superposition. If we only have a classical black box, the overhead of converting it to a quantum oracle may negate the speedup.

12.12.2 Generalizations

Several important generalizations of these algorithms exist:

Simon's Problem (1994): Given a function $f: \{0,1\}^n \to \{0,1\}^n$ with the promise that $f(x) = f(y)$ iff $y = x \oplus s$ for some hidden $s$, find $s$. The quantum algorithm uses $O(n)$ queries, while any classical algorithm requires $\Omega(2^{n/2})$ queries. This was the first provable exponential separation between quantum and randomized classical algorithms, and it directly inspired Shor's algorithm.

The Abelian Hidden Subgroup Problem: Both Deutsch-Jozsa and Bernstein-Vazirani are special cases of the abelian hidden subgroup problem. Given a group $G$ and a function $f: G \to S$ that is constant on cosets of a hidden subgroup $H$ and distinct on different cosets, find $H$. The quantum algorithm applies the QFT over $G$ to extract the subgroup structure. This framework encompasses Deutsch-Jozsa, Bernstein-Vazirani, Simon's problem, and Shor's factoring algorithm.

12.13 Simon's Problem: A Bridge to Exponential Speedup

Simon's problem (1994) is a natural extension of Bernstein-Vazirani that achieves an exponential quantum speedup against randomized classical algorithms. This makes it a stronger result than Deutsch-Jozsa (which only beats deterministic classical) and more practical than it might seem.

Simon's Problem: Given a function $f: \{0,1\}^n \to \{0,1\}^n$ with the promise that there exists a hidden string $s \in \{0,1\}^n$ (with $s \neq 0^n$) such that $f(x) = f(y)$ if and only if $y = x \oplus s$, find $s$.

The promise means that $f$ is 2-to-1: for every $x$, there is exactly one $y = x \oplus s$ such that $f(x) = f(y)$. The function has a "hidden period" $s$ in the group $\mathbb{Z}_2^n$.

Classical complexity: Any randomized classical algorithm requires $\Omega(2^{n/2})$ queries. This follows from the birthday paradox: to find two inputs $x, y$ with $f(x) = f(y)$, we need $\Theta(2^{n/2})$ random queries.

Quantum complexity: The quantum algorithm requires $O(n)$ queries.

The algorithm: The circuit is identical to Bernstein-Vazirani, but the oracle now maps $n$ input qubits to $n$ output qubits (not 1):

1. Apply $H^{\otimes n}$ to the input register.
2. Apply the oracle $U_f$.
3. Measure the output register. This collapses it to some value $f(x_0)$, and the input register collapses to $\frac{1}{\sqrt{2}}(|x_0\rangle + |x_0 \oplus s\rangle)$.
4. Apply $H^{\otimes n}$ to the input register and measure. This gives a random $y$ such that $y \cdot s = 0$.
5. Repeat $n-1$ times to get $n-1$ linearly independent equations of the form $y \cdot s = 0$.
6. Solve the system of linear equations to find $s$.

Each run of the circuit gives one equation $y \cdot s = 0$. After $O(n)$ runs, we have enough linearly independent equations to determine $s$ via Gaussian elimination.

Significance: Simon's problem was the first to demonstrate an exponential separation between quantum and randomized classical query complexity. It directly inspired Shor's algorithm, which uses a similar structure (period finding in a group) but over $\mathbb{Z}_N$ instead of $\mathbb{Z}_2^n$.

Recurring Theme — Quantum Advantage is Problem-Specific: Simon's problem achieves an exponential speedup because the function $f$ has a specific structure (hidden periodicity) that quantum algorithms can exploit via the Hadamard transform. For unstructured functions, no such speedup exists (as shown by the BBBV bound for search).

12.14 Practical Considerations and Noise

12.14.1 Effect of Noise on Deutsch-Jozsa

The Deutsch-Jozsa algorithm assumes a perfect oracle. In practice, the oracle circuit may introduce errors. Let us analyze the effect of a noisy oracle.

Suppose the oracle flips the wrong bit with probability $\varepsilon$. Then the phase kickback produces $(-1)^{f(x)}$ with probability $1 - \varepsilon$ and $(-1)^{1-f(x)}$ with probability $\varepsilon$. The amplitude of $|0\rangle^{\otimes n}$ after the final Hadamard becomes:

• For a constant function: $\frac{1}{2^n}\sum_x (-1)^{f(x)} \cdot (1 - 2\varepsilon) = (1 - 2\varepsilon) \cdot (\pm 1)$, so $P(|0\rangle^{\otimes n}) = (1 - 2\varepsilon)^2 \approx 1 - 4\varepsilon$
• For a balanced function: $\frac{1}{2^n}\sum_x (-1)^{f(x)}$ is no longer exactly zero, so $P(|0\rangle^{\otimes n}) \approx 4\varepsilon$

The algorithm still works as long as $\varepsilon$ is small enough that the constant case gives a much higher probability of measuring $|0\rangle^{\otimes n}$ than the balanced case.

Critical threshold: The algorithm loses its advantage when $\varepsilon \geq 1/4$, at which point the probability of measuring $|0\rangle^{\otimes n}$ is the same for constant and balanced functions.

12.14.2 Effect of Noise on Bernstein-Vazirani

For Bernstein-Vazirani, noise in the oracle causes the measured string to differ from $s$ in some bits. If each CNOT gate has error probability $\varepsilon$, the probability of correctly measuring $s$ is approximately $(1 - \varepsilon)^n \approx 1 - n\varepsilon$. For large $n$, this can become significant.

Mitigation: Run the algorithm multiple times and take the majority vote for each bit. With $O(\log(1/\delta))$ repetitions, the error probability drops to $\delta$.

Recurring Theme — Noise is the Enemy: Both algorithms are sensitive to noise in the oracle and in the Hadamard gates. On current quantum hardware, the error rates are high enough that these algorithms may give incorrect results for $n > 10$ or so. Error mitigation techniques (like running the inverse circuit and checking for consistency) can help, but true fault-tolerant quantum computation requires error correction.

12.13.3 Detailed Error Analysis for Deutsch-Jozsa

Let us compute the exact probability of error for the Deutsch-Jozsa algorithm with a noisy oracle. Suppose the oracle flips the phase of the correct state with probability $1 - \varepsilon$ and flips the wrong phase with probability $\varepsilon$.

For a constant function (all phases $+1$), the expected amplitude of $|0\rangle^{\otimes n}$ after the final Hadamard is:

$$\alpha_{0^n} = \frac{1}{2^n}\sum_x E[(-1)^{f_\varepsilon(x)}]$$

where $f_\varepsilon(x)$ is the noisy oracle output. For a constant function, $E[(-1)^{f_\varepsilon(x)}] = (1-\varepsilon)(+1) + \varepsilon(-1) = 1 - 2\varepsilon$ for each $x$.

Therefore $\alpha_{0^n} = 1 - 2\varepsilon$ and $P(|0\rangle^{\otimes n}) = (1-2\varepsilon)^2$.

For a balanced function, exactly half the phases are flipped by noise, so the expected amplitude of $|0\rangle^{\otimes n}$ is:

$$E[\alpha_{0^n}] = \frac{1}{2^n}\sum_x E[(-1)^{f_\varepsilon(x)}] \approx 0$$

to first order in $\varepsilon$, but with variance $\approx \varepsilon$. The probability of incorrectly measuring $|0\rangle^{\otimes n}$ is approximately $4\varepsilon$.

The algorithm distinguishes constant from balanced as long as $(1-2\varepsilon)^2 \gg 4\varepsilon$, i.e., $\varepsilon \ll 1/4$.

12.13.4 NISQ Implementation Considerations

On current Noisy Intermediate-Scale Quantum (NISQ) devices, the Deutsch-Jozsa and Bernstein-Vazirani algorithms face several challenges:

1. Gate errors: Each Hadamard gate and CNOT gate has a small probability of error. For a circuit with $O(n)$ gates and per-gate error rate $\delta$, the total error is approximately $n\delta$.

2. Readout errors: Measurement errors can flip the outcome of individual qubits. For an $n$-qubit measurement with per-qubit error rate $\mu$, the probability of measuring all qubits correctly is approximately $(1-\mu)^n$.

3. Decoherence: The circuit must execute within the coherence time $T_2$ of the qubits. For typical superconducting qubits, $T_2 \sim 100\ \mu\text{s}$, and gate times are $\sim 100\ \text{ns}$, allowing $\sim 1000$ gates before decoherence becomes significant.

For Deutsch-Jozsa with $n = 3$ (the typical demo on current hardware), the circuit depth is about 10-15 gates, well within current capabilities. Bernstein-Vazirani with $n = 5$ requires about 20-30 gates, also feasible. But for $n > 10$, the accumulated errors make the results unreliable.

Error mitigation strategies: - Readout error mitigation: Characterize the readout error matrix and apply its inverse to the measurement statistics. - Zero-noise extrapolation: Run the circuit at multiple noise levels and extrapolate to zero noise. - Randomized compiling: Convert deterministic errors into stochastic errors that are easier to mitigate.

12.15 Advanced Topic: The Deutsch-Jozsa Algorithm as a Hidden Subgroup Problem

Both Deutsch-Jozsa and Bernstein-Vazirani can be understood as instances of the hidden subgroup problem (HSP), which is the unifying framework for exponential quantum speedups.

The Hidden Subgroup Problem (HSP): Given a group $G$, a set $S$, and a function $f: G \to S$ that is constant on the cosets of a hidden subgroup $H \leq G$ and distinct on different cosets, find $H$ (or a generating set for $H$).

Deutsch-Jozsa as HSP:

The group is $G = \mathbb{Z}_2^n$ (binary strings under XOR). The function $f$ is either constant (hidden subgroup $H = G$) or balanced (hidden subgroup $H = \{0^n\}$). The algorithm distinguishes these two subgroups using a single query.

More precisely, in the Deutsch-Jozsa problem: - Constant function: $f(x) = c$ for all $x$. The kernel of $f$ is $H = G$, so $f$ is constant on all of $G$. - Balanced function: The kernel of $f$ is a subgroup of index 2 (or $f$ is balanced in a more general sense). The Hadamard transform reveals whether the kernel is the whole group or a proper subgroup.

Bernstein-Vazirani as HSP:

The function $f(x) = s \cdot x$ is a group homomorphism from $\mathbb{Z}_2^n$ to $\mathbb{Z}_2$. Its kernel is the subgroup $H = \{x : s \cdot x = 0\}$, which is a subgroup of index 2. The Hadamard transform maps the coset structure to computational basis states, revealing $s$.

Why this matters: The HSP framework generalizes to other groups: - $\mathbb{Z}_2^n$ (Deutsch-Jozsa, Bernstein-Vazirani, Simon's problem) - $\mathbb{Z}_N$ (Shor's factoring algorithm) - $\mathbb{Z}_N \times \mathbb{Z}_N$ (discrete logarithm)

In each case, the quantum algorithm uses the Fourier transform over the appropriate group to reveal the hidden subgroup structure. The exponential speedup comes from the ability of the QFT to extract global algebraic properties (subgroup structure) from a single function evaluation.

Recurring Theme — Quantum is Linear Algebra, Not Magic: The hidden subgroup problem is fundamentally about the representation theory of finite groups. The characters of the group form an orthonormal basis, and the QFT (or Hadamard transform) decomposes the function into these characters. The hidden subgroup determines which characters have nonzero Fourier coefficients, and a single measurement reveals this structure. All the "quantum magic" reduces to: (1) evaluate the function on a superposition, (2) compute the Fourier transform, (3) measure. The mathematics of group representations does the heavy lifting.

12.16 Quantum Advantage: What Deutsch-Jozsa and Bernstein-Vazirani Really Prove

It is important to be precise about what these algorithms prove about quantum advantage.

12.16.1 Deutsch-Jozsa: Exponential Separation (with a Caveat)

Deutsch-Jozsa proves an exponential separation between deterministic classical and quantum query complexity: 1 quantum query vs. $2^{n-1} + 1$ deterministic classical queries. However, a randomized classical algorithm can solve Deutsch-Jozsa with bounded error using only $O(1)$ queries (pick 2 random inputs; if they give the same answer, guess constant; if they give different answers, output balanced).

The probability of error for the randomized classical algorithm: After $k$ random queries, if all outputs are the same, the probability that the function is balanced (given this observation) is at most $1/2^{k-1}$. So with $k = O(\log(1/\varepsilon))$ queries, the error probability is at most $\varepsilon$.

What Deutsch-Jozsa really proves: It proves that quantum computers can solve certain promise problems with zero error (exactly) using exponentially fewer queries than deterministic classical algorithms. This is significant for understanding the power of quantum computation, even if it doesn't provide a practical advantage over randomized algorithms.

12.16.2 Bernstein-Vazirani: Polynomial but Robust Separation

Bernstein-Vazirani proves a polynomial separation (1 vs. $n$) that holds even against randomized classical algorithms. This is a more robust result because: - The classical lower bound of $n$ queries holds even for randomized algorithms with bounded error. - The quantum algorithm achieves zero error, so there's no gap between the quantum and classical success probabilities.

What Bernstein-Vazirani really proves: It proves that quantum computers can extract more information from a single function evaluation than classical computers. Specifically, a single quantum query reveals $n$ bits of information (the hidden string $s$), while a single classical query reveals only 1 bit (the value $s \cdot x$ for one specific $x$).

This is possible because the quantum query evaluates $f$ on a superposition of all $2^n$ inputs simultaneously, and the phase kickback mechanism extracts the global structure of $f$ (the inner product with $s$) rather than a single local value.

12.16.3 The Bigger Picture: Quantum Query Complexity

These results are best understood in the framework of quantum query complexity:

Deutsch-Jozsa has an exponential gap in the deterministic model but only a constant gap in the randomized model. Bernstein-Vazirani has a linear gap in both models.

The truly significant quantum speedups come from problems where the gap is exponential even against randomized classical algorithms: - Simon's problem: $O(n)$ quantum vs. $\Omega(2^{n/2})$ randomized classical - Shor's factoring: $O(n^3)$ quantum vs. $\Omega(2^{n^{1/3}})$ (conjectured) classical - Period finding: $O(n)$ quantum vs. $\Omega(2^{n/2})$ randomized classical