Efficient algorithms for quantum information bottleneck

Masahito Hayashi1,2,3,4 and Yuxiang Yang5

1Shenzhen Institute for Quantum Science and Engineering, Southern University of Science and Technology, Shenzhen,518055, China
2International Quantum Academy (SIQA), Futian District, Shenzhen 518048, China
3Guangdong Provincial Key Laboratory of Quantum Science and Engineering, Southern University of Science and Technology, Shenzhen, 518055, China
4Graduate School of Mathematics, Nagoya University, Nagoya, 464-8602, Japan
5QICI Quantum Information and Computation Initiative, Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

The ability to extract relevant information is critical to learning. An ingenious approach as such is the information bottleneck, an optimisation problem whose solution corresponds to a faithful and memory-efficient representation of relevant information from a large system. The advent of the age of quantum computing calls for efficient methods that work on information regarding quantum systems. Here we address this by proposing a new and general algorithm for the quantum generalisation of information bottleneck. Our algorithm excels in the speed and the definiteness of convergence compared with prior results. It also works for a much broader range of problems, including the quantum extension of deterministic information bottleneck, an important variant of the original information bottleneck problem. Notably, we discover that a quantum system can achieve strictly better performance than a classical system of the same size regarding quantum information bottleneck, providing new vision on justifying the advantage of quantum machine learning.

Imagine that a large amount of data about the weather are generated. In order to predict tomorrow's weather, such a large amount of data is difficult to handle, and it is needed to extract essential information T from the original large data X. The information bottleneck realizes this objective of information extraction by minimizing a certain informational quantity.

The advent of the age of quantum computing calls for information bottleneck algorithms that work for quantum systems. In this work, we design such an algorithm that works generally when either (or both) of T and Y is a quantum system. Our algorithm excels in the speed and the definiteness of convergence compared with prior results. Remarkably, we found a genuine advantage of using a quantum system as the new database T, which suggests that quantum systems could be better at representing key features in machine learning.

► BibTeX data

► References

[1] S. Arimoto. An algorithm for computing the capacity of arbitrary discrete memoryless channels. IEEE Transactions on Information Theory, 18 (1): 14–20, 1972. 10.1109/​TIT.1972.1054753.
https:/​/​doi.org/​10.1109/​TIT.1972.1054753

[2] Leonardo Banchi, Jason Pereira, and Stefano Pirandola. Generalization in quantum machine learning: A quantum information standpoint. PRX Quantum, 2: 040321, Nov 2021. 10.1103/​PRXQuantum.2.040321.
https:/​/​doi.org/​10.1103/​PRXQuantum.2.040321

[3] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549 (7671): 195–202, 2017. 10.1038/​nature23474.
https:/​/​doi.org/​10.1038/​nature23474

[4] R. Blahut. Computation of channel capacity and rate-distortion functions. IEEE Transactions on Information Theory, 18 (4): 460–473, 1972. 10.1109/​TIT.1972.1054855.
https:/​/​doi.org/​10.1109/​TIT.1972.1054855

[5] Carsten Blank, Daniel K Park, June-Koo Kevin Rhee, and Francesco Petruccione. Quantum classifier with tailored quantum kernel. npj Quantum Information, 6 (1): 1–7, 2020. 10.1038/​s41534-020-0272-6.
https:/​/​doi.org/​10.1038/​s41534-020-0272-6

[6] Nilanjana Datta, Christoph Hirche, and Andreas Winter. Convexity and operational interpretation of the quantum information bottleneck function. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 1157–1161, 2019. 10.1109/​ISIT.2019.8849518.
https:/​/​doi.org/​10.1109/​ISIT.2019.8849518

[7] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. 10.1145/​3313276.3316366.
https:/​/​doi.org/​10.1145/​3313276.3316366

[8] Ziv Goldfeld and Yury Polyanskiy. The information bottleneck problem and its applications in machine learning. IEEE Journal on Selected Areas in Information Theory, 1 (1): 19–38, 2020. 10.1109/​JSAIT.2020.2991561.
https:/​/​doi.org/​10.1109/​JSAIT.2020.2991561

[9] Arne L. Grimsmo and Susanne Still. Quantum predictive filtering. Phys. Rev. A, 94: 012338, Jul 2016. 10.1103/​PhysRevA.94.012338.
https:/​/​doi.org/​10.1103/​PhysRevA.94.012338

