Quantum majority vote

MaRDI QIDQ6418024zbMATH OpenFDO

Authors Harry Buhrman, Noah Linden, L. Mančinska, Ashley Montanaro, Maris Ozols

Publication date 21 November 2022

Abstract: 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 $|ps{i}_{1}angleotimesdotsotimes|ps{i}_{n}angle$ where each qubit is in one of two orthogonal states $|psiangle$ or $|ps{i}^{p}erpangle$, output the majority state. We show that an optimal algorithm for this problem achieves worst-case fidelity of $1/2+Theta(1/sqrtn)$. Under the promise that at least $2/3$ of the input qubits are in the majority state, the fidelity increases to $1-Theta(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}o0,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}logn)$ where $n$ is the number of input qubits.

This page was built for publication: Quantum majority vote

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6418024)