Deutsch-Jozsa算法(Deutsch-Jozsa Algorithm)

使用 Deutsch-Jozsa 算法通过单次量子查询判定布尔函数是恒定的还是平衡的。

问题

什么是 Deutsch-Jozsa 问题？

给定一个黑盒(Oracle)函数 $f : {0, 1}^{n} \to {0, 1}$ ，承诺 $f$ 满足以下条件之一：

恒定的(Constant) -- 对所有输入 $f (x) = 0$ ，或对所有输入 $f (x) = 1$ 。
平衡的(Balanced) -- 对恰好一半的输入 $f (x) = 0$ ，对另一半输入 $f (x) = 1$ 。

任务是使用最少的 $f$ 求值次数判定 $f$ 是哪种类型。

经典复杂度

在经典计算机上，最坏情况下必须对 $2^{n - 1} + 1$ 个输入求值 $f$ 才能确定。当有 $n$ 个输入位时，共有 $N = 2^{n}$ 个可能的输入。检查其中一半（ $2^{n - 1}$ ）后发现它们都返回相同的值，你仍然不能断定函数是恒定的——下一个求值可能打破这个模式。你需要再多一次查询来确认。

输入位 $n$	总输入数 $N = 2^{n}$	经典最坏情况
1	2	2
2	4	3
3	8	5
10	1,024	513
20	1,048,576	524,289

经典最坏情况复杂度为 $O (N) = O (2^{n})$ 。

量子加速

Deutsch-Jozsa 算法仅需一次量子查询即可解决问题，与 $n$ 无关。量子电路的运行时间为 $O (n)$ （用于 Hadamard 变换），但只对 Oracle $U_{f}$ 进行一次调用。

这是最早展示量子与经典查询复杂度之间指数分离的量子算法之一，尽管是针对承诺问题而非一般问题。

历史背景

1985 年 -- David Deutsch 提出了 $n = 1$ 的原始算法，证明量子计算机可以通过一次查询而非两次来确定 $f (0) \oplus f (1)$ 的值。
1992 年 -- Deutsch 和 Richard Jozsa 将算法推广到任意 $n$ 。
1993 年 -- Ethan Bernstein 和 Umesh Vazirani 发表了相关算法（Bernstein-Vazirani 算法），使用相同的电路结构解决不同的问题。

Deutsch-Jozsa 算法主要具有理论意义。它展示了量子并行性(Quantum Parallelism)和相位回踢(Phase Kickback)的原理，这些原理也是 Shor 算法和 Grover 算法等更实用算法的基础。

方案

电路结构

Deutsch-Jozsa 电路使用 $n + 1$ 个量子比特： $n$ 个输入量子比特和 1 个辅助量子比特(Ancilla)。算法分为五个步骤：

步骤 1：初始化。 将 $n$ 个输入量子比特制备为 $| 0 ⟩$ ，辅助量子比特制备为 $| 1 ⟩$ ：

| ψ_{0} ⟩ = | 0 ⟩^{\otimes n} | 1 ⟩

步骤 2：对所有量子比特施加 Hadamard。 对每个量子比特施加 $H$ ：

∥ ψ_{1} ⟩ = \frac{1}{\sqrt{2^{n}}} \sum_{x = 0}^{2^{n} - 1} ∥ x ⟩ \otimes \frac{1}{\sqrt{2}} (∥ 0 ⟩ - ∥ 1 ⟩)

步骤 3：施加 Oracle $U_{f}$ 。 Oracle 通过相位回踢机制编码 $f$ （下面解释）：

∥ ψ_{2} ⟩ = \frac{1}{\sqrt{2^{n}}} \sum_{x = 0}^{2^{n} - 1} (- 1)^{f (x)} ∥ x ⟩ \otimes \frac{1}{\sqrt{2}} (∥ 0 ⟩ - ∥ 1 ⟩)

步骤 4：对输入量子比特施加 Hadamard。 对前 $n$ 个量子比特施加 $H^{\otimes n}$ ：

