Document Open Access Logo

Robust and Space-Efficient Dual Adversary Quantum Query Algorithms

Authors Michael Czekanski, Shelby Kimmel, R. Teal Witter

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.36.pdf
  • Filesize: 0.76 MB
  • 19 pages

Document Identifiers

Author Details

Michael Czekanski
  • Department of Statistics and Data Science, Cornell University, Ithaca, NY, USA
Shelby Kimmel
  • Department of Computer Science, Middlebury College, VT, USA
R. Teal Witter
  • Department of Computer Science and Engineering, New York University, Brooklyn, NY, USA

Funding

  • Kimmel, Shelby: sponsored by the U.S. Army Research Office and this work was accomplished under Grant Number W911NF-20-1-0327. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
  • Witter, R. Teal: supported by NSF No. 1922658 and 1916505.

Acknowledgements

We thank Stacey Jeffery for elucidating discussions.

Cite As Get BibTex

Michael Czekanski, Shelby Kimmel, and R. Teal Witter. Robust and Space-Efficient Dual Adversary Quantum Query Algorithms. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.36

Abstract

The general adversary dual is a powerful tool in quantum computing because it gives a query-optimal bounded-error quantum algorithm for deciding any Boolean function. Unfortunately, the algorithm uses linear qubits in the worst case, and only works if the constraints of the general adversary dual are exactly satisfied. The challenge of improving the algorithm is that it is brittle to arbitrarily small errors since it relies on a reflection over a span of vectors. We overcome this challenge and build a robust dual adversary algorithm that can handle approximately satisfied constraints. As one application of our robust algorithm, we prove that for any Boolean function with polynomially many 1-valued inputs (or in fact a slightly weaker condition) there is a query-optimal algorithm that uses logarithmic qubits. As another application, we prove that numerically derived, approximate solutions to the general adversary dual give a bounded-error quantum algorithm under certain conditions. Further, we show that these conditions empirically hold with reasonable iterations for Boolean functions with small domains. We also develop several tools that may be of independent interest, including a robust approximate spectral gap lemma, a method to compress a general adversary dual solution using the Johnson-Lindenstrauss lemma, and open-source code to find solutions to the general adversary dual.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Quantum query complexity
Keywords
  • Quantum Computing
  • Robust Quantum Algorithms
  • Johnson-Lindenstrauss Lemma
  • Span Programs
  • Query Complexity
  • Space Complexity

Metrics

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

Related Versions

Supplementary Materials

