LIPIcs.CCC.2022.5.pdf
- Filesize: 0.88 MB
- 19 pages
Document
Quantum Search-To-Decision Reductions and the State Synthesis Problem
Authors
Sandy Irani 
,
Chinmay Nirkhe ,
Henry Yuen
-
Part of:
Volume:
37th Computational Complexity Conference (CCC 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computational Complexity Conference (CCC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-07-11
File
Document Identifiers
Author Details
- Department of Computer Science, University of California, Berkeley, CA, USA
- Challenge Institute for Quantum Computation, University of California, Berkeley, CA, USA
Acknowledgements
SI, CN, and HY were participants in the Simons Institute for the Theory of Computing Summer Cluster on Quantum Compuatation. Additionally, we thank Aram Harrow and Zeph Landau for insightful discussions.
Cite AsGet BibTex
Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. Quantum Search-To-Decision Reductions and the State Synthesis Problem. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CCC.2022.5
https://doi.org/10.4230/LIPIcs.CCC.2022.5
Abstract
It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the de facto computational task to study in complexity theory. In this work, we explore search-to-decision reductions for quantum search problems, wherein a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state. In particular, we focus on search-to-decision reductions for QMA, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a QMA problem up to inverse polynomial precision by making one query to a PP decision oracle. We complement this result by showing that QMA-search does not reduce to QMA-decision in polynomial-time, relative to a quantum oracle.
We also explore the more general state synthesis problem, in which the goal is to efficiently synthesize a target state by making queries to a classical oracle encoding the state. We prove that there exists a classical oracle with which any quantum state can be synthesized to inverse polynomial precision using only one oracle query and to inverse exponential precision using two oracle queries. This answers an open question of Aaronson [Aaronson, 2016], who presented a state synthesis algorithm that makes O(n) queries to a classical oracle to prepare an n-qubit state, and asked if the query complexity could be made sublinear.
Subject Classification
ACM Subject Classification
- Theory of computation → Quantum computation theory
Keywords
- Search-to-decision
- state synthesis
- quantum computing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Scott Aaronson. The complexity of quantum states and transformations: from quantum money to black holes. arXiv preprint, 2016. URL: http://arxiv.org/abs/1607.05256.
- Scott Aaronson. Open problems related to quantum query complexity, 2021. URL: http://arxiv.org/abs/2109.06917.
-
Scott Aaronson and Greg Kuperberg. Quantum versus classical proofs and advice. Theory OF Computing, 3:129-157, 2007.
- Dorit Aharonov, Michael Ben-Or, Fernando G. S. L. Brandao, and Or Sattath. The pursuit of uniqueness: Extending Valiant-Vazirani theorem to the probabilistic and quantum settings, 2008. URL: http://arxiv.org/abs/0810.4840.
- Man-Duen Choi. Completely positive linear maps on complex matrices. Linear Algebra and its Applications, 10(3):285-290, 1975. URL: https://doi.org/10.1016/0024-3795(75)90075-0.
- Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman. The importance of the spectral gap in estimating ground-state energies, 2020. URL: http://arxiv.org/abs/2007.11582.
- Bill Fefferman and Cedric Lin. Quantum Merlin Arthur with Exponentially Small Gap, 2016. URL: http://arxiv.org/abs/1601.01975.
- Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. Quantum search-to-decision reductions and the state synthesis problem, 2021. URL: http://arxiv.org/abs/2111.02999.
- A. Jamiołkowski. Linear transformations which preserve trace and positive semidefiniteness of operators. Reports on Mathematical Physics, 3(4):275-278, 1972. URL: https://doi.org/10.1016/0034-4877(72)90011-0.
-
Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi. Classical and quantum computation. Number 47 in Graduate Studies in Mathematics. American Mathematical Soc., 2002.
- William Kretschmer. Quantum pseudorandomness and classical complexity. arXiv preprint, 2021. URL: http://arxiv.org/abs/2103.09320.
-
Chris Marriott and J. Watrous. Quantum Arthur–Merlin games. computational complexity, 14:122-152, 2004.
-
Chinmay Nirkhe, Umesh Vazirani, and Henry Yuen. Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Leibniz International Proceedings in Informatics (LIPIcs), pages 91:1-91:11, 2018.
-
Gregory Rosenthal and Henry Yuen. Interactive proofs for synthesizing quantum states and unitaries. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.