[10] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103 (15): 150502, 2009. 10.1103/​PhysRevLett.103.150502.
https:/​/​doi.org/​10.1103/​PhysRevLett.103.150502

[11] Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 567 (7747): 209–212, 2019. 10.1038/​s41586-019-0980-2.
https:/​/​doi.org/​10.1038/​s41586-019-0980-2

[12] Masahito Hayashi and Vincent Y. F. Tan. Minimum rates of approximate sufficient statistics. IEEE Transactions on Information Theory, 64 (2): 875–888, 2018. 10.1109/​TIT.2017.2775612.
https:/​/​doi.org/​10.1109/​TIT.2017.2775612

[13] Carl W Helstrom. Quantum detection and estimation theory. Journal of Statistical Physics, 1 (2): 231–252, 1969. 10.1007/​BF01007479.
https:/​/​doi.org/​10.1007/​BF01007479

[14] Christoph Hirche and Andreas Winter. An alphabet-size bound for the information bottleneck function. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2383–2388, 2020. 10.1109/​ISIT44484.2020.9174416.
https:/​/​doi.org/​10.1109/​ISIT44484.2020.9174416

[15] Alexander S Holevo. Probabilistic and statistical aspects of quantum theory, volume 1. Springer Science & Business Media, 2011. 10.1007/​978-88-7642-378-9.
https:/​/​doi.org/​10.1007/​978-88-7642-378-9

[16] Winston H. Hsu, Lyndon S. Kennedy, and Shih-Fu Chang. Video search reranking via information bottleneck principle. MM '06, pages 35–44, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595934472. 10.1145/​1180639.1180654.
https:/​/​doi.org/​10.1145/​1180639.1180654

[17] Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac, and Nathan Killoran. Quantum embeddings for machine learning. arXiv preprint arXiv:2001.03622, 2020. 10.48550/​arXiv.2001.03622.
https:/​/​doi.org/​10.48550/​arXiv.2001.03622
arXiv:2001.03622

[18] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by uniform spectral amplification. arXiv preprint arXiv:1707.05391, 2017. 10.48550/​arXiv.1707.05391.
https:/​/​doi.org/​10.48550/​arXiv.1707.05391
arXiv:1707.05391

[19] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum, 3: 163, 2019. 10.22331/​q-2019-07-12-163.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163

[20] Adrián Pérez-Salinas, Alba Cervera-Lierta, Elies Gil-Fuster, and José I Latorre. Data re-uploading for a universal quantum classifier. Quantum, 4: 226, 2020. 10.22331/​q-2020-02-06-226.
https:/​/​doi.org/​10.22331/​q-2020-02-06-226

[21] Martin Plesch and Vladimír Bužek. Efficient compression of quantum information. Physical Review A, 81 (3): 032317, 2010. 10.1103/​PhysRevA.81.032317.
https:/​/​doi.org/​10.1103/​PhysRevA.81.032317

[22] Navneeth Ramakrishnan, Raban Iten, Volkher B. Scholz, and Mario Berta. Computing quantum channel capacities. IEEE Transactions on Information Theory, 67 (2): 946–960, 2021. 10.1109/​TIT.2020.3034471.
https:/​/​doi.org/​10.1109/​TIT.2020.3034471

[23] Lee A Rozema, Dylan H Mahler, Alex Hayat, Peter S Turner, and Aephraim M Steinberg. Quantum data compression of a qubit ensemble. Physical Review Letters, 113 (16): 160504, 2014. 10.1103/​PhysRevLett.113.160504.
https:/​/​doi.org/​10.1103/​PhysRevLett.113.160504

[24] Sina Salek, Daniela Cadamuro, Philipp Kammerlander, and Karoline Wiesner. Quantum rate-distortion coding of relevant information. IEEE Transactions on Information Theory, 65 (4): 2603–2613, 2019. 10.1109/​TIT.2018.2878412.
https:/​/​doi.org/​10.1109/​TIT.2018.2878412

[25] Maria Schuld. Supervised quantum machine learning models are kernel methods. arXiv preprint arXiv:2101.11020, 2021. 10.48550/​arXiv.2101.11020.
https:/​/​doi.org/​10.48550/​arXiv.2101.11020
arXiv:2101.11020

[26] Maria Schuld and Nathan Killoran. Quantum machine learning in feature Hilbert spaces. Physical Review Letters, 122 (4): 040504, 2019. 10.1103/​PhysRevLett.122.040504.
https:/​/​doi.org/​10.1103/​PhysRevLett.122.040504

