Deutsch-Jozsa Algorithm

Determine whether a Boolean function is constant or balanced with a single quantum query using the Deutsch-Jozsa algorithm.

---

Problem

What is the Deutsch-Jozsa Problem?

You are given a black-box (oracle) function $f:\{0,1{\}}^n\to \{0,1\}$ with the promise that $f$ is either:

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

The task is to determine which type $f$ is, using the fewest possible evaluations of $f$.

Classical Complexity

On a classical computer, in the worst case you must evaluate $f$ on $2^{n-1}+1$ inputs to be certain. With $n$ input bits there are $N=2^n$ possible inputs. After checking half of them ($2^{n-1}$) and finding that they all return the same value, you still cannot conclude the function is constant -- the very next evaluation could break the pattern. You need one more query to be sure.

Input bits $n$	Total inputs $N=2^n$	Classical worst case
1	2	2
2	4	3
3	8	5
10	1,024	513
20	1,048,576	524,289

Classical complexity is $O(N)=O(2^n)$ in the worst case.

Quantum Speedup

The Deutsch-Jozsa algorithm solves the problem with exactly one quantum query, regardless of $n$. The quantum circuit runs in $O(n)$ time (for the Hadamard transforms), but makes only a single call to the oracle $U_f$.

This was one of the first quantum algorithms to demonstrate an exponential separation between quantum and classical query complexity, albeit for a promise problem rather than a general one.

Historical Context

• 1985 -- David Deutsch proposed the original algorithm for $n=1$, showing that a quantum computer can distinguish $f(0)\oplus f(1)$ with one query instead of two.
• 1992 -- Deutsch and Richard Jozsa generalized the algorithm to arbitrary $n$.
• 1993 -- Ethan Bernstein and Umesh Vazirani published a related algorithm (Bernstein-Vazirani), which uses the same circuit structure to solve a different problem.

The Deutsch-Jozsa algorithm is primarily of theoretical interest. It demonstrates the principle of quantum parallelism and phase kickback, which underpin more practical algorithms like Shor's and Grover's.

---

Solution

Circuit Structure

The Deutsch-Jozsa circuit uses $n+1$ qubits: $n$ input qubits and 1 ancilla qubit. The algorithm proceeds in five steps:

Step 1: Initialize. Prepare $n$ input qubits in $|0⟩$ and the ancilla in $|1⟩$:

$$|{\psi }_0⟩=|0{⟩}^{\otimes n}|1⟩$$

Step 2: Hadamard all qubits. Apply $H$ to every qubit:

$$\parallel {\psi }_1⟩=\frac{1}{\sqrt{2^n}}\sum _{x=0}^{2^n-1}\parallel x⟩\otimes \frac{1}{\sqrt{2}}(\parallel 0⟩-\parallel 1⟩)$$

Step 3: Apply the oracle $U_f$. The oracle encodes $f$ via the phase kickback mechanism (explained below):

$$\parallel {\psi }_2⟩=\frac{1}{\sqrt{2^n}}\sum _{x=0}^{2^n-1}(-1{)}^{f(x)}\parallel x⟩\otimes \frac{1}{\sqrt{2}}(\parallel 0⟩-\parallel 1⟩)$$

Step 4: Hadamard on input qubits. Apply $H^{\otimes n}$ to the first $n$ qubits:

$$\parallel {\psi }_3⟩=\sum _{z=0}^{2^n-1}(\frac{1}{2^n}\sum _{x=0}^{2^n-1}(-1{)}^{f(x)}(-1{)}^{x\cdot z})\parallel z⟩\otimes \frac{1}{\sqrt{2}}(\parallel 0⟩-\parallel 1⟩)$$

Step 5: Measure. Measure the $n$ input qubits. The amplitude of $|0{⟩}^{\otimes n}$ is:

$${\alpha }_{0^n}=\frac{1}{2^n}\sum _{x=0}^{2^n-1}(-1{)}^{f(x)}$$

• If $f$ is constant, then $(-1{)}^{f(x)}$ is always $+1$ or always $-1$, so $|{\alpha }_{0^n}{|}^2=1$. We measure all zeros with certainty.
• If $f$ is balanced, the positive and negative terms cancel exactly, so ${\alpha }_{0^n}=0$. We never measure all zeros.

Decision Rule

Measurement of input qubits	Conclusion
All zeros: $|0{⟩}^{\otimes n}$	$f$ is constant
Anything else	$f$ is balanced

---

Code

