Document Open Access Logo

Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge

Authors Shalev Ben-David, Robin Kothari

PDF
Thumbnail PDF

File

LIPIcs.TQC.2019.2.pdf
  • Filesize: 0.53 MB
  • 23 pages

Document Identifiers

Author Details

Shalev Ben-David
  • University of Waterloo, Waterloo, ON, Canada
Robin Kothari
  • Quantum Architectures and Computation (QuArC) group, Microsoft Research, Redmond, WA, USA

Acknowledgements

We thank Scott Aaronson, Mika Göös, John Watrous, and Ronald de Wolf for helpful conversations about this work. Most of this work was performed while the first author was at the Massachusetts Institute of Technology and the University of Maryland and the second author was at the Massachusetts Institute of Technology. This work was partially supported by NSF grant CCF-1629809.

Cite As Get BibTex

Shalev Ben-David and Robin Kothari. Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.TQC.2019.2

Abstract

We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close to |0> on a 0-input and a state close to |1> on a 1-input, a "quantum distinguishing algorithm" can output any state, as long as the output states for any 0-input and 1-input are distinguishable. 
Using this measure, we establish a new relationship in query complexity: For all total functions f, Q_0(f)=O~(Q(f)^5), where Q_0(f) and Q(f) denote the zero-error and bounded-error quantum query complexity of f respectively, improving on the previously known sixth power relationship.
We also define a query measure based on quantum statistical zero-knowledge proofs, QSZK(f), which is at most Q(f). We show that QD(f) in fact lower bounds QSZK(f) and not just Q(f). QD(f) also upper bounds the (positive-weights) adversary bound, which yields the following relationships for all f: Q(f) >= QSZK(f) >= QD(f) = Omega(Adv(f)). This sheds some light on why the adversary bound proves suboptimal bounds for problems like Collision and Set Equality, which have low QSZK complexity.
Lastly, we show implications for lifting theorems in communication complexity. We show that a general lifting theorem for either zero-error quantum query complexity or for QSZK would imply a general lifting theorem for bounded-error quantum query complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • Quantum query complexity
  • quantum algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Scott Aaronson. Quantum certificate complexity. Journal of Computer and System Sciences, 74(3):313-322, 2008. URL: http://dx.doi.org/10.1016/j.jcss.2007.06.020.
  2. Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. In Proceedings of the 48th Symposium on Theory of Computing (STOC 2016), pages 863-876, 2016. URL: http://dx.doi.org/10.1145/2897518.2897644.
  3. Scott Aaronson and Yaoyun Shi. Quantum Lower Bounds for the Collision and the Element Distinctness Problems. Journal of the ACM, 51(4):595-605, 2004. URL: http://dx.doi.org/10.1145/1008731.1008735.
  4. Andris Ambainis. Quantum Lower Bounds by Quantum Arguments. Journal of Computer and System Sciences, 64(4):750-767, June 2002. URL: http://dx.doi.org/10.1006/jcss.2002.1826.
  5. Andris Ambainis. Polynomial Degree vs. Quantum Query Complexity. In Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS 2003), page 230, 2003. URL: http://dx.doi.org/10.1109/SFCS.2003.1238197.
  6. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. Separations in Query Complexity Based on Pointer Functions. In Proceedings of the 48th Symposium on Theory of Computing, STOC '16, pages 800-813, 2016. URL: http://dx.doi.org/10.1145/2897518.2897524.
  7. Howard Barnum, Michael Saks, and Mario Szegedy. Quantum Decision Trees and Semidefinite Programming. Technical report, Los Alamos National Laboratory, 2001. URL: http://permalink.lanl.gov/object/view?what=info:lanl-repo/lareport/LA-UR-01-6417.
  8. Howard Barnum, Michael Saks, and Mario Szegedy. Quantum query complexity and semi-definite programming. In 18th Conference on Computational Complexity (CCC 2003), pages 179-193, 2003. URL: http://dx.doi.org/10.1109/CCC.2003.1214419.
  9. 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. URL: http://dx.doi.org/10.1145/502090.502097.
  10. Aleksandrs Belovs and Robert Spalek. Adversary lower bound for the k-sum problem. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 323-328, 2013. URL: http://dx.doi.org/10.1145/2422436.2422474.
  11. Shalev Ben-David and Robin Kothari. Randomized Query Complexity of Sabotaged and Composed Functions. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 60:1-60:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.60.
  12. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing (special issue on quantum computing), 26:1510-1523, 1997. URL: http://dx.doi.org/10.1137/S0097539796300933.
  13. Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan. On the Power of Statistical Zero Knowledge. In 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 708-719, October 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.71.
  14. Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. Bounds for Small-Error and Zero-Error Quantum Algorithms. In Proceedings of the 40th Symposium on Foundations of Computer Science, FOCS '99, pages 358-368, 1999. URL: http://dx.doi.org/10.1109/SFFCS.1999.814607.
  15. 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.
  16. Lijie Chen. A note on oracle separations for BQP. arXiv preprint, 2016. URL: http://arxiv.org/abs/1605.00619.
  17. Oded Goldreich, Amit Sahai, and Salil Vadhan. Honest-verifier Statistical Zero-knowledge Equals General Statistical Zero-knowledge. In Proceedings of the 30th Symposium on Theory of Computing, STOC '98, pages 399-408, 1998. URL: http://dx.doi.org/10.1145/276698.276852.
  18. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles Are Nonnegative Juntas. SIAM Journal on Computing, 45(5):1835-1869, 2016. URL: http://dx.doi.org/10.1137/15M103145X.
  19. Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic Communication vs. Partition Number. In Proceedings of the 56th Symposium on Foundations of Computer Science (FOCS 2015), pages 1077-1088, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.70.
  20. Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP. In 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 132-143, October 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.21.
  21. Peter Høyer, Troy Lee, and Robert Špalek. Negative weights make adversaries stronger. In Proceedings of the 39th Symposium on Theory of Computing (STOC 2007), pages 526-535, 2007. URL: http://dx.doi.org/10.1145/1250790.1250867.
  22. Raghav Kulkarni and Avishay Tal. On Fractional Block Sensitivity. Chicago Journal of Theoretical Computer Science, 2016(8), July 2016. URL: http://dx.doi.org/10.4086/cjtcs.2016.008.
  23. Sophie Laplante and Frédéric Magniez. Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In Proceedings of the 19th Conference on Computational Complexity, pages 294-304, June 2004. URL: http://dx.doi.org/10.1109/CCC.2004.1313852.
  24. Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy. Quantum query complexity of state conversion. In Proceedings of the 52nd Symposium on Foundations of Computer Science (FOCS 2011), pages 344-353, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.75.
  25. Troy Lee and Jérémie Roland. A strong direct product theorem for quantum query complexity. Computational Complexity, 22(2):429-462, 2013. URL: http://dx.doi.org/10.1007/s00037-013-0066-8.
  26. Sanketh Menda and John Watrous. Oracle Separations for Quantum Statistical Zero-Knowledge. arXiv preprint, 2018. URL: http://arxiv.org/abs/1801.08967.
  27. Gatis Midrijanis. On randomized and quantum query complexities. arXiv preprint, 2005. URL: http://arxiv.org/abs/quant-ph/0501142.
  28. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  29. Ran Raz and Pierre McKenzie. Separation of the Monotone NC Hierarchy. Combinatorica, 19(3):403-435, 1999. URL: http://dx.doi.org/10.1007/s004930050062.
  30. Amit Sahai and Salil Vadhan. A Complete Problem for Statistical Zero Knowledge. Journal of the ACM, 50(2):196-249, March 2003. URL: http://dx.doi.org/10.1145/636865.636868.
  31. Alexander A. Sherstov. Making Polynomials Robust to Noise. In Proceedings of the 44th Symposium on Theory of Computing, STOC '12, pages 747-758, 2012. URL: http://dx.doi.org/10.1145/2213977.2214044.
  32. Robert Špalek and Mario Szegedy. All Quantum Adversary Methods are Equivalent. Theory of Computing, 2(1):1-18, 2006. URL: http://dx.doi.org/10.4086/toc.2006.v002a001.
  33. List of Open Problems in Sublinear Algorithms. Problem 77: Frontiers in Structural Communication Complexity. https://sublinear.info/index.php?title=Open_Problems:77, 2017.
  34. John Watrous. Limits on the Power of Quantum Statistical Zero-Knowledge. In Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS '02, pages 459-468, 2002. Full version available at https://cs.uwaterloo.ca/~watrous/Papers/. URL: http://dx.doi.org/10.1109/SFCS.2002.1181970.
  35. John Watrous. Zero-Knowledge against Quantum Attacks. SIAM Journal on Computing, 39(1):25-58, 2009. URL: http://dx.doi.org/10.1137/060670997.
  36. John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. Available at https://cs.uwaterloo.ca/~watrous/TQI/.
  37. Shengyu Zhang. On the power of Ambainis lower bounds. Theoretical Computer Science, 339(2):241-256, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.01.019.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact