Quantum majority vote

Understand

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 $|\psi_1\rangle \otimes \dots \otimes |\psi_n\rangle$ where each qubit is in one of two orthogonal states $|\psi\rangle$ or $|\psi^\perp\rangle$, output the majority state.
• We show that an optimal algorithm for this problem achieves worst-case fidelity of $1/2 + \Theta(1/\sqrt{n})$.