2016/12/15 by Tommaso F. Demarie, Yingkai Ouyang, Joseph F. Fitzsimons · 11 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Basis (linear algebra) #Bounded function #Computability, Logic, AI Algorithms #Computation #Computer science #Correctness #Electronic circuit #Mathematical analysis #Mathematics #Outcome (game theory) #Polynomial #Polynomial hierarchy #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum computer #Quantum mechanics #Theoretical computer science #Time complexity #cs.CC #cs.CR #quant-ph
paper · pdf · doi:10.1103/physreva.97.042319
published in Physical Review A 97(4) (American Physical Society) · 5 pages, comments welcome!
arxiv created 2016/12/15 · openalex publication_date 2018/04/11 · arxiv updated 2018/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We consider the task of verifying the correctness of quantum computation for a restricted class of circuits which contain at most two basis changes. This contains circuits giving rise to the second level of the Fourier hierarchy, the lowest level for which there is an established quantum advantage. We show that when the circuit has an outcome with probability at least the inverse of some polynomial in the circuit size, the outcome can be checked in polynomial time with bounded error by a completely classical verifier. This verification procedure is based on random sampling of computational paths and is only possible given knowledge of the likely outcome.