Document Open Access Logo

Quantum Chebyshev’s Inequality and Applications

Authors Yassine Hamoudi , Frédéric Magniez

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.69.pdf
  • Filesize: 0.61 MB
  • 16 pages

Document Identifiers

Author Details

Yassine Hamoudi
  • Université de Paris, IRIF, CNRS, F-75013 Paris, France
Frédéric Magniez
  • Université de Paris, IRIF, CNRS, F-75013 Paris, France

Funding

This research was supported by the French ANR project ANR-18-CE47-0010 (QUDATA) and the QuantERA ERA-NET Cofund project QuantAlgo.

Acknowledgements

The authors want to thank the anonymous referees for their valuable comments and suggestions which helped to improve this paper.

Cite AsGet BibTex

Yassine Hamoudi and Frédéric Magniez. Quantum Chebyshev’s Inequality and Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 69:1-69:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.69

Abstract

In this paper we provide new quantum algorithms with polynomial speed-up for a range of problems for which no such results were known, or we improve previous algorithms. First, we consider the approximation of the frequency moments F_k of order k >= 3 in the multi-pass streaming model with updates (turnstile model). We design a P-pass quantum streaming algorithm with memory M satisfying a tradeoff of P^2 M = O~(n^{1-2/k}), whereas the best classical algorithm requires P M = Theta(n^{1-2/k}). Then, we study the problem of estimating the number m of edges and the number t of triangles given query access to an n-vertex graph. We describe optimal quantum algorithms that perform O~(sqrt{n}/m^{1/4}) and O~(sqrt{n}/t^{1/6} + m^{3/4}/sqrt{t}) queries respectively. This is a quadratic speed-up compared to the classical complexity of these problems. For this purpose we develop a new quantum paradigm that we call Quantum Chebyshev’s inequality. Namely we demonstrate that, in a certain model of quantum sampling, one can approximate with relative error the mean of any random variable with a number of quantum samples that is linear in the ratio of the square root of the variance to the mean. Classically the dependence is quadratic. Our algorithm subsumes a previous result of Montanaro [Montanaro, 2015]. This new paradigm is based on a refinement of the Amplitude Estimation algorithm of Brassard et al. [Brassard et al., 2002] and of previous quantum algorithms for the mean estimation problem. We show that this speed-up is optimal, and we identify another common model of quantum sampling where it cannot be obtained. Finally, we develop a new technique called "variable-time amplitude estimation" that reduces the dependence of our algorithm on the sample preparation time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • Quantum algorithms
  • approximation algorithms
  • sublinear-time algorithms
  • Monte Carlo method
  • streaming algorithms
  • subgraph counting

Metrics

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

Related Versions

