量子并行性

把预言机 $U_f$ 作用在均匀叠加态上：

$U_f(\frac{1}{\sqrt{2^n}}{\sum }_x|x⟩|0⟩)=\frac{1}{\sqrt{2^n}}{\sum }_x|x⟩|f(x)⟩,$

一次操作就在振幅中同时携带了所有 $2^n$ 个函数值——这一现象称为量子并行性。

要点

• 它不是免费的：直接量子测量只能随机抽到一个 $(x,f(x))$，与经典随机查询无异。并行写入的价值只有通过干涉把全局性质（周期、对称性、承诺问题的答案）压到少数测量结果上才能兑现——Deutsch-Jozsa、Simon 算法、QFT 都是这一模式。
• 量子加速的正确心法是”叠加 → 干涉 → 读出”，而非”同时计算所有输入”。加速能否获得由查询复杂度下界（多项式方法、对抗方法）严格刻画。
• 并行性的物质基础是指数维希尔伯特空间；其代价是态难以经典模拟。

关联词条

• 概念：叠加态、Hadamard 门、量子预言机、相位反冲
• 算法：Deutsch-Jozsa 算法、Simon 算法

取材：量子计算概述、Deutsch-Jozsa 算法。

参考文献

• Nielsen & Chuang.《量子计算与量子信息》第 1 章（量子并行性，§1.4）.
• R. Cleve, A. Ekert, C. Macchiavello, M. Mosca. Quantum Algorithms Revisited. Proc. R. Soc. Lond. A 454, 339 (1998). arXiv:quant-ph/9708016