The 1-Qubit Deutsch Algorithm

The simplest case ($n=1$) was Deutsch's original 1985 result. Given $f:\{0,1\}\to \{0,1\}$, determine whether $f(0)=f(1)$ (constant) or $f(0)\ne f(1)$ (balanced) with a single query.

There are four possible functions:

Function	$f(0)$	$f(1)$	Type
$f_0$	0	0	Constant
$f_1$	1	1	Constant
$f_2$	0	1	Balanced
$f_3$	1	0	Balanced

from pyqpanda3 import core


def deutsch_oracle(oracle_type: str) -> core.QProg:
    """Build a 1-qubit Deutsch oracle for the four possible functions.

    The oracle acts on 2 qubits: qubit 0 is the input, qubit 1 is the ancilla.
    For a constant-0 oracle, nothing happens (identity).
    For a constant-1 oracle, X is applied to the ancilla.
    For balanced oracles, CNOT or CNOT+X encodes the function.

    Args:
        oracle_type: One of 'const0', 'const1', 'balanced01', 'balanced10'.

    Returns:
        A QProg containing the oracle gates.
    """
    oracle = core.QProg()
    if oracle_type == "const0":
        # f(0)=0, f(1)=0: U_f = identity (no gates needed)
        pass
    elif oracle_type == "const1":
        # f(0)=1, f(1)=1: flip ancilla regardless of input
        oracle << core.X(1)
    elif oracle_type == "balanced01":
        # f(0)=0, f(1)=1: CNOT from input to ancilla
        oracle << core.CNOT(0, 1)
    elif oracle_type == "balanced10":
        # f(0)=1, f(1)=0: CNOT + X on ancilla
        oracle << core.CNOT(0, 1)
        oracle << core.X(1)
    else:
        raise ValueError(f"Unknown oracle type: {oracle_type}")
    return oracle


def deutsch_algorithm(oracle_type: str) -> str:
    """Run the 1-qubit Deutsch algorithm.

    Args:
        oracle_type: The oracle function to test.

    Returns:
        'constant' or 'balanced'.
    """
    prog = core.QProg()

    # Step 1: Initialize ancilla qubit 1 to |1>.
    prog << core.X(1)

    # Step 2: Hadamard on both qubits.
    prog << core.H(0)
    prog << core.H(1)

    # Step 3: Apply the oracle.
    prog << deutsch_oracle(oracle_type)

    # Step 4: Hadamard on the input qubit.
    prog << core.H(0)

    # Step 5: Measure input qubit.
    prog << core.measure([0], [0])

    # Run the circuit.
    machine = core.CPUQVM()
    machine.run(prog, shots=1)
    counts = machine.result().get_counts()

    # If we measure |0>, f is constant; if |1>, f is balanced.
    result_bit = list(counts.keys())[0]
    return "constant" if result_bit == "0" else "balanced"


# Test all four possible 1-bit functions.
print("=== 1-Qubit Deutsch Algorithm ===")
for oracle_type in ["const0", "const1", "balanced01", "balanced10"]:
    result = deutsch_algorithm(oracle_type)
    print(f"  {oracle_type:>14s} => {result}")

Expected output:

=== 1-Qubit Deutsch Algorithm ===
         const0 => constant
         const1 => constant
     balanced01 => balanced
     balanced10 => balanced

n-Qubit Deutsch-Jozsa with a Constant Oracle

A constant oracle is trivial to implement: it either does nothing ($f(x)=0$ for all $x$) or applies $X$ to the ancilla ($f(x)=1$ for all $x$). In either case, the input qubits are completely unaffected.

from pyqpanda3 import core


def constant_oracle(n: int, value: int) -> core.QProg:
    """Build a constant oracle: f(x) = value for all x.

    Args:
        n: Number of input qubits.
        value: 0 or 1 (the constant output).

    Returns:
        A QProg implementing the constant oracle.
    """
    oracle = core.QProg()
    if value == 1:
        # Ancilla is qubit n. Flip it to encode f(x)=1.
        oracle << core.X(n)
    # If value == 0, the oracle is the identity (no gates).
    return oracle