References

  1. D. Aharonov and A. Ta-Shma. Adiabatic Quantum State Generation. SIAM Journal on Computing, 37(1):47-82, 2007. Google Scholar
  2. N. Alon, Y. Matias, and M. Szegedy. The Space Complexity of Approximating the Frequency Moments. Journal of Computer and System Sciences, 58(1):137-147, 1999. Google Scholar
  3. A. Ambainis. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. Technical report, arXiv.org, 2010. URL: http://arxiv.org/abs/1010.4458.
  4. A. Andoni, R. Krauthgamer, and K. Onak. Streaming Algorithms via Precision Sampling. In Proceedings of the 52nd Symposium on Foundations of Computer Science, FOCS '11, pages 363-372, 2011. Google Scholar
  5. S. Arunachalam and R. de Wolf. Optimal Quantum Sample Complexity of Learning Algorithms. In Proceedings of the 32nd Computational Complexity Conference, CCC '17, pages 25:1-25:31, 2017. Google Scholar
  6. S. Assadi, M. Kapralov, and S. Khanna. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In Proceedings of the 10th Conference on Innovations in Theoretical Computer Science, ITCS '19, pages 6:1-6:20, 2019. Google Scholar
  7. C. Badescu, R. O'Donnell, and J. Wright. Quantum state certification. Technical report, arXiv.org, 2017. URL: http://arxiv.org/abs/1708.06002.
  8. T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing Closeness of Discrete Distributions. Journal of the ACM, 60(1):4:1-4:25, 2013. Google Scholar
  9. C. Bennett. Time/Space Trade-Offs for Reversible Computation. SIAM Journal on Computing, 18(4):766-776, 1989. Google Scholar
  10. G. Brassard, F. Dupuis, S. Gambs, and A. Tapp. An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance. Technical report, arXiv.org, 2011. URL: http://arxiv.org/abs/1106.4267.
  11. G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. Quantum Computation and Quantum Information: A Millennium Volume, 1:53-74, 2002. Google Scholar
  12. S. Bravyi, A. W. Harrow, and A. Hassidim. Quantum Algorithms for Testing Properties of Distributions. IEEE Transactions on Information Theory, 57(6):3971-3981, 2011. Google Scholar
  13. C. L. Canonne, I. Diakonikolas, D. M. Kane, and A. Stewart. Testing conditional independence of discrete distributions. In Proceedings of the 50th Symposium on Theory of Computing, STOC '18, pages 735-748, 2018. Google Scholar
  14. A. Chakrabarti, G. Cormode, R. Kondapally, and A. McGregor. Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. SIAM Journal on Computing, 42(1):61-83, 2013. Google Scholar
  15. S. Chan, I. Diakonikolas, P. Valiant, and G. Valiant. Optimal Algorithms for Testing Closeness of Discrete Distributions. In Proceedings of the 25th Symposium on Discrete Algorithms, SODA '14, pages 1193-1203, 2014. Google Scholar
  16. B. Chazelle, R. Rubinfeld, and L. Trevisan. Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM Journal on Computing, 34(6):1370-1379, 2005. Google Scholar
  17. A. N. Chowdhury and R. D. Somma. Quantum Algorithms for Gibbs Sampling and Hitting-time Estimation. Quantum Information and Computation, 17(1-2):41-64, 2017. Google Scholar
  18. P. Dagum, R. Karp, M. Luby, and S. Ross. An Optimal Algorithm for Monte Carlo Estimation. SIAM Journal on Computing, 29(5):1484-1496, 2000. Google Scholar
  19. N. Destainville, B. Georgeot, and O. Giraud. Quantum Algorithm for Exact Monte Carlo Sampling. Physical Review Letters, 104:250502, 2010. Google Scholar
  20. M. Dyer, A. Frieze, and R. Kannan. A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies. Journal of the ACM, 38(1):1-17, 1991. Google Scholar
  21. T. Eden, A. Levi, and D. Ron. Approximately Counting Triangles in Sublinear Time. Technical Report TR15-046, ECCC, 2015. Google Scholar
  22. T. Eden, A. Levi, D. Ron, and C. Seshadhri. Approximately Counting Triangles in Sublinear Time. SIAM Journal on Computing, 46(5):1603-1646, 2017. Google Scholar
  23. T. Eden, D. Ron, and C. Seshadhri. Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP '17, pages 7:1-7:13, 2017. Google Scholar
  24. T. Eden, D. Ron, and C. Seshadhri. On Approximating the Number of K-cliques in Sublinear Time. In Proceedings of the 50th Symposium on Theory of Computing, STOC '18, pages 722-734, 2018. Google Scholar
  25. U. Feige. On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph. SIAM Journal on Computing, 35(4):964-984, 2006. Google Scholar
  26. S. Ganguly. Taylor Polynomial Estimator for Estimating Frequency Moments. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming, ICALP '15, pages 542-553, 2015. Google Scholar
  27. O. Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  28. O. Goldreich and D. Ron. Approximating Average Parameters of Graphs. Random Structures &Algorithms, 32(4):473-493, 2008. Google Scholar
  29. O. Goldreich and D. Ron. On Testing Expansion in Bounded-Degree Graphs. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 68-75. Springer-Verlag, 2011. Google Scholar
  30. M. Gonen, D. Ron, and Y. Shavitt. Counting Stars and Other Small Subgraphs in Sublinear-Time. SIAM Journal on Discrete Mathematics, 25(3):1365-1411, 2011. Google Scholar
  31. Y. Hamoudi and F. Magniez. Quantum Chebyshev’s Inequality and Applications. Technical report, arXiv.org, 2019. URL: http://arxiv.org/abs/1807.06456.
  32. S. Heinrich. Quantum Summation with an Application to Integration. Journal of Complexity, 18(1):1-50, 2002. Google Scholar
  33. C. W. Helstrom. Quantum detection and estimation theory. Journal of Statistical Physics, 1(2):231-252, June 1969. Google Scholar
  34. R. Jain and A. Nayak. The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: the Index Function Revisited. IEEE Transactions on Information Theory, 60(10):6646-6668, 2014. Google Scholar
  35. M. Jerrum and A. Sinclair. The Markov Chain Monte Carlo Method: An Approach to Approximate Counting and Integration. In Approximation Algorithms for NP-hard Problems, chapter 12, pages 482-520. PWS Publishing, 1996. Google Scholar
  36. M. Jerrum, A. Sinclair, and E. Vigoda. A Polynomial-time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries. Journal of the ACM, 51(4):671-697, 2004. Google Scholar
  37. M. R. Jerrum, L. G. Valiant, and V. V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169-188, 1986. Google Scholar
  38. Z. Ji, Y.-K. Liu, and F. Song. Pseudorandom Quantum States. In Advances in Cryptology, CRYPTO '18, pages 126-152, 2018. Google Scholar
  39. R. M. Karp and M. Luby. Monte-Carlo algorithms for enumeration and reliability problems. In Proceedings of the 24th Symposium on Foundations of Computer Science, FOCS '83, pages 56-64, 1983. Google Scholar
  40. T. Kaufman, M. Krivelevich, and D. Ron. Tight Bounds for Testing Bipartiteness in General Graphs. SIAM Journal on Computing, 33(6):1441-1483, 2004. Google Scholar
  41. E. Knill, G. Ortiz, and R. D. Somma. Optimal quantum measurements of expectation values of observables. Physical Review A, 75:012328, 2007. Google Scholar
  42. F. Le Gall. Exponential Separation of Quantum and Classical Online Space Complexity. Theory of Computing Systems, 45(2):188-202, 2009. Google Scholar
  43. T. Li and X. Wu. Quantum query complexity of entropy estimation. Technical report, arXiv.org, 2017. URL: http://arxiv.org/abs/1710.06025.
  44. Y. Li and D. P. Woodruff. A Tight Lower Bound for High Frequency Moment Estimation with Small Error. In Proceedings of the Workshop on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, APPROX/RANDOM '13, pages 623-638, 2013. Google Scholar
  45. F. Magniez, C. Mathieu, and A. Nayak. Recognizing Well-Parenthesized Expressions in the Streaming Model. SIAM Journal on Computing, 43(6):1880-1905, 2014. Google Scholar
  46. M. Monemizadeh and D. P. Woodruff. 1-pass Relative-error Lp-sampling with Applications. In Proceedings of the 21st Symposium on Discrete Algorithms, SODA '10, pages 1143-1160, 2010. Google Scholar
  47. A. Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 471(2181), 2015. Google Scholar
  48. A. Montanaro. The quantum complexity of approximating the frequency moments. Quantum Information and Computation, 16:1169-1190, 2016. Google Scholar
  49. A. Nayak and D. Touchette. Augmented Index and Quantum Streaming Algorithms for DYCK(2). In Proceedings of the 32nd Conference on Computational Complexity, CCC '17, pages 23:1-23:21, 2017. Google Scholar
  50. A. Nayak and F. Wu. The Quantum Query Complexity of Approximating the Median and Related Statistics. In Proceedings of the 31st Symposium on Theory of Computing, STOC '99, pages 384-393, 1999. Google Scholar
  51. D. Poulin and P. Wocjan. Sampling from the Thermal Quantum Gibbs State and Evaluating Partition Functions with a Quantum Computer. Physical Review Letters, 103:220502, 2009. Google Scholar
  52. C. Seshadhri. A simpler sublinear algorithm for approximating the triangle count. Technical report, arXiv.org, 2015. URL: http://arxiv.org/abs/1505.01927.
  53. K. Temme, T. J. Osborne, K. Vollbrecht, D. Poulin, and F. Verstraete. Quantum Metropolis Sampling. Nature, 471:87, 2011. Google Scholar
  54. D. Štefankovič, S. Vempala, and E. Vigoda. Adaptive Simulated Annealing: A Near-optimal Connection Between Sampling and Counting. Journal of the ACM, 56(3):18:1-18:36, 2009. Google Scholar
  55. P. Wocjan and A. Abeyesinghe. Speedup via quantum sampling. Physical Review A, 78:042336, 2008. Google Scholar
  56. P. Wocjan, C.-F. Chiang, D. Nagaj, and A. Abeyesinghe. Quantum algorithm for approximating partition functions. Physical Review A, 80:022340, 2009. Google Scholar
  57. D. P. Woodruff and Q. Zhang. Tight Bounds for Distributed Functional Monitoring. In Proceedings of the 44th Symposium on Theory of Computing, STOC '12, pages 941-960, 2012. 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 Imprint Privacy Contact