论文标题
量子多数投票
Quantum majority vote
论文作者
论文摘要
多数投票是扩大在计算机科学及其他方面广泛使用的正确结果的基本方法。尽管它可以扩增具有经典输出的量子设备的正确性，但尚不清楚量子输出的类似程序。我们将量子多数投票作为以下任务引入：给定产品状态$ |ψ_1\ rangle \ otimes \ dots \ otimes \ otimes |ψ_n\ rangle $，其中每个量子位于两个正交状态$ | |ψ\ rangle $或$ | | 〜perp \ perp \ perp \ thep \ ar \ rangle $中，输出有多于多数元。我们表明，此问题的最佳算法达到了$ 1/2 +θ（1/\ sqrt {n}）$的最差案例保真度。根据承诺至少$ 2/3 $的输入量子位处于多数状态，保真度增加到$1-θ（1/n）$，并接近$ 1 $ $ n $的$ 1 $。 我们还考虑了在未知的量子基础上计算任何对称和均衡的布尔函数$ f：\ {0,1 \}^n \ to \ {0,1 \} $的更普遍的问题，并表明我们量子多数票算法的概括是对此任务的最佳选择。通用算法的最佳参数及其最差的保真度可以通过大小$ o（n）$的简单线性程序来确定。算法的时间复杂性为$ O（n^4 \ log n）$，其中$ n $是输入量子数的数量。
Majority vote is a basic method for amplifying correct outcomes that is widely used in computer science and beyond. While it can amplify the correctness of a quantum device with classical output, the analogous procedure for quantum output is not known. We introduce quantum majority vote as the following task: given a product state $|ψ_1\rangle \otimes \dots \otimes |ψ_n\rangle$ where each qubit is in one of two orthogonal states $|ψ\rangle$ or $|ψ^\perp\rangle$, output the majority state. We show that an optimal algorithm for this problem achieves worst-case fidelity of $1/2 + Θ(1/\sqrt{n})$. Under the promise that at least $2/3$ of the input qubits are in the majority state, the fidelity increases to $1 - Θ(1/n)$ and approaches $1$ as $n$ increases. We also consider the more general problem of computing any symmetric and equivariant Boolean function $f: \{0,1\}^n \to \{0,1\}$ in an unknown quantum basis, and show that a generalization of our quantum majority vote algorithm is optimal for this task. The optimal parameters for the generalized algorithm and its worst-case fidelity can be determined by a simple linear program of size $O(n)$. The time complexity of the algorithm is $O(n^4 \log n)$ where $n$ is the number of input qubits.