def deutsch_jozsa(n: int, oracle: core.QProg) -> str:
    """Run the Deutsch-Jozsa algorithm on n input qubits.

    Args:
        n: Number of input qubits.
        oracle: A QProg implementing the oracle U_f.

    Returns:
        'constant' or 'balanced'.
    """
    prog = core.QProg()

    # Step 1: Initialize ancilla (qubit n) to |1>.
    prog << core.X(n)

    # Step 2: Hadamard on all n+1 qubits.
    for i in range(n + 1):
        prog << core.H(i)

    # Step 3: Apply the oracle.
    prog << oracle

    # Step 4: Hadamard on the n input qubits.
    for i in range(n):
        prog << core.H(i)

    # Step 5: Measure the n input qubits.
    prog << core.measure(list(range(n)), list(range(n)))

    # Run the circuit.
    machine = core.CPUQVM()
    machine.run(prog, shots=1)
    counts = machine.result().get_counts()

    # If the measurement is all zeros, f is constant; otherwise balanced.
    all_zeros = "0" * n
    result_key = list(counts.keys())[0]
    return "constant" if result_key == all_zeros else "balanced"


# Test with a constant-0 oracle on 3 input qubits.
n = 3
print(f"=== Constant-0 Oracle (n={n}) ===")
oracle = constant_oracle(n, value=0)
result = deutsch_jozsa(n, oracle)
print(f"  Result: {result}")
assert result == "constant"

# Test with a constant-1 oracle.
print(f"\n=== Constant-1 Oracle (n={n}) ===")
oracle = constant_oracle(n, value=1)
result = deutsch_jozsa(n, oracle)
print(f"  Result: {result}")
assert result == "constant"

Expected output:

=== Constant-0 Oracle (n=3) ===
  Result: constant

=== Constant-1 Oracle (n=3) ===
  Result: constant

n-Qubit Deutsch-Jozsa with a Balanced Oracle

A balanced oracle returns $f(x)=0$ for exactly half the inputs and $f(x)=1$ for the other half. The simplest construction uses CNOT gates: for each input qubit $i$, a CNOT from qubit $i$ to the ancilla flips the ancilla whenever input bit $i$ is 1.

For the parity function $f(x)=x_0\oplus x_1\oplus \cdots \oplus x_{n-1}$, the oracle applies CNOT from every input qubit to the ancilla. This function is balanced because exactly half of all $n$-bit strings have even parity and half have odd parity.

from pyqpanda3 import core


def balanced_parity_oracle(n: int) -> core.QProg:
    """Build a balanced oracle computing the parity of the input.

    f(x) = x_0 XOR x_1 XOR ... XOR x_{n-1}

    This is balanced: exactly half of all inputs have even parity (f=0)
    and half have odd parity (f=1).

    Args:
        n: Number of input qubits.

    Returns:
        A QProg implementing the parity oracle.
    """
    oracle = core.QProg()
    # CNOT from each input qubit to the ancilla (qubit n).
    for i in range(n):
        oracle << core.CNOT(i, n)
    return oracle


# Test the balanced parity oracle on 3 input qubits.
n = 3
print(f"=== Balanced Parity Oracle (n={n}) ===")
oracle = balanced_parity_oracle(n)
result = deutsch_jozsa(n, oracle)
print(f"  Result: {result}")
assert result == "balanced"

Expected output:

=== Balanced Parity Oracle (n=3) ===
  Result: balanced

Building Balanced Oracles with CNOT and X Gates

There are many balanced functions. This section demonstrates several constructions and verifies that Deutsch-Jozsa correctly identifies all of them as balanced.

from pyqpanda3 import core


def balanced_first_bit_oracle(n: int) -> core.QProg:
    """Balanced oracle: f(x) = x_0 (the first input bit).

    Exactly half the inputs have x_0 = 0 and half have x_0 = 1.
    """
    oracle = core.QProg()
    oracle << core.CNOT(0, n)
    return oracle


def balanced_half_oracle(n: int) -> core.QProg:
    """Balanced oracle: f(x) = 1 iff x < 2^{n-1}.

    The first half of all inputs (by numerical value) maps to 1,
    the second half to 0. Achieved by CNOT on the most significant bit
    followed by X on the ancilla.
    """
    oracle = core.QProg()
    oracle << core.CNOT(n - 1, n)
    oracle << core.X(n)
    return oracle


def balanced_xor_pair_oracle(n: int) -> core.QProg:
    """Balanced oracle: f(x) = x_0 XOR x_1 (requires n >= 2).

    Balanced because for each setting of the other bits, exactly one
    of (x_0=0,x_1=1) and (x_0=1,x_1=0) gives f=1.
    """
    if n < 2:
        raise ValueError("XOR pair oracle requires n >= 2")
    oracle = core.QProg()
    oracle << core.CNOT(0, n)
    oracle << core.CNOT(1, n)
    return oracle


