设有如下游戏：
用户在心中任意想一个整数 a，满足：
a \in \mathbb{Z}, \quad 0 \le a < 2^n问：如何在尽可能少的询问中确定 a。
该问题可在两种计算模型下讨论：
- 在经典计算机中，可通过二分查找等基础算法逐步确定该数；
- 在量子计算机中，则通过 Bernstein–Vazirani 算法求解问题。
接下来，我们从经典算法出发，逐步引出量子算法思想。
二分查找算法
在经典计算机中，快速查找目标的常用方法是二分查找（Binary Search），适用于有序序列，能在对数时间内完成搜索。
假设有一个递增的连续有序数组：
A = [0, 1, 2, \dots, 2^n - 1]
用户心中选择一个数 a，每次询问用户：“目标是否大于等于某个中间值 m？”根据回答逐步缩小范围，直到唯一确定 a。
二分查找的核心思想是折半搜索：每一步将搜索区间分为两半，只保留可能包含目标的一半，其实现如下：
n = 7 # 数字位数
def binary_search(low = 0, high = 2 ** n - 1):
if low == high:
return low
mid = (low + high + 1) // 2
response = input(f"目标大于等于 {mid} 吗？（1 表示是，0 表示否）: ")
if response == "1":
return binary_search(mid, high)
elif response == "0":
return binary_search(low, mid - 1)
else:
raise ValueError("输入错误，请输入 1 或 0")
if __name__ == "__main__":
print(f"请心中想一个数字，范围 0 ~ {2 ** n - 1}")
result = binary_search()
print(f"答案是 {result}")每次比较后，搜索范围缩小为原来的一半，对于特定的 n 经过 k 次比较后，剩余区间为：
2^n / 2^k
因此搜索次数为 n 次，总体时间复杂度为：
T_{\text{binary}} = O(\log_22^n) = O(n)通常意义上，对于长度为 N 的数组，其时间复杂度有：
T_{\text{binary}} = O(\log N)这种逐步缩小搜索空间、以对数步数确定目标的方式，成为了经典计算机查找问题的最有效策略之一。
按位求解算法
另一种方法是按位逐位确定用户心中整数。算法从最高位到最低位依次询问每一位的取值；通过累加前面已确定的位值，逐步缩小搜索范围。
这与二分查找本质相同：每次比较相当于判断当前区间最高位是 0 还是 1。其实现如下：
n = 7 # 数字位数
def bitwise_search():
bit_values = ["0"] * n
for i in range(n, 0, -1):
reference = 2 ** (i - 1) + int("".join(bit_values), 2)
response = input(f"大于等于 {reference}?（1 表示是，0 表示否）: ")
bit_values[n - i] = response
return "".join(bit_values)
if __name__ == "__main__":
print(f"请心中想一个数字，范围 0 ~ {2 ** n - 1}")
result = bitwise_search()
print(f"答案为 {int(result, 2)}（二进制表示：{result}）")
不难看出，算法对于数值的每一位都需进行一次询问，总共 n 次，即时间复杂度与二分查找法相同，有：
T_{\text{bitwise}}=O(n)Bernstein–Vazirani 算法
事实上，Bernstein–Vazirani 算法与按位求解算法相类似。因为默认分配的量子位初始值为 0，则对需要置 1 的位依次进行 X 操作即可，因此，对二进制数 0100101 有：
X_1 X_4 X_6
基于 Qiskit 的实现有：
from qiskit import QuantumCircuit
from qiskit_aer import Aer
qc = QuantumCircuit(7, 7)
#对于 37，其二进制为 0100101
qc.x([1, 4, 6])
qc.measure(range(7), range(7)) # 测量量子比特并存入经典比特
sim = Aer.get_backend("qasm_simulator")
job = sim.run(qc, shots=1024)
result = job.result()
counts = result.get_counts()
print("结果为：", counts)因为：
\begin{aligned}H H &= I\\H X H &= Z\end{aligned}所以，可以电路等效为：
\begin{aligned}
&X_1 X_4 X_6\\
&= (H_1 H_1) (H_4 H_4) (H_6 H_6) X_1 X_4 X_6 (H_1 H_1) (H_4 H_4) (H_6 H_6) \\
&= (H_1 H_1 X_1 H_1 H_1) (H_4 H_4 X_4 H_4 H_4) (H_6 H_6 X_6 H_6 H_6) \\
&= (H_1 Z_1 H_1) (H_4 Z_4 H_4) (H_6 Z_6 H_6) \\
&= H_1 H_4 H_6 Z_1 Z_4 Z_6 H_1 H_4 H_6 \\
&= (H_1 H_2 \dots H_7) Z_1 Z_4 Z_6 (H_1 H_2 \dots H_7)
\end{aligned}即有，将所有量子比特做 H 操作，形成叠加态，并对需要做相位变化的量子比特做 Z 操作，最后再对全体量子比特做 H 操作，得到最终解。
进一步的，对于任意
\ket\psi=\alpha\ket0+\beta\ket1
有：
\begin{aligned}
(Z \otimes I)\ket{\psi}\ket{-}
&= Z\ket{\psi}\ket{-} \\[4pt]
&= (\alpha\ket{0}-\beta\ket{1})\ket{-} \\[4pt]
&= \alpha\ket{0}\ket{-} - \beta\ket{1}\ket{-} \\[4pt]
&= \alpha\ket{0}\ket{-} + \frac{\beta}{\sqrt{2}}\,\ket{1}(\ket{1}-\ket{0}) \\[4pt]
&= \alpha\ket{0}\ket{-} + \frac{\beta}{\sqrt{2}}\,\ket{1}X(\ket{0}-\ket{1}) \\[4pt]
&= \alpha\ket{0}\ket{-} + \beta\ket{1}X\ket{-} \\[4pt]
&= \alpha\,CX\ket{0}\ket{-} + \beta\,CX\ket{1}\ket{-} \\[4pt]
&= CX(\alpha\ket{0}+\beta\ket{1})\ket{-} \\[4pt]
&= CX\ket{\psi}\ket{-}
\end{aligned}不难发现，通常情况下，CX 门会使两个量子产生纠缠，但当目标比特为 |-> 时，CX 门并不会使两个量子产生纠缠，只会把相位”踢回“控制比特，使整个系统仍为可分离态。
因此，基于该特性，可设置辅助量子比特 8，使电路有：
\begin{aligned}
&X_1 X_4 X_6 X_8 H_8\\
&= X_8 (H_1 H_2 \dots H_7 H_8) Z_1 Z_4 Z_6 (H_1 H_2 \dots H_7)\\
&=X_8 (H_1 H_2 \dots H_7 H_8) CX_{18} CX_{48} CX_{68} (H_1 H_2 \dots H_7)
\end{aligned}此即 Bernstein-Vazirani 算法的电路结构，实现了基于量子谕示（Quantum Oracle）函数的数值查找过程。根据推导过程知，该方法基于辅助量子比特实现了相位“踢回”，从而改变控制量子比特，最终实现谕示：
U_f \ket{x}\ket{-} = (-1)^{f_s(x)}\ket{x}\ket{-}其中，BV 函数有：
f_s(x)=s_1x_1 \oplus s_2x_2 \oplus s_3x_3 \cdots \oplus s_nx_n
此算法在一次量子查询中即可获得完整二进制串，时间复杂度为：
T_{BV}=O(1)
发表回复