∥ ψ_{3} ⟩ = \sum_{z = 0}^{2^{n} - 1} (\frac{1}{2^{n}} \sum_{x = 0}^{2^{n} - 1} (- 1)^{f (x)} (- 1)^{x \cdot z}) ∥ z ⟩ \otimes \frac{1}{\sqrt{2}} (∥ 0 ⟩ - ∥ 1 ⟩)

步骤 5：测量。 测量 $n$ 个输入量子比特。 $| 0 ⟩^{\otimes n}$ 的振幅为：

α_{0^{n}} = \frac{1}{2^{n}} \sum_{x = 0}^{2^{n} - 1} (- 1)^{f (x)}

如果 $f$ 是恒定的，则 $(- 1)^{f (x)}$ 始终为 $+ 1$ 或始终为 $- 1$ ，因此 $| α_{0^{n}} |^{2} = 1$ 。我们确定性地测得全零。
如果 $f$ 是平衡的，正负项精确相消，因此 $α_{0^{n}} = 0$ 。我们永远不会测得全零。

判定规则

输入量子比特的测量结果	结论
全零： $\| 0 ⟩^{\otimes n}$	$f$ 是恒定的
其他任何结果	$f$ 是平衡的

代码

1 量子比特 Deutsch 算法

最简单的情况（ $n = 1$ ）是 Deutsch 1985 年的原始结果。给定 $f : {0, 1} \to {0, 1}$ ，通过单次查询判定 $f (0) = f (1)$ （恒定的）还是 $f (0) \neq f (1)$ （平衡的）。

有四种可能的函数：

函数	$f (0)$	$f (1)$	类型
$f_{0}$	0	0	恒定的
$f_{1}$	1	1	恒定的
$f_{2}$	0	1	平衡的
$f_{3}$	1	0	平衡的

python

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}")

预期输出：

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

n 量子比特 Deutsch-Jozsa 与恒定 Oracle

恒定 Oracle 的实现很简单：要么什么也不做（对所有 $x$ ， $f (x) = 0$ ），要么对辅助量子比特施加 $X$ （对所有 $x$ ， $f (x) = 1$ ）。无论哪种情况，输入量子比特完全不受影响。

python

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"

预期输出：

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

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

n 量子比特 Deutsch-Jozsa 与平衡 Oracle

平衡 Oracle 对恰好一半的输入返回 $f (x) = 0$ ，对另一半返回 $f (x) = 1$ 。最简单的构造使用 CNOT 门：对每个输入量子比特 $i$ ，从量子比特 $i$ 到辅助量子比特的 CNOT 在输入位 $i$ 为 1 时翻转辅助量子比特。

对于奇偶校验函数 $f (x) = x_{0} \oplus x_{1} \oplus \dots \oplus x_{n - 1}$ ，Oracle 对每个输入量子比特到辅助量子比特施加 CNOT。这个函数是平衡的，因为恰好一半的 $n$ 位字符串具有偶奇偶性，一半具有奇奇偶性。

python

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"

预期输出：

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

使用 CNOT 和 X 门构建平衡 Oracle

存在许多平衡函数。本节演示几种构造并验证 Deutsch-Jozsa 能正确识别它们全部为平衡的。

python

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"

预期输出：

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

多种 Oracle 类型的规模化测试

本示例运行综合测试：对从 1 到 6 的每个 $n$ ，测试两种恒定 Oracle 和奇偶校验平衡 Oracle，验证算法每次都产生正确答案。

python

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)

预期输出：

  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!

使用状态向量分析验证

为了理解内部发生了什么，运行不带测量的电路并检查状态向量。这确认了恒定 Oracle 在输入量子比特上产生 $| 0 ⟩^{\otimes n}$ ，而平衡 Oracle 在那里产生零振幅。

python

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")

预期输出：

--- 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

对于恒定 Oracle，所有振幅集中在输入量子比特的 $| 000 ⟩$ （辅助量子比特处于 $| - ⟩$ ）。对于平衡 Oracle，全零振幅精确为零，确认我们永远不会测得全零。

在 Stabilizer 模拟器上运行

