LIPIcs.TQC.2015.1.pdf
- Filesize: 0.82 MB
- 26 pages
Document
Oracles with Costs
Authors
-
Part of:
Volume:
10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-11-04
Cite AsGet BibTex
Shelby Kimmel, Cedric Yen-Yu Lin, and Han-Hsuan Lin. Oracles with Costs. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.TQC.2015.1
https://doi.org/10.4230/LIPIcs.TQC.2015.1
Abstract
While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.
Keywords
- Quantum Algorithms
- Query Complexity
- Amplitude Amplification
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Andris Ambainis. Quantum lower bounds by quantum arguments. In Proc. 32nd ACM STOC, pages 636-643. ACM, 2000.
-
Andris Ambainis. Quantum search with variable times. Theory of Computing Systems, 47(3):786-807, 2010.
-
Andris Ambainis, Ansis Rosmanis, and Dominique Unruh. Quantum attacks on classical proof systems - the hardness of quantum rewinding. arXiv preprint arXiv:1404.6898, 2014.
-
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald De Wolf. Quantum lower bounds by polynomials. Journal of the ACM (JACM), 48(4):778-797, 2001.
-
Aleksandrs Belovs. Learning-graph-based quantum algorithm for k-distinctness. In Proc. IEEE 53rd FOCS, pages 207-216. IEEE Computer Society, 2012.
-
Aleksandrs Belovs and Ansis Rosmanis. On the power of non-adaptive learning graphs. Computational Complexity, 23(2):323-354, 2014.
-
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510-1523, 1997.
-
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. arXiv preprint quant-ph/0005055, 2000.
-
Nicolas J Cerf, Lov K Grover, and Colin P Williams. Nested quantum search and structured problems. Physical Review A, 61(3):032303, 2000.
-
Cătălin Dohotaru and Peter Høyer. Exact quantum lower bound for grover’s problem. Quantum Information and Computation, 9(5-6):533-540, 2009.
-
Mark Ettinger, Peter Høyer, and Emanuel Knill. The quantum query complexity of the hidden subgroup problem is polynomial. Information Processing Letters, 91(1):43-48, 2004.
-
Peter Høyer, Troy Lee, and Robert Špalek. Negative weights make adversaries stronger. In Proc. 39th ACM STOC, pages 526-535, 2007.
-
Troy Lee, Rajat Mittal, Ben W Reichardt, Robert Špalek, and Mario Szegedy. Quantum query complexity of state conversion. In Proc. 52nd IEEE FOCS, pages 344-353. IEEE, 2011.
-
Ashley Montanaro. Quantum search with advice. In Theory of Quantum Computation, Communication, and Cryptography, pages 77-93. Springer, 2011.
-
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, and Luca Trevisan. Quantum lower bound for inverting a permutation with advice. arXiv preprint arXiv:1408.3193, 2014.
-
Theodore J Yoder, Guang Hao Low, and Isaac L Chuang. Fixed-point quantum search with an optimal number of queries. Physical review letters, 113(21):210501, 2014.