Deutsch-Jozsa算法(Deutsch-Jozsa Algorithm)
使用 Deutsch-Jozsa 算法通过单次量子查询判定布尔函数是恒定的还是平衡的。
问题
什么是 Deutsch-Jozsa 问题？
给定一个黑盒(Oracle)函数
- 恒定的(Constant) -- 对所有输入
，或对所有输入 。 - 平衡的(Balanced) -- 对恰好一半的输入
，对另一半输入 。
任务是使用最少的
经典复杂度
在经典计算机上，最坏情况下必须对
| 输入位 | 总输入数 | 经典最坏情况 |
|---|---|---|
| 1 | 2 | 2 |
| 2 | 4 | 3 |
| 3 | 8 | 5 |
| 10 | 1,024 | 513 |
| 20 | 1,048,576 | 524,289 |
经典最坏情况复杂度为
量子加速
Deutsch-Jozsa 算法仅需一次量子查询即可解决问题，与
这是最早展示量子与经典查询复杂度之间指数分离的量子算法之一，尽管是针对承诺问题而非一般问题。
mermaid
graph LR
A["Oracle f(x)"] --> B{"经典"}
A --> C{"量子"}
B --> D["O(2^n / 2 + 1) 次查询"]
C --> E["1 次查询, O(n) 个门"]
style D fill:#EF5350,color:#fff
style E fill:#66BB6A,color:#fff历史背景
- 1985 年 -- David Deutsch 提出了
的原始算法，证明量子计算机可以通过一次查询而非两次来确定 的值。 - 1992 年 -- Deutsch 和 Richard Jozsa 将算法推广到任意
。 - 1993 年 -- Ethan Bernstein 和 Umesh Vazirani 发表了相关算法（Bernstein-Vazirani 算法），使用相同的电路结构解决不同的问题。
Deutsch-Jozsa 算法主要具有理论意义。它展示了量子并行性(Quantum Parallelism)和相位回踢(Phase Kickback)的原理，这些原理也是 Shor 算法和 Grover 算法等更实用算法的基础。
方案
电路结构
Deutsch-Jozsa 电路使用
mermaid
flowchart LR
subgraph S1["步骤 1"]
A["|0>^n |1>"]
end
subgraph S2["步骤 2"]
B["H^(n+1)"]
end
subgraph S3["步骤 3"]
C["U_f"]
end
subgraph S4["步骤 4"]
D["H^n | I"]
end
subgraph S5["步骤 5"]
E["测量前 n 个"]
end
S1 --> S2 --> S3 --> S4 --> S5
style S1 fill:#E3F2FD
style S2 fill:#BBDEFB
style S3 fill:#90CAF9
style S4 fill:#64B5F6
style S5 fill:#42A5F5,color:#fff步骤 1：初始化。 将
步骤 2：对所有量子比特施加 Hadamard。 对每个量子比特施加
步骤 3：施加 Oracle
步骤 4：对输入量子比特施加 Hadamard。 对前
步骤 5：测量。 测量
- 如果
是恒定的，则 始终为 或始终为 ，因此 。我们确定性地测得全零。 - 如果
是平衡的，正负项精确相消，因此 。我们永远不会测得全零。
判定规则
| 输入量子比特的测量结果 | 结论 |
|---|---|
| 全零： | |
| 其他任何结果 |
mermaid
flowchart TD
A["测量输入量子比特"] --> B{"结果 = |0>^n ?"}
B -->|"是"| C["f 是恒定的"]
B -->|"否"| D["f 是平衡的"]
style C fill:#C8E6C9
style D fill:#FFCDD2代码
1 量子比特 Deutsch 算法
最简单的情况（
有四种可能的函数：
| 函数 | 类型 | ||
|---|---|---|---|
| 0 | 0 | 恒定的 | |
| 1 | 1 | 恒定的 | |
| 0 | 1 | 平衡的 | |
| 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预期输出：
=== 1-Qubit Deutsch Algorithm ===
const0 => constant
const1 => constant
balanced01 => balanced
balanced10 => balancedn 量子比特 Deutsch-Jozsa 与恒定 Oracle
恒定 Oracle 的实现很简单：要么什么也不做（对所有
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预期输出：
=== Constant-0 Oracle (n=3) ===
Result: constant
=== Constant-1 Oracle (n=3) ===
Result: constantn 量子比特 Deutsch-Jozsa 与平衡 Oracle
平衡 Oracle 对恰好一半的输入返回
对于奇偶校验函数
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预期输出：
=== 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预期输出：
=== Multiple Balanced Oracles (n=4) ===
parity (all bits) => balanced
first bit => balanced
first half => balanced
x_0 XOR x_1 => balanced多种 Oracle 类型的规模化测试
本示例运行综合测试：对从 1 到 6 的每个
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!预期输出：
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 在输入量子比特上产生
python
from pyqpanda3 import core
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+0.000000j
Amplitude |0>^3|1>_anc: -0.707107+0.000000j
Non-zero amplitudes (|threshold| > 0.001):
|0000>: 0.707107+0.000000j
|1000>: -0.707107+0.000000j
--- Balanced Parity Oracle (n=3) ---
State vector length: 16
P(input qubits = |0>^3) = 0.000000
Amplitude |0>^3|0>_anc: 0.000000+0.000000j
Amplitude |0>^3|1>_anc: 0.000000+0.000000j
Non-zero amplitudes (|threshold| > 0.001):
|0111>: 0.707107+0.000000j
|1111>: -0.707107+0.000000j预期输出：
--- Constant-0 Oracle (n=3) ---
State vector length: 16
P(input qubits = |0>^3) = 1.000000
Amplitude |0>^3|0>_anc: 0.707107+0.000000j
Amplitude |0>^3|1>_anc: -0.707107+0.000000j
Non-zero amplitudes (|threshold| > 0.001):
|0000>: 0.707107+0.000000j
|1000>: -0.707107+0.000000j
--- Balanced Parity Oracle (n=3) ---
State vector length: 16
P(input qubits = |0>^3) = 0.000000
Amplitude |0>^3|0>_anc: 0.000000+0.000000j
Amplitude |0>^3|1>_anc: 0.000000+0.000000j
Non-zero amplitudes (|threshold| > 0.001):
|0111>: 0.707107+0.000000j
|1111>: -0.707107+0.000000j对于恒定 Oracle，所有振幅集中在输入量子比特的
在 Stabilizer 模拟器上运行
Deutsch-Jozsa 电路仅使用 Clifford 门（H, X, CNOT），因此可以使用 Stabilizer 后端高效模拟。这对于较大的
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预期输出：
=== 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.9090
Counts: {'101': 3, '000': 909, '100': 18, '001': 37, '010': 30, '110': 2, '011': 1}
=> Likely CONSTANT (noise-affected)
Balanced parity oracle:
P(|000>) = 0.0050
Counts: {'111': 820, '010': 8, '110': 55, '000': 5, '101': 29, '100': 7, '001': 30, '011': 46}
=> Likely BALANCED预期输出（近似）：
=== 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 仍保持
解析
相位回踢(Phase Kickback)
Deutsch-Jozsa 背后的关键机制是相位回踢。Oracle
其中
现在考虑辅助量子比特处于态
如果
如果
在两种情况下，辅助量子比特都保持在
这就是相位回踢：函数值被从辅助量子比特"回踢"到输入寄存器的相位中。辅助量子比特本质上是催化剂——它实现了相位编码而自身不发生改变。
mermaid
sequenceDiagram
participant Input as Input Register
participant Ancilla as Ancilla
participant Oracle as U_f
Note over Input: Superposition over all x
Note over Ancilla: Prepared in |->
Input->>Oracle: x
Ancilla->>Oracle: |->
Note over Oracle: Computes f(x)
Oracle->>Input: (-1)^f(x) x
Oracle->>Ancilla: |-> (unchanged)
Note over Input: f(x) encoded as phase
Note over Ancilla: Still in |->为什么辅助量子比特初始化为 |1>
辅助量子比特必须制备为
如果辅助量子比特从
Hadamard 变换分析
其中
完整的 Deutsch-Jozsa 算法将
恒定情况：
平衡情况： 求和被分成
相长/相消干涉是完全的、确定性的——不存在概率性模糊。
n = 2 的逐步追踪
让我们追踪
恒定-0 Oracle：
| 步骤 | 输入量子比特的状态 | 辅助量子比特的状态 |
|---|---|---|
| 初始化 | ||
| 测量 | 确定为 | -- |
由于
平衡 Oracle：
| 步骤 | 输入量子比特的状态 | 辅助量子比特的状态 |
|---|---|---|
| 初始化 | ||
| 测量 | 确定为 | -- |
来自
mermaid
flowchart TD
subgraph Const["恒定-0 Oracle"]
C1["H|0>^2 = 均匀叠加"]
C2["U_f: 无相位变化"]
C3["H^2: 逆转回 |00>"]
C4["测量: 00 (恒定的)"]
C1 --> C2 --> C3 --> C4
end
subgraph Bal["平衡 f(x) = x_0"]
B1["H|0>^2 = 均匀叠加"]
B2["U_f: 相位 (-1)^{x_0}"]
B3["H^2: 干涉 -> |10>"]
B4["测量: 10 (平衡的)"]
B1 --> B2 --> B3 --> B4
end
style C4 fill:#C8E6C9
style B4 fill:#FFCDD2Oracle 作为量子门
Oracle
这总是酉的，因为 XOR 是自身的逆：应用
对于特定函数，
| 函数 | Oracle 电路 | 门数量 |
|---|---|---|
| 恒等 | 0 | |
| 辅助量子比特上的 X | 1 | |
| 从量子比特 | 1 | |
| CNOT( | 2 | |
| 从每个输入到辅助量子比特的 CNOT | ||
| CNOT(0, anc) + X(anc) | 2 |
任何平衡函数都可以表示为
与 Bernstein-Vazirani 算法的联系
Deutsch-Jozsa 电路在结构上与 Bernstein-Vazirani 算法完全相同。Deutsch-Jozsa 区分恒定与平衡，而 Bernstein-Vazirani 解决不同的问题：
Bernstein-Vazirani 问题。 给定对
相同的电路（Hadamard、Oracle、Hadamard、测量）精确产生
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()
# Reverse because pyqpanda3 returns measurement strings with
# qubit 0 as the least significant (rightmost) character.
return list(counts.keys())[0][::-1]
# 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预期输出：
=== 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注意秘密
与其他量子算法的联系
Deutsch-Jozsa 引入的技术贯穿整个量子计算：
mermaid
graph TD
A["Deutsch-Jozsa<br/>(相位回踢)"] --> B["Bernstein-Vazirani<br/>(秘密字符串)"]
A --> C["Simon 算法<br/>(周期寻找)"]
C --> D["Shor 算法<br/>(因数分解)"]
A --> E["Grover 算法<br/>(振幅放大)"]
A --> F["量子相位估计"]
style A fill:#1565C0,color:#fff
style B fill:#42A5F5,color:#fff
style C fill:#42A5F5,color:#fff
style D fill:#1B5E20,color:#fff
style E fill:#1B5E20,color:#fff
style F fill:#42A5F5,color:#fff- 相位回踢是量子相位估计中使用的相同机制，是 Shor 因数分解算法的基础。
- Hadamard 变换用于创建叠加和执行干涉，在几乎所有量子算法中使用。
- 基于 Oracle 的算法（Grover、Simon）遵循在叠加中查询黑盒函数的相同模式。
- 相长/相消干涉放大正确答案在 Grover 的振幅放大中出现。
局限性与实际考虑
概率性经典算法。 尽管最坏情况经典复杂度为
Oracle 构建成本。 在实践中，必须有人构建 Oracle 电路。如果 Oracle 需要
确定性量子优势。 与随机化经典算法不同，量子算法以概率 1 给出正确答案（无错误）。这在量子算法中很少见——大多数（如 Grover）有小的错误概率。
噪声敏感性。 在有噪声的硬件上，恒定 Oracle 可能产生非零测量结果，导致错误的"平衡"判定。需要错误缓解或多次采样的多数投票。
资源总结
| 资源 | Deutsch-Jozsa |
|---|---|
| 量子比特 | |
| Oracle 查询 | 1 |
| Hadamard 门 | |
| 总门数（奇偶校验 Oracle） | |
| 电路深度 | |
| 测量采样次数 | 1（确定性的） |
该算法是确定性的（正确概率为 1），只需单次采样，使用线性数量的门。