Deutsch-Jozsa 电路仅使用 Clifford 门（H, X, CNOT），因此可以使用 Stabilizer 后端高效模拟。这对于较大的 $n$ 非常有用，因为状态向量以 $2^{n}$ 的规模增长。

python

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}")

预期输出：

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

带噪声模拟的 Deutsch-Jozsa

真实量子硬件会引入误差。本示例展示去极化噪声如何导致 Deutsch-Jozsa 算法在恒定情况下产生错误结果（虚假的非零测量结果）。

python

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))

预期输出（近似）：

=== 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

尽管有噪声，恒定 Oracle 仍保持 $| 000 ⟩$ 上的高概率，而平衡 Oracle 在那里的概率接近零。在足够多的采样次数下，即使在中等噪声下判定结果仍然是正确的。

解析

相位回踢(Phase Kickback)

Deutsch-Jozsa 背后的关键机制是相位回踢。Oracle $U_{f}$ 通过其在计算基上的作用定义：

U_{f} | x ⟩ | y ⟩ = | x ⟩ | y \oplus f (x) ⟩

其中 $\oplus$ 表示 XOR（模 2 加法）。

现在考虑辅助量子比特处于态 $| - ⟩ = \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) ⟩)

如果 $f (x) = 0$ ：

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

如果 $f (x) = 1$ ：

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

在两种情况下，辅助量子比特都保持在 $| - ⟩$ ，但输入寄存器获得了相位 $(- 1)^{f (x)}$ ：

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

这就是相位回踢：函数值被从辅助量子比特"回踢"到输入寄存器的相位中。辅助量子比特本质上是催化剂——它实现了相位编码而自身不发生改变。

为什么辅助量子比特初始化为 |1>

辅助量子比特必须制备为 $| 1 ⟩$ （而非 $| 0 ⟩$ ），这样 Hadamard 门才能将其变为 $| - ⟩$ ：

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

如果辅助量子比特从 $| 0 ⟩$ 开始，Hadamard 会产生 $| + ⟩ = \frac{1}{\sqrt{2}} (| 0 ⟩ + | 1 ⟩)$ ，相位回踢将不起作用，因为：

U_{f} | x ⟩ | + ⟩ = | x ⟩ | + ⟩

$f (x) = 0$ 和 $f (x) = 1$ 产生相同的结果（没有相位变化），因此不会编码关于 $f$ 的任何信息。

Hadamard 变换分析

$n$ 量子比特 Hadamard 变换 $H^{\otimes n}$ 扮演核心角色。它将每个计算基态映射为均匀叠加：

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

其中 $x \cdot z = x_{0} z_{0} \oplus x_{1} z_{1} \oplus \dots \oplus x_{n - 1} z_{n - 1}$ 是按位内积模 2。

完整的 Deutsch-Jozsa 算法将 $H^{\otimes n}$ 应用三次（通过初始叠加和两次显式应用），在 Oracle 两侧。测量前输入寄存器的最终态为：