# Test multiple balanced oracle constructions.
n = 4
print(f"=== Multiple Balanced Oracles (n={n}) ===")

oracles = {
    "parity (all bits)": balanced_parity_oracle(n),
    "first bit": balanced_first_bit_oracle(n),
    "first half": balanced_half_oracle(n),
    "x_0 XOR x_1": balanced_xor_pair_oracle(n),
}

for name, oracle in oracles.items():
    result = deutsch_jozsa(n, oracle)
    print(f"  {name:>20s} => {result}")
    assert result == "balanced"

Expected output:

=== Multiple Balanced Oracles (n=4) ===
   parity (all bits) => balanced
           first bit => balanced
          first half => balanced
         x_0 XOR x_1 => balanced

Testing Multiple Oracle Types at Scale

This example runs a comprehensive test: for each $n$ from 1 to 6, it tests both constant oracles and the parity balanced oracle, verifying the algorithm produces the correct answer every time.

from pyqpanda3 import core


def run_all_tests(max_n: int = 6) -> None:
    """Run Deutsch-Jozsa on all oracle types for n = 1 to max_n.

    Tests constant-0, constant-1, and balanced (parity) oracles.
    Reports results and asserts correctness.
    """
    print(f"{'n':>3s}  {'Oracle':<20s}  {'Result':<10s}  {'Correct?'}")
    print("-" * 50)

    for n in range(1, max_n + 1):
        # Constant-0
        result = deutsch_jozsa(n, constant_oracle(n, 0))
        correct = result == "constant"
        print(f"{n:>3d}  {'constant-0':<20s}  {result:<10s}  {'OK' if correct else 'FAIL'}")

        # Constant-1
        result = deutsch_jozsa(n, constant_oracle(n, 1))
        correct = result == "constant"
        print(f"{n:>3d}  {'constant-1':<20s}  {result:<10s}  {'OK' if correct else 'FAIL'}")

        # Balanced (parity)
        result = deutsch_jozsa(n, balanced_parity_oracle(n))
        correct = result == "balanced"
        print(f"{n:>3d}  {'balanced (parity)':<20s}  {result:<10s}  {'OK' if correct else 'FAIL'}")

    print("\nAll tests passed!")


run_all_tests(max_n=6)

Expected output:

  n  Oracle                 Result      Correct?
--------------------------------------------------
  1  constant-0             constant    OK
  1  constant-1             constant    OK
  1  balanced (parity)      balanced    OK
  2  constant-0             constant    OK
  2  constant-1             constant    OK
  2  balanced (parity)      balanced    OK
  3  constant-0             constant    OK
  3  constant-1             constant    OK
  3  balanced (parity)      balanced    OK
  4  constant-0             constant    OK
  4  constant-1             constant    OK
  4  balanced (parity)      balanced    OK
  5  constant-0             constant    OK
  5  constant-1             constant    OK
  5  balanced (parity)      balanced    OK
  6  constant-0             constant    OK
  6  constant-1             constant    OK
  6  balanced (parity)      balanced    OK

All tests passed!

Verifying with State Vector Analysis

To understand what happens internally, run the circuit without measurement and inspect the state vector. This confirms that the constant oracle produces $|0{⟩}^{\otimes n}$ on the input qubits and the balanced oracle produces zero amplitude there.

from pyqpanda3 import core
import numpy as np


def analyze_state_vector(n: int, oracle: core.QProg, label: str) -> None:
    """Run Deutsch-Jozsa without measurement and print the input-qubit state.

    Args:
        n: Number of input qubits.
        oracle: The oracle to apply.
        label: Description for display.
    """
    prog = core.QProg()

    # Initialize ancilla to |1>.
    prog << core.X(n)

    # Hadamard all qubits.
    for i in range(n + 1):
        prog << core.H(i)

    # Apply oracle.
    prog << oracle

    # Hadamard on input qubits only.
    for i in range(n):
        prog << core.H(i)

    # No measurement -- get state vector.
    machine = core.CPUQVM()
    machine.run(prog, shots=1)
    sv = machine.result().get_state_vector()

    print(f"\n--- {label} (n={n}) ---")
    print(f"State vector length: {len(sv)}")

    # Extract probabilities for the input qubits.
    # The ancilla (qubit n) should be in (|0> - |1>)/sqrt(2) throughout.
    # We look at the probability of the all-zero state on input qubits.
    all_zeros_idx = 0  # ancilla |0>: input qubits all |0>
    # Also index where input qubits all 0 and ancilla is |1>
    all_zeros_with_anc1 = 2 ** n

    amp_0 = sv[all_zeros_idx]
    amp_1 = sv[all_zeros_with_anc1]
    prob_input_zeros = abs(amp_0) ** 2 + abs(amp_1) ** 2

    print(f"P(input qubits = |0>^{n}) = {prob_input_zeros:.6f}")
    print(f"  Amplitude |0>^{n}|0>_anc: {amp_0:.6f}")
    print(f"  Amplitude |0>^{n}|1>_anc: {amp_1:.6f}")

    # Print all non-zero amplitudes for inspection.
    print(f"\nNon-zero amplitudes (|threshold| > 0.001):")
    for idx in range(len(sv)):
        if abs(sv[idx]) > 0.001:
            bits = format(idx, f"0{n + 1}b")
            print(f"  |{bits}>: {sv[idx]:.6f}")


