Document Open Access Logo

Quantum Algorithms for Learning a Hidden Graph

Authors Ashley Montanaro, Changpeng Shao

PDF
Thumbnail PDF

File

LIPIcs.TQC.2022.1.pdf
  • Filesize: 0.74 MB
  • 22 pages

Document Identifiers

Author Details

Ashley Montanaro
  • School of Mathematics, University of Bristol, UK
  • Phasecraft Ltd., Bristol, UK
Changpeng Shao
  • School of Mathematics, University of Bristol, UK

Funding

This paper was supported by the QuantERA ERA-NET Cofund in Quantum Technologies implemented within the European Union’s Horizon 2020 Programme (QuantAlgo project) and EPSRC grants EP/R043957/1 and EP/T001062/1. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 817581).

Acknowledgements

We would like to thank João Doriguello and Ryan Mann for helpful discussions on the topic of this work.

Cite As Get BibTex

Ashley Montanaro and Changpeng Shao. Quantum Algorithms for Learning a Hidden Graph. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.TQC.2022.1

Abstract

We study the problem of learning an unknown graph provided via an oracle using a quantum algorithm. We consider three query models. In the first model ("OR queries"), the oracle returns whether a given subset of the vertices contains any edges. In the second ("parity queries"), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph.
We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model.
A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al. for a "gapped" version of the group testing problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum query complexity
Keywords
  • Quantum algorithms
  • query complexity
  • graphs
  • combinatorial group testing

Metrics

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

