2022/11/21 by Harry Buhrman, Buhrman, Harry, Noah Linden +7 · 1 voice · 3 citations
#quant-ph #math.RT
paper · pdf · doi:10.48550/arxiv.2211.11729
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⟩ ⊗ … ⊗ |ψn⟩ where each qubit is in one of two orthogonal states |ψ⟩ or |ψ^⊥⟩, output the majority state. We show that an optimal algorithm for this problem achieves worst-case fidelity of 1/2 + Θ(1/√(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 → \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(n4 log n) where n is the number of input qubits.