Quantum majority vote
MATH CS Seminar Featuring Maris Ozols, ASSISTANT PROFESSOR UNIVERSITY OF AMSTERDAM QuSoft
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 ∣ψ_i⟩ 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. ...