Document Open Access Logo

Quantum Algorithms for Matrix Scaling and Matrix Balancing

Authors Joran van Apeldoorn, Sander Gribling, Yinan Li , Harold Nieuwboer , Michael Walter, Ronald de Wolf

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.110.pdf
  • Filesize: 0.87 MB
  • 17 pages

Document Identifiers

Author Details

Joran van Apeldoorn
  • Institute for Information Law and QuSoft, University of Amsterdam, The Netherlands
Sander Gribling
  • IRIF, Université de Paris, CNRS, Paris, France
Yinan Li
  • Graduate School of Mathematics, Nagoya University, Japan
Harold Nieuwboer
  • Korteweg-de Vries Institute for Mathematics and QuSoft, University of Amsterdam, The Netherlands
Michael Walter
  • KdVI, ITFA, ILLC, and QuSoft, University of Amsterdam, The Netherlands
Ronald de Wolf
  • QuSoft, CWI, Amsterdam, The Netherlands
  • University of Amsterdam, The Netherlands

Funding

  • van Apeldoorn, Joran: Dutch Research Council (NWO/OCW), as part of QSC (024.003.037).
  • Gribling, Sander: Partially supported by SIRTEQ-grant QuIPP.
  • Li, Yinan: MEXT Quantum Leap Flagship Program grant no. JPMXS0120319794.
  • Nieuwboer, Harold: NWO grant no. OCENW.KLEIN.267.
  • Walter, Michael: NWO Veni grant no. 680-47-459 and grant no. OCENW.KLEIN.267.
  • de Wolf, Ronald: NWO/OCW through QSC (024.003.037) and QuantAlgo (QuantERA 680-91-034).

Acknowledgements

We thank the ICALP referees for some very helpful feedback.

Cite As Get BibTex

Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, and Ronald de Wolf. Quantum Algorithms for Matrix Scaling and Matrix Balancing. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 110:1-110:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.110

Abstract

Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications, such as approximating the permanent, and pre-conditioning linear systems to make them more numerically stable. We study the power and limitations of quantum algorithms for these problems. We provide quantum implementations of two classical (in both senses of the word) methods: Sinkhorn’s algorithm for matrix scaling and Osborne’s algorithm for matrix balancing. Using amplitude estimation as our main tool, our quantum implementations both run in time Õ(√{mn}/ε⁴) for scaling or balancing an n × n matrix (given by an oracle) with m non-zero entries to within 𝓁₁-error ε. Their classical analogs use time Õ(m/ε²), and every classical algorithm for scaling or balancing with small constant ε requires Ω(m) queries to the entries of the input matrix. We thus achieve a polynomial speed-up in terms of n, at the expense of a worse polynomial dependence on the obtained 𝓁₁-error ε. Even for constant ε these problems are already non-trivial (and relevant in applications). Along the way, we extend the classical analysis of Sinkhorn’s and Osborne’s algorithm to allow for errors in the computation of marginals. We also adapt an improved analysis of Sinkhorn’s algorithm for entrywise-positive matrices to the 𝓁₁-setting, obtaining an Õ(n^{1.5}/ε³)-time quantum algorithm for ε-𝓁₁-scaling. We also prove a lower bound, showing our quantum algorithm for matrix scaling is essentially optimal for constant ε: every quantum algorithm for matrix scaling that achieves a constant 𝓁₁-error w.r.t. uniform marginals needs Ω(√{mn}) queries.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Quantum computation theory
Keywords
  • Matrix scaling
  • matrix balancing
  • quantum algorithms

Metrics

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

Related Versions