References

  1. Scott Aaronson and Daniel Gottesman. Identifying stabilizer states, 2008. URL: http://pirsa.org/08080052/.
  2. Hasan Abasi and Bshouty Nader. On learning graphs with edge-detecting queries. In Algorithmic Learning Theory, pages 3-30. PMLR, 2019. arXiv:1803.10639. Google Scholar
  3. M. Aldridge, O. Johnson, and J. Scarlett. Group testing: An information theory perspective. Foundations and Trends in Communications and Information Theory, 15(3-4):196-392, 2019. arXiv:1902.06002. Google Scholar
  4. Noga Alon and Vera Asodi. Learning a hidden subgraph. SIAM Journal on Discrete Mathematics, 18(4):697-712, 2005. URL: https://doi.org/10.1137/S0895480103431071.
  5. Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov. Learning a hidden matching. SIAM Journal on Computing, 33(2):487-501, 2004. URL: https://doi.org/10.1137/S0097539702420139.
  6. Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf. Efficient quantum algorithms for (gapped) group testing and junta testing. In Proc. 27superscriptth ACM-SIAM Symp. Discrete Algorithms, pages 903-922, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch65.
  7. Andris Ambainis and Ashley Montanaro. Quantum algorithms for search with wildcards and combinatorial group testing. Quantum Information and Computation, 14(5&6), 2014. URL: https://doi.org/10.26421/QIC14.5-6.
  8. Dana Angluin and Jiang Chen. Learning a hidden hypergraph. Journal of Machine Learning Research, 7:2215-2236, 2006. Google Scholar
  9. Dana Angluin and Jiang Chen. Learning a hidden graph using O(log n) queries per edge. Journal of Computer and System Sciences, 74(4):546-556, 2008. URL: https://doi.org/10.1016/j.jcss.2007.06.006.
  10. George K Atia and Venkatesh Saligrama. Boolean compressed sensing and noisy group testing. IEEE Transactions on Information Theory, 58(3):1880-1901, 2012. arXiv:0907.1061. Google Scholar
  11. A. Atıcı and R. Servedio. Improved bounds on quantum learning algorithms. Quantum Information Processing, 4(5):355-386, 2005. quant-ph/0411140. Google Scholar
  12. 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: https://doi.org/10.1145/502090.502097.
  13. Paul Beame, Sariel Har-Peled, Ramamoorthy S. Natarajan, Cyrus Rashtchian, and Makrand Sinha. Edge estimation with independent set oracles. ACM Transactions on Algorithms (TALG), 16(4):1-27, 2020. URL: https://doi.org/10.1145/3404867.
  14. Richard Beigel, Noga Alon, Simon Kasif, Mehmet S. Apaydin, and Lance Fortnow. An optimal procedure for gap closing in whole genome shotgun sequencing. In RECOMB 2001, pages 22-30, 2001. URL: https://doi.org/10.1145/369133.369152.
  15. Aleksandrs Belovs. Quantum algorithms for learning symmetric juntas via the adversary bound. Computational Complexity, 24:255-293, 2015. URL: https://doi.org/10.1007/s00037-015-0099-2.
  16. Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, and Daochen Wang. Symmetries, graph properties, and quantum speedups, 2020. arXiv:2006.12760. Google Scholar
  17. Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411-1473, 1997. URL: https://doi.org/10.1137/S0097539796300921.
  18. Mathilde Bouvel, Vladimir Grebinski, and Gregory Kucherov. Combinatorial search on graphs motivated by bioinformatics applications: a brief survey. In WG 2005: Graph-Theoretic Concepts in Computer Science, pages 16-27, 2005. URL: https://doi.org/10.1007/11604686_2.
  19. G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. Quantum Computation and Quantum Information: A Millennium Volume, pages 53-74, 2002. quant-ph/0005055. Google Scholar
  20. Nader H Bshouty and Hanna Mazzawi. Reconstructing weighted graphs with minimal query complexity. Theoretical computer science, 412(19):1782-1790, 2011. URL: https://doi.org/10.1016/j.tcs.2010.12.055.
  21. Chun Lam Chan, Pak Hou Che, Sidharth Jaggi, and Venkatesh Saligrama. Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1832-1839. IEEE, 2011. arXiv:1107.4540. Google Scholar
  22. Huilan Chang, Hong-Bin Chen, Hung-Lin Fu, and Chie-Huai Shi. Reconstruction of hidden graphs and threshold group testing. Journal of Combinatorial Optimization, 22:270-281, 2011. URL: https://doi.org/10.1007/s10878-010-9291-0.
  23. Huilan Chang, Hung-Lin Fu, and Chih-Huai Shih. Learning a hidden graph. Optimization Letters, 8:2341-2348, 2014. URL: https://doi.org/10.1007/s11590-014-0751-9.
  24. H.-B. Chen and H.-L. Fu. Nonadaptive algorithms for threshold group testing. Discrete Applied Mathematics, 157:1581-1585, 2009. Google Scholar
  25. Sung-Soon Choi and Jeong H. Kim. Optimal query complexity bounds for finding graphs. Artificial Intelligence, 174(9-10):551-569, 2010. URL: https://doi.org/10.1016/j.artint.2010.02.003.
  26. Dingzhu Du, Frank K Hwang, and Frank Hwang. Combinatorial group testing and its applications, volume 12. World Scientific, 2000. Google Scholar
  27. Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310-1328, 2006. URL: https://doi.org/10.1137/050644719.
  28. Paulo JSG Ferreira, Bruno Jesus, Jose Vieira, and Armando J Pinho. The rank of random binary matrices and distributed storage applications. IEEE communications letters, 17(1):151-154, 2012. Google Scholar
  29. Vladimir Grebinski and Gregory Kucherov. Optimal query bounds for reconstructing a Hamiltonian cycle in complete graphs. In Fifth Israel Symposium on the Theory of Computing Systems, pages 166-173, 1997. URL: https://doi.org/10.1109/ISTCS.1997.595169.
  30. Vladimir Grebinski and Gregory Kucherov. Reconstructing a hamiltonian cycle by querying the graph: Application to dna physical mapping. Discrete Applied Mathematics, 88(1-3):147-165, 1998. URL: https://doi.org/10.1016/S0166-218X(98)00070-5.
  31. Vladimir Grebinski and Gregory Kucherov. Optimal reconstruction of graphs under the additive model. Algorithmica, 28(1):104-124, 2000. URL: https://doi.org/10.1007/s004530010033.
  32. Marc Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, Maarten Van den Nest, and Hans J. Briegel. Entanglement in graph states and its applications. In Quantum Computers, Algorithms and Chaos, International School of Physics, Enrico Fermi. IOS Press, 2006. URL: https://doi.org/10.3254/978-1-61499-018-5-115.
  33. I. Krasikov and S. Litsyn. Survey of binary Krawtchouk polynomials. In Codes and Association Schemes, volume 56 of DIMACS series in Discrete Mathematics and Theoretical Computer Science, pages 199-212. American Mathematical Society, 1999. Google Scholar
  34. Troy Lee, Miklos Santha, and Shengyu Zhang. Quantum algorithms for graph problems with cut queries. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 939-958. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.59.
  35. Ashley Montanaro. The quantum query complexity of learning multilinear polynomials. Information Processing Letters, 112(11):438-442, 2012. URL: https://doi.org/10.1016/j.ipl.2012.03.002.
  36. Ashley Montanaro. Learning stabilizer states by Bell sampling, 2017. arXiv:1707.04012. Google Scholar
  37. Ashwin Nayak. Optimal lower bounds for quantum automata and random access codes. In Proc. 40superscriptth Annual Symp. Foundations of Computer Science, pages 369-376, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814608.
  38. R. O'Donnell. Computational Applications Of Noise Sensitivity. PhD thesis, Carnegie Mellon University, 2003. Google Scholar
  39. Ely Porat and Amir Rothschild. Explicit non-adaptive combinatorial group testing schemes. In International Colloquium on Automata, Languages, and Programming, pages 748-759. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_61.
  40. Lev Reyzin and Nikhil Srivastava. Learning and verifying graphs using queries with a focus on edge counting. In International Conference on Algorithmic Learning Theory, pages 285-297. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-75225-7_24.
  41. Rocco A. Servedio and Steven J. Gortler. Equivalences and separations between quantum and classical learnability. SIAM Journal on Computing, 33(5):1067-1092, 2004. URL: https://doi.org/10.1137/S0097539704412910.
  42. Liming Zhao, Carlos A. Pérez-Delgado, and Joseph F. Fitzsimons. Fast graph operations in quantum computation. Physical Review A, 93:032314, 2016. URL: https://doi.org/10.1103/PhysRevA.93.032314.
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