# Analyze constant-0 oracle.
n = 3
analyze_state_vector(n, constant_oracle(n, 0), "Constant-0 Oracle")

# Analyze balanced parity oracle.
analyze_state_vector(n, balanced_parity_oracle(n), "Balanced Parity Oracle")

Expected output:

--- Constant-0 Oracle (n=3) ---
State vector length: 16
P(input qubits = |0>^3) = 1.000000
  Amplitude |0>^3|0>_anc: 0.707107
  Amplitude |0>^3|1>_anc: -0.707107

Non-zero amplitudes (|threshold| > 0.001):
  |0000>: 0.707107
  |0001>: -0.707107

--- Balanced Parity Oracle (n=3) ---
State vector length: 16
P(input qubits = |0>^3) = 0.000000
  Amplitude |0>^3|0>_anc: 0.000000
  Amplitude |0>^3|1>_anc: 0.000000

Non-zero amplitudes (|threshold| > 0.001):
  |0010>: 0.500000
  |0100>: 0.500000
  |1000>: -0.500000
  |1110>: -0.500000
  |0011>: -0.500000
  |0101>: -0.500000
  |1010>: -0.500000
  |1111>: -0.500000

For the constant oracle, all amplitude is concentrated in $|000⟩$ on the input qubits (with the ancilla in $|-⟩$). For the balanced oracle, the all-zeros amplitude is exactly zero, confirming we never measure it.

Running on the Stabilizer Simulator

The Deutsch-Jozsa circuit uses only Clifford gates (H, X, CNOT), so it can be simulated efficiently using the Stabilizer backend. This is useful for large $n$ where the state vector grows as $2^n$.

from pyqpanda3 import core


def deutsch_jozsa_stabilizer(n: int, oracle: core.QProg) -> str:
    """Run Deutsch-Jozsa using the Stabilizer simulator.

    Args:
        n: Number of input qubits.
        oracle: The oracle to apply.

    Returns:
        'constant' or 'balanced'.
    """
    prog = core.QProg()

    prog << core.X(n)
    for i in range(n + 1):
        prog << core.H(i)
    prog << oracle
    for i in range(n):
        prog << core.H(i)
    prog << core.measure(list(range(n)), list(range(n)))

    stab = core.Stabilizer()
    stab.run(prog, shots=1)
    counts = stab.result().get_counts()

    all_zeros = "0" * n
    result_key = list(counts.keys())[0]
    return "constant" if result_key == all_zeros else "balanced"


# Verify the Stabilizer gives the same results as CPUQVM.
n = 5
print(f"=== Stabilizer Backend (n={n}) ===")

result = deutsch_jozsa_stabilizer(n, constant_oracle(n, 0))
print(f"  Constant-0: {result}")

result = deutsch_jozsa_stabilizer(n, balanced_parity_oracle(n))
print(f"  Balanced:   {result}")

Expected output:

=== Stabilizer Backend (n=5) ===
  Constant-0: constant
  Balanced:   balanced

Deutsch-Jozsa with Noise Simulation

Real quantum hardware introduces errors. This example shows how depolarizing noise can cause the Deutsch-Jozsa algorithm to produce incorrect results for the constant case (spurious non-zero measurement outcomes).

from pyqpanda3 import core