References

  1. Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Much faster algorithms for matrix scaling. In Proceedings of IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS'17), pages 890-901, 2017. Google Scholar
  2. Jason Altschuler, Jonathan Niles-Weed, and Philippe Rigollet. Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. In Advances in Neural Information Processing Systems, volume 30, pages 1964-1974, 2017. Google Scholar
  3. Jason M. Altschuler and Pablo A. Parrilo. Approximating Min-Mean-Cycle for low-diameter graphs in near-optimal time and memory, 2020. URL: http://arxiv.org/abs/2004.03114.
  4. Jason M. Altschuler and Pablo A. Parrilo. Random Osborne: A simple, practical algorithm for matrix balancing in near-linear time, 2020. URL: http://arxiv.org/abs/2004.02837.
  5. Andris Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750-767, 2002. Earlier version in STOC'00. quant-ph/0002066. Google Scholar
  6. E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen. LAPACK Users' Guide. SIAM, 1999. URL: https://doi.org/10.1137/1.9780898719604.
  7. Joran van Apeldoorn and András Gilyén. Improvements in quantum SDP-solving with applications. In Proceedings of 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 99:1-99:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.99.
  8. Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. Quantum, 4(230), 2020. Earlier version in FOCS'17. URL: http://arxiv.org/abs/1705.01843.
  9. Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, and Ronald de Wolf. Quantum algorithms for matrix scaling and matrix balancing, 2020. URL: http://arxiv.org/abs/2011.12823v1.
  10. Srinivasan Arunachalam and Reevu Maity. Quantum boosting. In Proceedings of 37th International Conference on Machine Learning (ICML'20), 2020. URL: http://arxiv.org/abs/2002.05056.
  11. Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proceedings of 43rd Symposium on Theory of Computing (STOC'11), pages 519-528. ACM, 2011. Google Scholar
  12. Andrew Michael Bradley. Algorithms for the equilibration of matrices and their application to limited-memory Quasi-Newton methods. PhD thesis, Stanford University, 2010. Google Scholar
  13. Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. In Proceedings of 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.27.
  14. Fernando G. S. L. Brandão and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In Proceedings of IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS'17), pages 415-426, 2017. URL: https://doi.org/10.1109/FOCS.2017.45.
  15. Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of Contemporary Mathematics, pages 53-74. American Mathematical Society, 2002. URL: http://arxiv.org/abs/quant-ph/0005055.
  16. Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes. In Proceedings of 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS'18), pages 883-897, 2018. URL: https://doi.org/10.1109/FOCS.2018.00088.
  17. Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Towards a theory of non-commutative optimization: geodesic 1st and 2nd order methods for moment maps and polytopes. In Proceedings of 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS'19), pages 845-861. IEEE, 2019. Google Scholar
  18. Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory. In Proceedings of 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1-24:20, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.24.
  19. Peter Bürgisser, Yinan Li, Harold Nieuwboer, and Michael Walter. Interior-point methods for unconstrained geometric programming and scaling problems, 2020. URL: http://arxiv.org/abs/2008.12110.
  20. Deeparnab Chakrabarty and Sanjeev Khanna. Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling. Mathematical Programming, pages 1-13, 2020. Google Scholar
  21. Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balancing via box constrained Newton’s method and interior point methods. In Proceedings of IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS'17), pages 902-913, 2017. URL: https://doi.org/10.1109/FOCS.2017.88.
  22. Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, volume 26, pages 2292-2300, 2013. Google Scholar
  23. 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.
  24. Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum, 1996. URL: http://arxiv.org/abs/quant-ph/9607014.
  25. Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. In Proceedings of 16th Annual IEEE Conference on Computational Complexity, pages 100-106, 2001. URL: https://doi.org/10.1109/CCC.2001.933877.
  26. Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. Geometric and Functional Analysis, 28(1):100-145, 2018. Earlier version in STOC'17. Google Scholar
  27. Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. Operator scaling: theory and applications. Foundations of Computational Mathematics, pages 1-68, 2019. Earlier version in FOCS'16. Google Scholar
  28. Ankit Garg and Rafael Oliveira. Recent progress on scaling algorithms and applications. Bulletin of the EATCS, Computational Complexity Column, 125, 2018. URL: http://arxiv.org/abs/1808.09669.
  29. Leonid Gurvits. Classical complexity and quantum entanglement. Journal of Computer and System Sciences, 69(3):448-484, 2004. URL: https://doi.org/10.1016/j.jcss.2004.06.003.
  30. Yassine Hamoudi, Maharshi Ray, Patrick Rebentrost, Miklos Santha, Xin Wang, and Siyi Yang. Quantum algorithms for hedging and the Sparsitron, 2020. URL: http://arxiv.org/abs/2002.06003.
  31. Martin Idel. A review of matrix scaling and Sinkhorn’s normal form for matrices and positive maps, 2016. URL: http://arxiv.org/abs/1609.06349.
  32. Adam Izdebski and Ronald de Wolf. Improved quantum boosting, 2020. URL: http://arxiv.org/abs/2009.08360.
  33. B. Kalantari, L. Khachiyan, and A. Shokoufandeh. On the complexity of matrix balancing. SIAM Journal on Matrix Analysis and Applications, 18(2):450-463, 1997. URL: https://doi.org/10.1137/S0895479895289765.
  34. B. Kalantari, I. Lari, F. Ricca, and B. Simeone. On the complexity of general matrix scaling and entropy minimization via the RAS algorithm. Mathematical Programming, 112:371-401, 2008. Google Scholar
  35. Bahman Kalantari and Leonid Khachiyan. On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms. Operations Research Letters, 14(5):237-244, 1993. URL: https://doi.org/10.1016/0167-6377(93)90087-W.
  36. Bahman Kalantari and Leonid Khachiyan. On the complexity of nonnegative-matrix scaling. Linear Algebra and its Applications, 240:87-103, 1996. URL: https://doi.org/10.1016/0024-3795(94)00188-X.
  37. J. Kruithof. Telefoonverkeersrekening. De Ingenieur, 52:E15-E25, 1937. Google Scholar
  38. Nathan Linial, Alex Samorodnitsky, and Avi Wigderson. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica, 20(4):545-568, 2000. URL: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/LSW98/lsw00.pdf.
  39. Oren E. Livne and Gene H. Golub. Scaling by binormalization. Numerical Algorithms, 35(1):97-120, 2004. Google Scholar
  40. Mathworks. balance: diagonal scaling to improve eigenvalue accuracy. URL: https://www.mathworks.com/help/matlab/ref/balance.html.
  41. Arkadi Nemirovski and Uriel Rothblum. On complexity of matrix scaling. Linear Algebra and its Applications, 302-303:435-460, 1999. URL: https://doi.org/10.1016/S0024-3795(99)00212-8.
  42. Brendan O'Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. A primal-dual operator splitting method for conic optimization. Journal of Optimization Theory and Applications, 169(3):1042-1068, 2016. URL: http://arxiv.org/abs/1312.3039.
  43. E. E. Osborne. On pre-conditioning of matrices. Journal of ACM, 7(4), 1960. URL: https://doi.org/10.1145/321043.321048.
  44. Rafail Ostrovsky, Yuval Rabani, and Arman Yousefi. Matrix balancing in L_p norms: Bounding the convergence rate of Osborne’s iteration. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), pages 154-169, 2017. URL: https://doi.org/10.1137/1.9781611974782.11.
  45. B. N. Parlett and C. Reinsch. Balancing a matrix for calculation of eigenvalues and eigenvectors. Numerische Mathematik, 13:293-304, 1969. Google Scholar
  46. Thomas Pock and Antonin Chambolle. Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In Proceedings of IEEE International Conference on Computer Vision (ICCV), pages 1762-1769, 2011. Google Scholar
  47. Uriel G. Rothblum and Hans Schneider. Scalings of matrices which have prespecified row sums and column sums via optimization. Linear Algebra and its Applications, 114:737-764, 1989. Google Scholar
  48. Leonard J. Schulman and Alistair Sinclair. Analysis of a classical matrix preconditioning algorithm. In Proceedings of 47th Annual ACM Symposium on Theory of Computing (STOC'15), pages 831-840, 2015. Google Scholar
  49. Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. The Annals of Mathematical Statistics, 35(2):876-879, 1964. Google Scholar
  50. Richard Stone. Multiple classifications in social accounting. University of Cambridge, Department of Applied Economics, 1964. 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