Abstract
We show that quantum query complexity satisfies a strong direct product theorem. This means that computing k copies of a function with fewer than k times the quantum queries needed to compute one copy of the function implies that the overall success probability will be exponentially small in k. For a boolean function f, we also show an XOR lemma—computing the parity of k copies of f with fewer than k times the queries needed for one copy implies that the advantage over random guessing will be exponentially small. We do this by showing that the multiplicative adversary method, which inherently satisfies a strong direct product theorem, characterizes bounded-error quantum query complexity. In particular, we show that the multiplicative adversary bound is always at least as large as the additive adversary bound, which is known to characterize bounded-error quantum query complexity.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Andris Ambainis (2002) Quantum Lower Bounds by Quantum Arguments. Journal of Computer and System Sciences 64(4): 750–767
Andris Ambainis (2006) Polynomial degree vs. quantum query complexity. Journal of Computer and System Sciences 72(2): 220–238
Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani (2010a) The quantum query complexity of certification. Quantum Information and Computation 10: 181–188
Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, Shengyu Zhang (2010b) Any AND-OR Formula of Size N Can Be Evaluated in Time N 1/2+o(1) on a Quantum Computer. SIAM Journal on Computing 39(6): 2513
Andris Ambainis, Loïck Magnin, Martin Roetteler, & Jérémie Roland (2011). Symmetry-assisted adversaries for quantum state generation. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 167–177. IEEE Computer Society.
Andris Ambainis, Robert Špalek & Ronald de Wolf (2006). A new quantum lower bound method with applications to direct product theorems and time-space tradeoffs. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 618–633. ACM. ISBN 1-59593-134-1.
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca & Ronald de Wolf (1998). Quantum Lower Bounds by Polynomials. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 352. IEEE Computer Society. ISBN 0-8186-9172-7.
Aleksandrs Belovs (2011). Personal communication.
Rajendra Bhatia (2007). Positive definite matrices. Princeton University Press.
Harry Buhrman, de Ronald Wolf (2002) Complexity measures and decision tree complexity: A survey. Theoretical Computer Science 288(1): 21–43
Andrew M. Childs, Richard Cleve, Stephen P. Jordan, David Yeung (2009) Discrete-query quantum algorithm for NAND trees. Theory of Computing 5: 119–123
Thomas M. Cover & Joy A. Thomas (2006). Elements of Information Theory. Wiley.
Andrew Drucker (2011). Improved Direct Product Theorems for Randomized Query Complexity. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 1–11. IEEE Computer Society.
Edward Farhi, Jeffrey Goldstone, Sam Gutmann (2008) A Quantum Algorithm for the Hamiltonian NAND Tree. Theory of Computing 4: 169–190
Oded Goldreich, Noam Nisan & Avi Wigderson (2011). On Yao’s XOR-Lemma. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, volume 6650 of Lecture Notes in Computer Science, 273–301. Springer.
Peter Høyer, Troy Lee & Robert Špalek (2007). Negative weights make adversaries stronger. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 526–535. ACM. ISBN 978-1-59593-631-8.
Rahul Jain, Attila Pereszlenyi & Penghui Yao (2012). A direct product theorem for bounded-round public coin randomized communication complexity. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society.
Hartmut Klauck, Robert Špalek, de Ronald Wolf (2007) Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. SIAM Journal on Computing 36(5): 1472–1493
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek & Mario Szegedy (2011). Quantum query complexity of state conversion. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, 344–353. IEEE Computer Society.
Troy Lee & Jérémie Roland (2012). A strong direct product theorem for quantum query complexity. In Proceedings of the 27th IEEE Conference on Computational Complexity, 234–246. IEEE Computer Society.
Troy Lee, Adi Shraibman & Robert Špalek (2008). A Direct Product Theorem for Discrepancy. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 71–80. IEEE Computer Society.
Nati Linial, Shahar Mendelson, Gideon Schechtman, Adi Shraibman (2007) Complexity measures of sign matrices. Combinatorica 27: 439–463
Nati Linial, Adi Shraibman (2009) Lower bounds in communication complexity based on factorization norms. Random Structures and Algorithms 34(3): 368–394
Michael A. Nielsen & Isaac L. Chuang (2000). Quantum Computation and Quantum Information. Cambridge University Press.
Ran Raz (1998) A Parallel Repetition Theorem. SIAM Journal on Computing 27(3): 763–803
Ben W. Reichardt (2009). Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 544–551. IEEE Computer Society. ISSN 0272-5428.
Ben W. Reichardt (2011). Reflections for quantum query algorithms. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 560–569. SIAM.
Ben W. Reichardt & Robert Špalek (2008). Span-program-based quantum algorithm for evaluating formulas. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 103–112. ACM. ISBN 978-1-60558-047-0.
Ronen Shaltiel (2003) Towards proving strong direct product theorems. Computational Complexity 12(1-2): 1–22
Alexander A. Sherstov (2011). Strong direct product theorems for quantum communication and query complexity. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 41–50. ACM.
Robert Špalek (2008). The Multiplicative Quantum Adversary. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 237–248. IEEE Computer Society. ISBN 978-0-7695-3169-4.
Falk Unger (2009). A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 221–229. IEEE Computer Society.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lee, T., Roland, J. A strong direct product theorem for quantum query complexity. comput. complex. 22, 429–462 (2013). https://doi.org/10.1007/s00037-013-0066-8
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-013-0066-8