def deutsch_jozsa_noisy(n: int, oracle: core.QProg, shots: int = 1000) -> None:
    """Run Deutsch-Jozsa with a depolarizing noise model.

    Prints the measurement distribution and inferred result.
    """
    prog = core.QProg()
    prog << core.X(n)
    for i in range(n + 1):
        prog << core.H(i)
    prog << oracle
    for i in range(n):
        prog << core.H(i)
    prog << core.measure(list(range(n)), list(range(n)))

    # Noise model: 1% depolarizing on single-qubit gates, 2% on CNOT.
    noise = core.NoiseModel()
    for i in range(n + 1):
        noise.add_quantum_error(
            core.depolarizing_error(0.01), core.GateType.H, [i]
        )
    for i in range(n):
        noise.add_quantum_error(
            core.depolarizing_error(0.02), core.GateType.CNOT, [i, n]
        )

    machine = core.CPUQVM()
    machine.run(prog, shots=shots, model=noise)
    counts = machine.result().get_counts()

    all_zeros = "0" * n
    constant_prob = counts.get(all_zeros, 0) / shots
    print(f"  P(|{all_zeros}>) = {constant_prob:.4f}")
    print(f"  Counts: {counts}")

    # With noise, the result is a majority vote.
    if constant_prob > 0.5:
        print(f"  => Likely CONSTANT (noise-affected)")
    else:
        print(f"  => Likely BALANCED")


n = 3
print(f"=== Noisy Deutsch-Jozsa (n={n}, 1% H / 2% CNOT depolarizing) ===")
print(f"\nConstant-0 oracle:")
deutsch_jozsa_noisy(n, constant_oracle(n, 0))

print(f"\nBalanced parity oracle:")
deutsch_jozsa_noisy(n, balanced_parity_oracle(n))

Expected output (approximate):

=== Noisy Deutsch-Jozsa (n=3, 1% H / 2% CNOT depolarizing) ===

Constant-0 oracle:
  P(|000>) = 0.9430
  Counts: {'000': 943, '001': 12, '010': 15, '100': 10, '110': 8, '011': 4, '101': 5, '111': 3}
  => Likely CONSTANT (noise-affected)

Balanced parity oracle:
  P(|000>) = 0.0020
  Counts: {'010': 198, '011': 203, '001': 195, '101': 104, '110': 100, '100': 100, '111': 98}
  => Likely BALANCED

The constant oracle retains a high probability on $|000⟩$ despite noise, while the balanced oracle has near-zero probability there. With sufficient shots, the decision remains correct even under moderate noise.

---

Explanation

Phase Kickback

The key mechanism behind Deutsch-Jozsa is phase kickback. The oracle $U_f$ is defined by its action on the computational basis:

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

where $\oplus$ denotes XOR (addition mod 2).

Now consider what happens when the ancilla is in the state $|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$:

$$U_f|x⟩|-⟩=U_f|x⟩\cdot \frac{1}{\sqrt{2}}(|0⟩-|1⟩)$$$$=|x⟩\cdot \frac{1}{\sqrt{2}}(|0\oplus f(x)⟩-|1\oplus f(x)⟩)$$

If $f(x)=0$:

$$=|x⟩\cdot \frac{1}{\sqrt{2}}(|0⟩-|1⟩)=|x⟩|-⟩$$

If $f(x)=1$:

$$=|x⟩\cdot \frac{1}{\sqrt{2}}(|1⟩-|0⟩)=-|x⟩|-⟩$$

In both cases, the ancilla remains in $|-⟩$, but the input register picks up a phase of $(-1{)}^{f(x)}$:

$$U_f|x⟩|-⟩=(-1{)}^{f(x)}|x⟩|-⟩$$

This is the phase kickback: the function value is "kicked back" from the ancilla into the phase of the input register. The ancilla is effectively a catalyst -- it enables the phase encoding without being changed.

Why the Ancilla Starts in |1>

The ancilla must be prepared in $|1⟩$ (not $|0⟩$) so that the Hadamard gate puts it into $|-⟩$:

$$H|1⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=|-⟩$$

If the ancilla started in $|0⟩$, the Hadamard would produce $|+⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$, and the phase kickback would not work because:

$$U_f|x⟩|+⟩=|x⟩|+⟩$$

Both $f(x)=0$ and $f(x)=1$ produce the same result (no phase change), so no information about $f$ would be encoded.

Hadamard Transform Analysis

The $n$-qubit Hadamard transform $H^{\otimes n}$ plays a central role. It maps each computational basis state into a uniform superposition:

$$H^{\otimes n}|x⟩=\frac{1}{\sqrt{2^n}}\sum _{z=0}^{2^n-1}(-1{)}^{x\cdot z}|z⟩$$