[27] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. An introduction to quantum machine learning. Contemporary Physics, 56 (2): 172–185, 2015. 10.1080/​00107514.2014.964942.
https:/​/​doi.org/​10.1080/​00107514.2014.964942

[28] Ravid Shwartz-Ziv and Naftali Tishby. Opening the black box of deep neural networks via information. arXiv preprint arXiv:1703.00810, 2017. 10.48550/​arXiv.1703.00810.
https:/​/​doi.org/​10.48550/​arXiv.1703.00810
arXiv:1703.00810

[29] Noam Slonim and Naftali Tishby. Document clustering using word clusters via the information bottleneck method. SIGIR '00, pages 208–215, New York, NY, USA, 2000. Association for Computing Machinery. ISBN 1581132263. 10.1145/​345508.345578.
https:/​/​doi.org/​10.1145/​345508.345578

[30] Maximilian Stark, Aizaz Shah, and Gerhard Bauch. Polar code construction using the information bottleneck method. In 2018 IEEE Wireless Communications and Networking Conference Workshops (WCNCW), pages 7–12, 2018. 10.1109/​WCNCW.2018.8368978.
https:/​/​doi.org/​10.1109/​WCNCW.2018.8368978

[31] DJ Strouse and David J. Schwab. The Deterministic Information Bottleneck. Neural Computation, 29 (6): 1611–1630, 06 2017. ISSN 0899-7667. 10.1162/​NECO_a_00961.
https:/​/​doi.org/​10.1162/​NECO_a_00961

[32] N. Tishby, F. C. Pereira, and W. Bialek. The information bottleneck method. In The 37th annual Allerton Conference on Communication, Control, and Computing, pages 368–377. Univ. Illinois Press, 1999. 10.48550/​arXiv.physics/​0004057.
https:/​/​doi.org/​10.48550/​arXiv.physics/​0004057

[33] Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 IEEE information theory workshop (ITW), pages 1–5. IEEE, 2015. 10.1109/​ITW.2015.7133169.
https:/​/​doi.org/​10.1109/​ITW.2015.7133169

[34] Peter Wittek. Quantum machine learning: what quantum computing means to data mining. Academic Press, 2014. 10.1016/​C2013-0-19170-2.
https:/​/​doi.org/​10.1016/​C2013-0-19170-2

[35] Yuxiang Yang, Giulio Chiribella, and Daniel Ebler. Efficient quantum compression for ensembles of identically prepared mixed states. Physical Review Letters, 116 (8): 080501, 2016a. 10.1103/​PhysRevLett.116.080501.
https:/​/​doi.org/​10.1103/​PhysRevLett.116.080501

[36] Yuxiang Yang, Giulio Chiribella, and Masahito Hayashi. Optimal compression for identically prepared qubit states. Phys. Rev. Lett., 117: 090502, Aug 2016b. 10.1103/​PhysRevLett.117.090502.
https:/​/​doi.org/​10.1103/​PhysRevLett.117.090502

[37] Yuxiang Yang, Ge Bai, Giulio Chiribella, and Masahito Hayashi. Compression for quantum population coding. IEEE Transactions on Information Theory, 64 (7): 4766–4783, 2018a. 10.1109/​TIT.2017.2788407.
https:/​/​doi.org/​10.1109/​TIT.2017.2788407

[38] Yuxiang Yang, Giulio Chiribella, and Masahito Hayashi. Quantum stopwatch: how to store time in a quantum memory. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474 (2213): 20170773, 2018b. 10.1098/​rspa.2017.0773.
https:/​/​doi.org/​10.1098/​rspa.2017.0773

Cited by

[1] Yuxuan Du, Yibo Yang, Dacheng Tao, and Min-Hsiu Hsieh, "Problem-Dependent Power of Quantum Neural Networks on Multiclass Classification", Physical Review Letters 131 14, 140601 (2023).

[2] Cynthia Olvera, Oscar Montiel Ross, and Yoshio Rubio, "EEG-based motor imagery classification with quantum algorithms", Expert Systems with Applications 247, 123354 (2024).

[3] Ahmet Burak Catli and Nathan Wiebe, "Training quantum neural networks using the Quantum Information Bottleneck method", arXiv:2212.02600, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2024-02-26 02:58:45) and SAO/NASA ADS (last updated successfully 2024-02-26 02:58:46). The list may be incomplete as not all publishers provide suitable and complete citation data.