LIPIcs.TQC.2016.7.pdf
- Filesize: 482 kB
- 14 pages
Document
The Structure of Promises in Quantum Speedups
Author
-
Part of:
Volume:
11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)
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: 2016-09-22
Cite As Get BibTex
Shalev Ben-David. The Structure of Promises in Quantum Speedups. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.TQC.2016.7
Abstract
In 1998, Beals, Buhrman, Cleve, Mosca, and de Wolf showed that no super-polynomial quantum speedup is possible in the query complexity setting unless there is a promise on the input. We examine several types of "unstructured" promises, and show that they also are not compatible with super-polynomial quantum speedups. We conclude that such speedups are only possible when the input is known to have some structure. Specifically, we show that there is a polynomial relationship of degree 18 between D(f) and Q(f) for any Boolean function f defined on permutations (elements of [n]^n in which each alphabet element occurs exactly once). More generally, this holds for all f defined on orbits of the symmetric group action (which acts on an element of [M]^n by permuting its entries). We also show that any Boolean function f defined on a "symmetric" subset of the Boolean hypercube has a polynomial relationship between R(f) and Q(f) - although in that setting, D(f) may be exponentially larger.
Subject Classification
Keywords
- Quantum computing
- quantum query complexity
- decision tree complexity
- lower bounds
- quantum adversary method
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. arXiv preprint http://arxiv.org/abs/arXiv:0911.0996, 2009.
- Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. In Proceedings of the 47th ACM Symposium on Theory of Computing (STOC 2015), pages 307-316, 2015. URL: http://dx.doi.org/10.1145/2746539.2746547.
-
Scott Aaronson and Shalev Ben-David. Sculpting quantum speedups. arXiv preprint http://arxiv.org/abs/arXiv:1512.04016, 2015.
- Andris Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750-767, 2002. URL: http://dx.doi.org/10.1006/jcss.2002.1826.
- Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778-797, 2001. http://arxiv.org/abs/arXiv:quant-ph/9802049, URL: http://dx.doi.org/10.1145/502090.502097.
-
Joe P Buhler, Hendrik W Lenstra Jr, and Carl Pomerance. Factoring integers with the number field sieve. In The development of the number field sieve, pages 50-94. Springer, 1993.
- Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21-43, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00144-X.
-
Richard Cleve. The query complexity of order-finding. Information and Computation, 192(2):162-171, 2004.
-
Ashwin Nayak. Inverting a permutation is as hard as unordered search. arXiv preprint http://arxiv.org/abs/arXiv:1007.2899, 2010.
- Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484-1509, 1997. URL: http://arxiv.org/abs/quant-ph/9508027.
- Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing, 26(5):1474-1483, 1997. URL: http://dx.doi.org/10.1137/S0097539796298637.