| ψ_{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 ⟩

$| z ⟩ = | 0 ⟩^{\otimes n}$ （其中 $z = 0^{n}$ ）的振幅为：

α_{0^{n}} = \frac{1}{2^{n}} \sum_{x = 0}^{2^{n} - 1} (- 1)^{f (x)}

恒定情况： $(- 1)^{f (x)}$ 始终为 $+ 1$ （如果 $f \equiv 0$ ）或始终为 $- 1$ （如果 $f \equiv 1$ ）。无论哪种情况， $| α_{0^{n}} | = 1$ 。

平衡情况： 求和被分成 $2^{n - 1}$ 个 $f (x) = 0$ 的项（贡献 $+ 1$ ）和 $2^{n - 1}$ 个 $f (x) = 1$ 的项（贡献 $- 1$ ）：

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

相长/相消干涉是完全的、确定性的——不存在概率性模糊。

n = 2 的逐步追踪

让我们追踪 $n = 2$ 时算法对恒定和平衡 Oracle 的执行过程。

恒定-0 Oracle： $f (x) = 0$

步骤	输入量子比特的状态	辅助量子比特的状态
初始化	$\| 00 ⟩$	$\| 1 ⟩$
$H^{\otimes 3}$ 后	$\frac{1}{2} (\| 00 ⟩ + \| 01 ⟩ + \| 10 ⟩ + \| 11 ⟩)$	$\| - ⟩$
$U_{f}$ 后	$\frac{1}{2} (\| 00 ⟩ + \| 01 ⟩ + \| 10 ⟩ + \| 11 ⟩)$	$\| - ⟩$
$H^{\otimes 2}$ 后	$\| 00 ⟩$	$\| - ⟩$
测量	确定为 $\| 00 ⟩$	--

由于 $f (x) = 0$ 处处成立，没有添加相位，第二个 Hadamard 完美逆转变第一个。

平衡 Oracle： $f (x) = x_{0}$

步骤	输入量子比特的状态	辅助量子比特的状态
初始化	$\| 00 ⟩$	$\| 1 ⟩$
$H^{\otimes 3}$ 后	$\frac{1}{2} (\| 00 ⟩ + \| 01 ⟩ + \| 10 ⟩ + \| 11 ⟩)$	$\| - ⟩$
$U_{f}$ 后	$\frac{1}{2} (\| 00 ⟩ + \| 01 ⟩ - \| 10 ⟩ - \| 11 ⟩)$	$\| - ⟩$
$H^{\otimes 2}$ 后	$\| 10 ⟩$	$\| - ⟩$
测量	确定为 $\| 10 ⟩$	--

来自 $f (x)$ 的相位导致 $| 00 ⟩$ 处的相消干涉和 $| 10 ⟩$ 处的相长干涉。

Oracle 作为量子门

Oracle $U_{f}$ 必须是酉算子。对于布尔函数 $f : {0, 1}^{n} \to {0, 1}$ ，标准 Oracle 为：

U_{f} | x ⟩ | y ⟩ = | x ⟩ | y \oplus f (x) ⟩

这总是酉的，因为 XOR 是自身的逆：应用 $U_{f}$ 两次回到原始态。

对于特定函数， $U_{f}$ 可以分解为基本门：

函数	Oracle 电路	门数量
$f (x) = 0$ （恒定的）	恒等	0
$f (x) = 1$ （恒定的）	辅助量子比特上的 X	1
$f (x) = x_{i}$ （平衡的）	从量子比特 $i$ 到辅助量子比特的 CNOT	1
$f (x) = x_{i} \oplus x_{j}$ （平衡的）	CNOT( $i$ , anc) + CNOT( $j$ , anc)	2
$f (x) = ⨁_{i} x_{i}$ （平衡的）	从每个输入到辅助量子比特的 CNOT	$n$
$f (x) = \neg x_{0}$ （平衡的）	CNOT(0, anc) + X(anc)	2

任何平衡函数都可以表示为 $f (x) = s \cdot x$ （对某个字符串 $s$ 的线性函数），加上可能的常数偏移。线性函数的 Oracle 对每个 $s_{i} = 1$ 的量子比特 $i$ 使用到辅助量子比特的 CNOT 门。

与 Bernstein-Vazirani 算法的联系

Deutsch-Jozsa 电路在结构上与 Bernstein-Vazirani 算法完全相同。Deutsch-Jozsa 区分恒定与平衡，而 Bernstein-Vazirani 解决不同的问题：

Bernstein-Vazirani 问题。 给定对 $f_{s} (x) = s \cdot x$ 的 Oracle 访问（ $s$ 为秘密字符串 $s \in {0, 1}^{n}$ ），找到 $s$ 。

相同的电路（Hadamard、Oracle、Hadamard、测量）精确产生 $| s ⟩$ 作为测量结果。这是因为相位回踢编码了 $(- 1)^{s \cdot x}$ ，而 Hadamard 变换充当 $Z_{2}^{n}$ 上的量子傅里叶变换，完美解码秘密字符串。

python

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'}")

预期输出：

=== 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

注意秘密 $s = 0000$ 给出恒定 Oracle（对所有 $x$ ， $f (x) = 0$ ）。

与其他量子算法的联系

Deutsch-Jozsa 引入的技术贯穿整个量子计算：

相位回踢是量子相位估计中使用的相同机制，是 Shor 因数分解算法的基础。
Hadamard 变换用于创建叠加和执行干涉，在几乎所有量子算法中使用。
基于 Oracle 的算法（Grover、Simon）遵循在叠加中查询黑盒函数的相同模式。
相长/相消干涉放大正确答案在 Grover 的振幅放大中出现。

局限性与实际考虑

概率性经典算法。 尽管最坏情况经典复杂度为 $O (2^{n - 1} + 1)$ ，选择 $k$ 个随机输入的随机化经典算法区分恒定与平衡函数的错误概率为 $2^{- (k - 1)}$ 。当 $k = 100$ 时，错误概率低于 $2^{- 99}$ ，可以忽略不计。因此 Deutsch-Jozsa 的量子优势主要是理论上的。

Oracle 构建成本。 在实践中，必须有人构建 Oracle 电路。如果 Oracle 需要 $O (2^{n})$ 个门来构建，则整体的量子优势就消失了。当 Oracle 可以高效实现（例如 $O (n)$ 个门）时，该算法才有意义。

确定性量子优势。 与随机化经典算法不同，量子算法以概率 1 给出正确答案（无错误）。这在量子算法中很少见——大多数（如 Grover）有小的错误概率。

噪声敏感性。 在有噪声的硬件上，恒定 Oracle 可能产生非零测量结果，导致错误的"平衡"判定。需要错误缓解或多次采样的多数投票。

资源总结

资源	Deutsch-Jozsa
量子比特	$n + 1$
Oracle 查询	1
Hadamard 门	$2 n + 1$
总门数（奇偶校验 Oracle）	$2 n + 1 + n = 3 n + 1$
电路深度	$O (n)$
测量采样次数	1（确定性的）

该算法是确定性的（正确概率为 1），只需单次采样，使用线性数量的门。

Deutsch-Jozsa算法(Deutsch-Jozsa Algorithm) ​

问题 ​

什么是 Deutsch-Jozsa 问题？ ​

经典复杂度 ​

量子加速 ​

历史背景 ​

方案 ​

电路结构 ​

判定规则 ​

代码 ​

1 量子比特 Deutsch 算法 ​

n 量子比特 Deutsch-Jozsa 与恒定 Oracle ​

n 量子比特 Deutsch-Jozsa 与平衡 Oracle ​

使用 CNOT 和 X 门构建平衡 Oracle ​

多种 Oracle 类型的规模化测试 ​

使用状态向量分析验证 ​

在 Stabilizer 模拟器上运行 ​

带噪声模拟的 Deutsch-Jozsa ​

解析 ​

相位回踢(Phase Kickback) ​

为什么辅助量子比特初始化为 |1> ​

Hadamard 变换分析 ​

n = 2 的逐步追踪 ​

恒定-0 Oracle：f(x)=0 ​

平衡 Oracle：f(x)=x0 ​

Oracle 作为量子门 ​

与 Bernstein-Vazirani 算法的联系 ​

与其他量子算法的联系 ​

局限性与实际考虑 ​

资源总结 ​

Deutsch-Jozsa算法(Deutsch-Jozsa Algorithm)

问题

什么是 Deutsch-Jozsa 问题？

经典复杂度

量子加速

历史背景

方案

电路结构

判定规则

代码

1 量子比特 Deutsch 算法

n 量子比特 Deutsch-Jozsa 与恒定 Oracle

n 量子比特 Deutsch-Jozsa 与平衡 Oracle

使用 CNOT 和 X 门构建平衡 Oracle

多种 Oracle 类型的规模化测试

使用状态向量分析验证

在 Stabilizer 模拟器上运行

带噪声模拟的 Deutsch-Jozsa

解析

相位回踢(Phase Kickback)

为什么辅助量子比特初始化为 |1>

Hadamard 变换分析

n = 2 的逐步追踪

恒定-0 Oracle： $f (x) = 0$

平衡 Oracle： $f (x) = x_{0}$

Oracle 作为量子门

与 Bernstein-Vazirani 算法的联系

与其他量子算法的联系

局限性与实际考虑

资源总结