Quantum Majority Vote
Publikation: Bidrag til bog/antologi/rapport › Konferenceabstrakt i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 403 KB, PDF-dokument
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}ⁿ → {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⁴ log n) where n is the number of input qubits.
We also consider the more general problem of computing any symmetric and equivariant Boolean function f: {0,1}ⁿ → {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⁴ log n) where n is the number of input qubits.
Originalsprog | Engelsk |
---|---|
Titel | 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
Antal sider | 1 |
Forlag | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Publikationsdato | 2023 |
Artikelnummer | 29 |
ISBN (Elektronisk) | 978-3-95977-263-1 |
DOI | |
Status | Udgivet - 2023 |
Begivenhed | 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) - MIT, Cambridge, MASS, USA Varighed: 10 jan. 2023 → 13 jan. 2023 |
Konference
Konference | 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
---|---|
Lokation | MIT |
Land | USA |
By | Cambridge, MASS |
Periode | 10/01/2023 → 13/01/2023 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 251 |
ISSN | 1868-8969 |
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
Ingen data tilgængelig
ID: 337688849