References

  1. Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):1-9, 2021. Google Scholar
  2. Andris Ambainis. Quantum lower bounds by quantum arguments. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 636-643, 2000. Google Scholar
  3. Noel T Anderson, Jay-U Chung, Shelby Kimmel, Da-Yeon Koh, and Xiaohan Ye. Improved quantum query complexity on easier inputs. arXiv preprint, 2023. URL: https://arxiv.org/abs/2303.00217.
  4. Jeongho Bang, Junghee Ryu, Seokwon Yoo, Marcin Pawłowski, and Jinhyoung Lee. A strategy for quantum algorithm design assisted by machine learning. New Journal of Physics, 16(7):073017, 2014. Google Scholar
  5. Howard Barnum, Michael Saks, and Mario Szegedy. Quantum query complexity and semi-definite programming. In 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings., pages 179-193. IEEE, 2003. Google Scholar
  6. 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. Google Scholar
  7. Salman Beigi and Leila Taghavi. Quantum Speedup Based on Classical Decision Trees. arXiv, September 2019. URL: https://arxiv.org/abs/1905.13095.
  8. Salman Beigi and Leila Taghavi. Span Program for Non-binary Functions. arXiv, May 2019. URL: https://arxiv.org/abs/1805.02714.
  9. Aleksandrs Belovs. Learning-graph-based quantum algorithm for k-distinctness. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 207-216. IEEE, 2012. Google Scholar
  10. Aleksandrs Belovs and Duyal Yolcu. One-way ticket to las vegas and the quantum adversary. arXiv preprint, 2023. URL: https://arxiv.org/abs/2301.02003.
  11. Chris Cade, Ashley Montanaro, and Aleksandrs Belovs. Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness. Quantum Information & Computation, 18(1-2):18-50, February 2018. Google Scholar
  12. Titouan Carette, Mathieu Laurière, and Frédéric Magniez. Extended learning graphs for triangle finding. Algorithmica, 82(4):980-1005, 2020. Google Scholar
  13. Giuseppe Carleo, Ignacio Cirac, Kyle Cranmer, Laurent Daudet, Maria Schuld, Naftali Tishby, Leslie Vogt-Maranto, and Lenka Zdeborová. Machine learning and the physical sciences. Reviews of Modern Physics, 91(4):045002, 2019. Google Scholar
  14. Andrew Childs. Lecture notes on quantum algorithms, 2022. URL: https://www.cs.umd.edu/~amchilds/qa/qa.pdf.
  15. Andrew M Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 59-68, 2003. Google Scholar
  16. R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969):339-354, January 1998. URL: https://doi.org/10.1098/rspa.1998.0164.
  17. Michael Czekanski, Shelby Kimmel, and R. Teal Witter. Robust and space-efficient dual adversary quantum query algorithms, 2023. URL: https://arxiv.org/abs/2306.15040.
  18. Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithms, 22(1):60-65, 2003. Google Scholar
  19. J Niel De Beaudrap, Richard Cleve, John Watrous, et al. Sharp quantum versus classical query complexity separations. Algorithmica, 34(4):449-461, 2002. Google Scholar
  20. Kai DeLorenzo, Shelby Kimmel, and R. Teal Witter. Applications of the Quantum Algorithm for st-Connectivity. In Wim van Dam and Laura Mancinska, editors, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), volume 135 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:14, Dagstuhl, Germany, 2019. Schloss Dagstuhlendash Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.TQC.2019.6.
  21. Steven Diamond and Stephen Boyd. Cvxpy: A python-embedded modeling language for convex optimization. The Journal of Machine Learning Research, 17(1):2909-2913, 2016. Google Scholar
  22. Lijun Ding, Alp Yurtsever, Volkan Cevher, Joel A Tropp, and Madeleine Udell. An optimal-storage approach to semidefinite programming using approximate complementarity. SIAM Journal on Optimization, 31(4):2695-2725, 2021. Google Scholar
  23. Simon Foucart, Holger Rauhut, Simon Foucart, and Holger Rauhut. An invitation to compressive sensing. Springer, 2013. Google Scholar
  24. Katsuki Fujisawa, Masakazu Kojima, Kazuhide Nakata, and Makoto Yamashita. Sdpa (semidefinite programming algorithm) user’s manual—version 6.2. 0. Department of Mathematical and Com-puting Sciences, Tokyo Institute of Technology. Research Reports on Mathematical and Computing Sciences Series B: Operations Research, 2002. Google Scholar
  25. Dmitry Gavinsky, Julia Kempe, and Ronald De Wolf. Strengths and weaknesses of quantum fingerprinting. In 21st Annual IEEE Conference on Computational Complexity (CCC'06), pages 8-pp. IEEE, 2006. Google Scholar
  26. Lov K. Grover. Quantum Mechanics Helps in Searching for a Needle in a Haystack. Physical Review Letters, 79(2):325-328, July 1997. URL: https://doi.org/10.1103/PhysRevLett.79.325.
  27. Aram W Harrow, Ashley Montanaro, and Anthony J Short. Limitations on quantum dimensionality reduction. International Journal of Quantum Information, 13(04):1440001, 2015. Google Scholar
  28. Peter Hoyer, Troy Lee, and Robert Spalek. Negative weights make adversaries stronger. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 526-535, 2007. Google Scholar
  29. IBM. The IBM quantum development roadmap, 2022. URL: https://www.ibm.com/quantum/roadmap.
  30. Tsuyoshi Ito and Stacey Jeffery. Approximate Span Programs. Algorithmica, 81(6):2158-2195, June 2019. URL: https://doi.org/10.1007/s00453-018-0527-1.
  31. Stacey Jeffery. Span programs and quantum space complexity. arXiv preprint, 2019. URL: https://arxiv.org/abs/1908.04232.
  32. Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum algorithm for path-edge sampling. arXiv preprint, 2023. URL: https://arxiv.org/abs/2303.03319.
  33. Stacey Jeffery and Sebastian Zur. Multidimensional quantum walks, with application to k-distinctness. arXiv preprint, 2022. URL: https://arxiv.org/abs/2208.13492.
  34. William B Johnson and Joram Lindenstraus. Extensions of lipschitz mappings into a hilbert space. Contemp. Math., 26:189-206, 1984. Google Scholar
  35. Daniel M Kane and Jelani Nelson. Sparser johnson-lindenstrauss transforms. Journal of the ACM (JACM), 61(1):1-23, 2014. Google Scholar
  36. Mauricio Karchmer and Avi Wigderson. On span programs. In [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 102-111. IEEE, 1993. Google Scholar
  37. A. Yu Kitaev. Quantum measurements and the Abelian Stabilizer Problem. arXiv, November 1995. URL: https://arxiv.org/abs/quant-ph/9511026.
  38. K. G. Larsen and J. Nelson. Optimality of the Johnson-Lindenstrauss Lemma. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 633-638, October 2017. URL: https://doi.org/10.1109/FOCS.2017.64.
  39. Kasper Green Larsen and Jelani Nelson. Optimality of the johnson-lindenstrauss lemma. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 633-638. IEEE, 2017. Google Scholar
  40. Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy. Quantum Query Complexity of State Conversion. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 344-353, October 2011. URL: https://doi.org/10.1109/FOCS.2011.75.
  41. Daniel Nagaj, Pawel Wocjan, and Yong Zhang. Fast amplification of qma. arXiv preprint, 2009. URL: https://arxiv.org/abs/0904.1549.
  42. Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1):4213, 2014. Google Scholar
  43. Ben W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 544-551, October 2009. URL: https://doi.org/10.1109/FOCS.2009.55.
  44. Ben W. Reichardt. Reflections for quantum query algorithms. In Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, pages 560-569. Society for Industrial and Applied Mathematics, January 2011. URL: https://doi.org/10.1137/1.9781611973082.44.
  45. Ben W Reichardt and Robert Spalek. Span-program-based quantum algorithm for evaluating formulas. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 103-112, 2008. Google Scholar
  46. B.W. Reichardt. Span programs are equivalent to quantum query algorithms. SIAM Journal on Computing, 43(3):1206-1219, 2014. URL: https://doi.org/10.1137/100792640.
  47. Anthony Man-Cho So, Yinyu Ye, and Jiawei Zhang. A unified theorem on sdp rank reduction. Mathematics of Operations Research, 33(4):910-920, 2008. Google Scholar
  48. Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM review, 38(1):49-95, 1996. Google Scholar
  49. Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. Google Scholar
  50. Zaiwen Wen, Donald Goldfarb, and Wotao Yin. Alternating direction augmented lagrangian methods for semidefinite programming. Mathematical Programming Computation, 2(3-4):203-230, 2010. Google Scholar
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