where $x\cdot z=x_0{z}_0\oplus x_1{z}_1\oplus \cdots \oplus x_{n-1}{z}_{n-1}$ is the bitwise inner product modulo 2.

The full Deutsch-Jozsa algorithm applies $H^{\otimes n}$ three times (effective via two explicit applications and the initial superposition), sandwiching the oracle. The final state of the input register before measurement is:

$$|{\psi }_{\text{out}}⟩=H^{\otimes n}(\frac{1}{\sqrt{2^n}}\sum _x(-1{)}^{f(x)}|x⟩)$$$$=\sum _z(\frac{1}{2^n}\sum _x(-1{)}^{f(x)}(-1{)}^{x\cdot z})|z⟩$$

The amplitude of $|z⟩=|0{⟩}^{\otimes n}$ (where $z=0^n$) is:

$${\alpha }_{0^n}=\frac{1}{2^n}\sum _{x=0}^{2^n-1}(-1{)}^{f(x)}$$

Constant case: $(-1{)}^{f(x)}$ is always $+1$ (if $f\equiv 0$) or always $-1$ (if $f\equiv 1$). Either way, $|{\alpha }_{0^n}|=1$.

Balanced case: The sum splits into $2^{n-1}$ terms with $f(x)=0$ contributing $+1$ and $2^{n-1}$ terms with $f(x)=1$ contributing $-1$:

$${\alpha }_{0^n}=\frac{1}{2^n}(2^{n-1}\cdot (+1)+2^{n-1}\cdot (-1))=0$$

The constructive/destructive interference is total and deterministic -- there is no probabilistic ambiguity.

Step-by-Step Trace for n = 2

Let us trace through the algorithm for $n=2$ with both a constant and a balanced oracle.

Constant-0 Oracle: $f(x)=0$

Step	State of input qubits	State of ancilla
Initialize	$|00⟩$	$|1⟩$
After $H^{\otimes 3}$	$\frac{1}{2}(|00⟩+|01⟩+|10⟩+|11⟩)$	$|-⟩$
After $U_f$	$\frac{1}{2}(|00⟩+|01⟩+|10⟩+|11⟩)$	$|-⟩$
After $H^{\otimes 2}$	$|00⟩$	$|-⟩$
Measure	$|00⟩$ with certainty	--

Since $f(x)=0$ everywhere, no phase is added, and the second Hadamard perfectly reverses the first.

Balanced Oracle: $f(x)=x_0$

Step	State of input qubits	State of ancilla
Initialize	$|00⟩$	$|1⟩$
After $H^{\otimes 3}$	$\frac{1}{2}(|00⟩+|01⟩+|10⟩+|11⟩)$	$|-⟩$
After $U_f$	$\frac{1}{2}(|00⟩+|01⟩-|10⟩-|11⟩)$	$|-⟩$
After $H^{\otimes 2}$	$|10⟩$	$|-⟩$
Measure	$|10⟩$ with certainty	--

The phases from $f(x)$ cause destructive interference at $|00⟩$ and constructive interference at $|10⟩$.

The Oracle as a Quantum Gate

The oracle $U_f$ must be a unitary operator. For a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$, the standard oracle is:

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

This is always unitary because XOR is its own inverse: applying $U_f$ twice returns to the original state.

For specific functions, $U_f$ can be decomposed into elementary gates:

Function	Oracle Circuit	Gate Count
$f(x)=0$ (constant)	Identity	0
$f(x)=1$ (constant)	X on ancilla	1
$f(x)=x_i$ (balanced)	CNOT from qubit $i$ to ancilla	1
$f(x)=x_i\oplus x_j$ (balanced)	CNOT($i$, anc) + CNOT($j$, anc)	2
$f(x)=\underset{i}{⨁}{x}_i$ (balanced)	CNOT from each input to ancilla	$n$
$f(x)=\mathrm{\neg }{x}_0$ (balanced)	CNOT(0, anc) + X(anc)	2

Any balanced function can be expressed as $f(x)=s\cdot x$ for some string $s$ (a linear function), plus possibly a constant offset. The oracle for a linear function uses CNOT gates from each qubit $i$ where $s_i=1$ to the ancilla.

Connection to Bernstein-Vazirani

The Deutsch-Jozsa circuit is structurally identical to the Bernstein-Vazirani algorithm. While Deutsch-Jozsa distinguishes constant from balanced, Bernstein-Vazirani solves a different problem:

Bernstein-Vazirani problem. Given oracle access to $f_s(x)=s\cdot x$ for a secret string $s\in \{0,1{\}}^n$, find $s$.

The same circuit (Hadamard, oracle, Hadamard, measure) produces exactly $|s⟩$ as the measurement outcome. This works because the phase kickback encodes $(-1{)}^{s\cdot x}$, and the Hadamard transform acts as a quantum Fourier transform over $Z_2^n$, perfectly decoding the secret string.

from pyqpanda3 import core


def bernstein_vazirani(n: int, secret: str) -> str:
    """Run the Bernstein-Vazirani algorithm to recover a secret string.

    Args:
        n: Number of input qubits.
        secret: Binary string of length n (e.g., '101').

    Returns:
        The recovered secret string.
    """
    prog = core.QProg()

    # Initialize ancilla to |1>.
    prog << core.X(n)

    # Hadamard all qubits.
    for i in range(n + 1):
        prog << core.H(i)

    # Oracle: f_s(x) = s . x.
    # CNOT from qubit i to ancilla for each s_i = 1.
    for i in range(n):
        if secret[i] == "1":
            prog << core.CNOT(i, n)

    # Hadamard on input qubits.
    for i in range(n):
        prog << core.H(i)

    # Measure input qubits.
    prog << core.measure(list(range(n)), list(range(n)))

    # Run and return result.
    machine = core.CPUQVM()
    machine.run(prog, shots=1)
    counts = machine.result().get_counts()
    return list(counts.keys())[0]


# Test Bernstein-Vazirani.
n = 4
secrets = ["0000", "0001", "1010", "1111", "0101"]
print("=== Bernstein-Vazirani ===")
for s in secrets:
    recovered = bernstein_vazirani(n, s)
    print(f"  Secret: {s} => Recovered: {recovered} {'OK' if recovered == s else 'FAIL'}")

Expected output:

=== Bernstein-Vazirani ===
  Secret: 0000 => Recovered: 0000 OK
  Secret: 0001 => Recovered: 0001 OK
  Secret: 1010 => Recovered: 1010 OK
  Secret: 1111 => Recovered: 1111 OK
  Secret: 0101 => Recovered: 0101 OK

Note that the secret $s=0000$ gives a constant oracle ($f(x)=0$ for all $x$). The Deutsch-Jozsa and Bernstein-Vazirani algorithms share the same circuit -- only the interpretation of the output differs.

Connection to Other Quantum Algorithms

The techniques introduced by Deutsch-Jozsa appear throughout quantum computing:

• Phase kickback is the same mechanism used in quantum phase estimation, which underlies Shor's factoring algorithm.
• Hadamard transforms for creating superpositions and performing interference are used in virtually every quantum algorithm.
• Oracle-based algorithms (Grover, Simon) follow the same pattern of querying a black-box function in superposition.
• Constructive/destructive interference to amplify the correct answer appears in Grover's amplitude amplification.

Limitations and Practical Considerations

Probabilistic classical algorithm. Although the worst-case classical complexity is $O(2^{n-1}+1)$, a randomized classical algorithm that picks $k$ random inputs achieves an error probability of $2^{-(k-1)}$ for distinguishing constant from balanced functions. With $k=100$, the error probability is below $2^{-99}$, which is negligible. So the quantum advantage for Deutsch-Jozsa is mainly theoretical.

Oracle construction cost. In practice, someone must build the oracle circuit. If the oracle requires $O(2^n)$ gates to construct, the overall quantum advantage is lost. The algorithm is interesting when the oracle can be implemented efficiently (e.g., $O(n)$ gates).

Deterministic quantum advantage. Unlike the randomized classical algorithm, the quantum algorithm gives the correct answer with probability 1 (no error). This is rare among quantum algorithms -- most (like Grover's) have a small error probability.

Noise sensitivity. On noisy hardware, the constant oracle may produce non-zero measurement outcomes, leading to a false "balanced" verdict. Error mitigation or majority voting over multiple shots is needed.

Summary of Resources

Resource	Deutsch-Jozsa
Qubits	$n+1$
Oracle queries	1
Hadamard gates	$2n+1$
Total gates (parity oracle)	$2n+1+n=3n+1$
Circuit depth	$O(n)$
Measurement shots	1 (deterministic)

The algorithm is deterministic (probability 1 of correctness), requires only a single shot, and uses a linear number of gates.