Qubit-efficient Encoding Schemes For Binary Optimisation Problems

Republished By Plato

Followers: 0

Benjamin Tan¹, Marc-Antoine Lemonde¹, Supanut Thanasilp¹, Jirawat Tangpanitanon¹, and Dimitris G. Angelakis^1,2

¹Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543
²School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece 73100

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

Abstract

We propose and analyze a set of variational quantum algorithms for solving quadratic unconstrained binary optimization problems where a problem consisting of $n_c$ classical variables can be implemented on $mathcal O(log n_c)$ number of qubits. The underlying encoding scheme allows for a systematic increase in correlations among the classical variables captured by a variational quantum state by progressively increasing the number of qubits involved. We first examine the simplest limit where all correlations are neglected, i.e. when the quantum state can only describe statistically independent classical variables. We apply this minimal encoding to find approximate solutions of a general problem instance comprised of $64$ classical variables using $7$ qubits. Next, we show how two-body correlations between the classical variables can be incorporated in the variational quantum state and how it can improve the quality of the approximate solutions. We give an example by solving a $42$-variable Max-Cut problem using only $8$ qubits where we exploit the specific topology of the problem. We analyze whether these cases can be optimized efficiently given the limited resources available in state-of-the-art quantum platforms. Lastly, we present the general framework for extending the expressibility of the probability distribution to any multi-body correlations.

Featured image: Our encoding scheme uses qubits to capture classical correlations between subgroups of classical variables in a QUBO problem, allowing for approximate solutions to be found with fewer qubits. The encoding scheme provides flexibility in the amount of correlations to be captured and by extension, the number of qubits required to solve the problem.

[embedded content]

Popular summary

One promising application where quantum computers are expected to become a disruptive innovation is in the field of combinatorial optimization. So far, most quantum algorithms for combinatorial problems entail mapping each classical variable to single qubit in the quantum device. While this mapping in principle allows for an efficient search over the exponentially large number of possible solutions, the quantum resources required and restricted connectivity of current quantum hardware limits the problem sizes to toy models. Current state-of-the-art quantum experiments have found approximate solutions for a fully connected problem of only $17$ variables while modern classical methods can find solutions for problem sizes with over $10^4$ variables. In our work, we introduce an alternative encoding scheme that could allow intermediate-scale quantum devices to tackle problem sizes rivaling the biggest instances that can be solved using modern classical methods.

We adopt a fundamentally different approach by using a quantum state to encode correlations between restricted subsets of variables. In the simplest allowed encoding, each subset consists of a single variable, allowing for approximate solutions to be found using exponentially fewer qubits. The flexibility of our encoding scheme allows for additional qubits to systematically increase the correlations captured by the quantum state. Using numerical simulations, we demonstrate this encoding scheme on a $64$-variable optimization problem using only $7$ qubits and $104$ gates in the limiting case where no correlations are captured. We also demonstrate, with a $42$-variable example using $8$ qubits, how capturing two-body correlation yields better results. Lastly, we include results showing how this reduction in resources is advantageous compared to standard quantum approaches when implemented on noisy quantum hardware.

Moving forward, we aim to explore the possibilities of enhancing the performance of this encoding scheme to compete alongside state-of-the-art classical algorithms

► BibTeX data

@article{Tan2021qubitefficient, doi = {10.22331/q-2021-05-04-454}, url = {https://doi.org/10.22331/q-2021-05-04-454}, title = {Qubit-efficient encoding schemes for binary optimisation problems}, author = {Tan, Benjamin and Lemonde, Marc-Antoine and Thanasilp, Supanut and Tangpanitanon, Jirawat and Angelakis, Dimitris G.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {5}, pages = {454}, month = may, year = {2021}<br /> }

► References

[1] Deanna M. Abrams, Nicolas Didier, Blake R. Johnson, Marcus P. da Silva, and Colm A. Ryan. Implementation of xy entangling gates with a single calibrated pulse. Nature Electronics, 3 (12): 744–750, Nov 2020. ISSN 2520-1131. 10.1038/s41928-020-00498-1.
https://doi.org/10.1038/s41928-020-00498-1

[2] Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation. Rev. Mod. Phys., 90: 015002, Jan 2018. 10.1103/RevModPhys.90.015002.
https://doi.org/10.1103/RevModPhys.90.015002

[3] Arya K. Babbush R. et al. Arute, F. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 10.1038/s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5

[4] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. Quantum algorithms for quantum chemistry and quantum materials science. Chemical Reviews, 120 (22): 12685–12717, Oct 2020. ISSN 1520-6890. 10.1021/acs.chemrev.9b00829.
https://doi.org/10.1021/acs.chemrev.9b00829

[5] Andreas Bengtsson, Pontus Vikstål, Christopher Warren, Marika Svensson, Xiu Gu, Anton Frisk Kockum, Philip Krantz, Christian Križan, Daryoush Shiri, Ida-Maria Svensson, and et al. Improved success probability with greater circuit depth for the quantum approximate optimization algorithm. Physical Review Applied, 14 (3), Sep 2020. ISSN 2331-7019. 10.1103/physrevapplied.14.034010.
https://doi.org/10.1103/physrevapplied.14.034010

[6] Lee Braine, Daniel J Egger, Jennifer Glick, and Stefan Woerner. Quantum algorithms for mixed binary optimization applied to transaction settlement. arXiv preprint arXiv:1910.05788, 2019.
arXiv:1910.05788

[7] Fernando G.S.L. Brandão, Aram W. Harrow, and Michał Horodecki. Local Random Quantum Circuits are Approximate Polynomial-Designs. Communications in Mathematical Physics, 346 (2): 397–434, 2016. ISSN 14320916. 10.1007/s00220-016-2706-8.
https://doi.org/10.1007/s00220-016-2706-8

[8] Colin D. Bruzewicz, John Chiaverini, Robert McConnell, and Jeremy M. Sage. Trapped-ion quantum computing: Progress and challenges. Applied Physics Reviews, 6 (2): 021314, 2019. 10.1063/1.5088164.
https://doi.org/10.1063/1.5088164

[9] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Communications, 12 (1), Mar 2021. ISSN 2041-1723. 10.1038/s41467-021-21728-w.
https://doi.org/10.1038/s41467-021-21728-w

[10] Brian Coyle, Daniel Mills, Vincent Danos, and Elham Kashefi. The born supremacy: quantum advantage and training of an ising born machine. npj Quantum Information, 6 (1), Jul 2020. ISSN 2056-6387. 10.1038/s41534-020-00288-9.
https://doi.org/10.1038/s41534-020-00288-9

[11] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao. Expressive power of parametrized quantum circuits. Physical Review Research, 2 (3), Jul 2020. ISSN 2643-1564. 10.1103/physrevresearch.2.033125.
https://doi.org/10.1103/physrevresearch.2.033125

[12] Suguru Endo, Zhenyu Cai, Simon C. Benjamin, and Xiao Yuan. Hybrid quantum-classical algorithms and quantum error mitigation. Journal of the Physical Society of Japan, 90 (3): 032001, Mar 2021. ISSN 1347-4073. 10.7566/jpsj.90.032001.
https://doi.org/10.7566/jpsj.90.032001

[13] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014a.
arXiv:1411.4028

[14] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. arXiv preprint arXiv:1412.6062, 2014b.
arXiv:1412.6062

[15] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The quantum approximate optimization algorithm and the sherrington-kirkpatrick model at infinite size. arXiv preprint arXiv:1910.08187, 2019.
arXiv:1910.08187

[16] Dimitris Fouskakis and David Draper. Stochastic optimization: a review. International Statistical Review, 70 (3): 315–349, 2002. 10.1111/j.1751-5823.2002.tb00174.x.
https://doi.org/10.1111/j.1751-5823.2002.tb00174.x

[17] F. Glover M. Lewis Z.P Lü H.B Wang Y. Wang G. Kochenberger, J.K. Hao. The unconstrained binary quadratic programming problem: a survey. Journal of Combinatorial Optimization, 28 (1): 58–81, 2014. 10.1007/s10878-014-9734-0.
https://doi.org/10.1007/s10878-014-9734-0

[18] Michael R Garey and David S Johnson. Computers and intractability, volume 174. freeman San Francisco, 1979.
https://dl.acm.org/doi/book/10.5555/574848

[19] Lov K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 79: 325–328, Jul 1997. 10.1103/PhysRevLett.79.325.
https://doi.org/10.1103/PhysRevLett.79.325

[20] LLC Gurobi Optimization. Gurobi optimizer reference manual, 2020. URL http://www.gurobi.com.
http://www.gurobi.com

[21] Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, and et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17 (3): 332–336, Feb 2021. ISSN 1745-2481. 10.1038/s41567-020-01105-y.
https://doi.org/10.1038/s41567-020-01105-y

[22] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549 (7671): 242–246, 2017. 10.1038/nature23879.
https://doi.org/10.1038/nature23879

[23] Richard M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972. ISBN 978-1-4684-2001-2. 10.1007/978-1-4684-2001-2_9.
https://doi.org/10.1007/978-1-4684-2001-2_9

[24] Nathan Killoran, Thomas R. Bromley, Juan Miguel Arrazola, Maria Schuld, Nicolás Quesada, and Seth Lloyd. Continuous-variable quantum neural networks. Phys. Rev. Research, 1: 033063, Oct 2019. 10.1103/PhysRevResearch.1.033063.
https://doi.org/10.1103/PhysRevResearch.1.033063

[25] Tjalling C. Koopmans and Martin Beckmann. Assignment problems and the location of economic activities. Econometrica, 25 (1): 53–76, 1957. ISSN 00129682, 14680262. 10.2307/1907742.
https://doi.org/10.2307/1907742

[26] Nathan Lacroix, Christoph Hellings, Christian Kraglund Andersen, Agustin Di Paolo, Ants Remm, Stefania Lazar, Sebastian Krinner, Graham J. Norris, Mihai Gabureac, Johannes Heinsoo, and et al. Improving the performance of deep quantum optimization algorithms with continuous gate sets. PRX Quantum, 1 (2), Oct 2020. ISSN 2691-3399. 10.1103/prxquantum.1.020304.
https://doi.org/10.1103/prxquantum.1.020304

[27] Jose I. Latorre. Image compression and entanglement. arXiv preprint arXiv:0510031, 2005.
arXiv:quant-ph/0510031

[28] Wim Lavrijsen, Ana Tudor, Juliane Müller, Costin Iancu, and Wibe de Jong. Classical optimizers for noisy intermediate-scale quantum devices. arXiv preprint arXiv:2004.03004, 2020. 10.1109/QCE49297.2020.00041.
https://doi.org/10.1109/QCE49297.2020.00041
arXiv:2004.03004

[29] Wolfgang Lechner, Philipp Hauke, and Peter Zoller. A quantum annealing architecture with all-to-all connectivity from local interactions. Science Advances, 1 (9): 1–6, 2015. ISSN 23752548. 10.1126/sciadv.1500838.
https://doi.org/10.1126/sciadv.1500838

[30] Harry Markowitz. Portfolio selection. The Journal of Finance, 7 (1): 77–91, 1952. 10.2307/2975974.
https://doi.org/10.2307/2975974

[31] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan. Quantum computational chemistry. Rev. Mod. Phys., 92: 015003, Mar 2020a. 10.1103/RevModPhys.92.015003.
https://doi.org/10.1103/RevModPhys.92.015003

[32] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan. Quantum computational chemistry. Reviews of Modern Physics, 92 (1), Mar 2020b. ISSN 1539-0756. 10.1103/revmodphys.92.015003.
https://doi.org/10.1103/revmodphys.92.015003

[33] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18 (2): 023023, feb 2016. 10.1088/1367-2630/18/2/023023.
https://doi.org/10.1088/1367-2630/18/2/023023

[34] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9 (1): 4812, 2018. 10.1038/s41467-018-07090-4.
https://doi.org/10.1038/s41467-018-07090-4

[35] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, Abhinav Kandala, Antonio Mezzacapo, Peter Müller, Walter Riess, Gian Salis, John Smolin, Ivano Tavernelli, and Kristan Temme. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology, 3 (3): 030503, jun 2018. 10.1088/2058-9565/aab822.
https://doi.org/10.1088/2058-9565/aab822

[36] J. S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E. Schuyler Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papageorge, E. C. Peterson, G. Prawiroatmodjo, N. Rubin, Colm A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, Robert S. Smith, A. Staley, N. Tezak, W. J. Zeng, A. Hudson, Blake R. Johnson, M. Reagor, M. P. da Silva, and C. Rigetti. Unsupervised machine learning on a hybrid quantum computer. arXiv preprint arXiv:1712.05771, 2017.
arXiv:1712.05771

[37] Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S. Collins, Arinjoy De, Paul W. Hess, Harvey B. Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin, and et al. Quantum approximate optimization of the long-range ising model with a trapped-ion quantum simulator. Proceedings of the National Academy of Sciences, 117 (41): 25396–25401, Oct 2020. ISSN 1091-6490. 10.1073/pnas.2006373117.
https://doi.org/10.1073/pnas.2006373117

[38] 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. 10.1038/ncomms5213.
https://doi.org/10.1038/ncomms5213

[39] M. Powell. A view of algorithms for optimization without derivatives. Mathematics TODAY, 43, 01 2007.

[40] John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2: 79, August 2018. ISSN 2521-327X. 10.22331/q-2018-08-06-79.
https://doi.org/10.22331/q-2018-08-06-79

[41] Xiaogang Qiang, Xiaoqi Zhou, Jianwei Wang, Callum M. Wilkes, Thomas Loke, Sean O’Gara, Laurent Kling, Graham D. Marshall, Raffaele Santagati, Timothy C. Ralph, Jingbo B. Wang, Jeremy L. O’Brien, Mark G. Thompson, and Jonathan C. F. Matthews. Large-scale silicon quantum photonics implementing arbitrary two-qubit processing. Nature Photonics, 12 (9): 534–539, 2018. 10.1038/s41566-018-0236-y.
https://doi.org/10.1038/s41566-018-0236-y

[42] Arthur G. Rattew, Shaohan Hu, Marco Pistoia, Richard Chen, and Steve Wood. A domain-agnostic, noise-resistant, hardware-efficient evolutionary variational quantum eigensolver. arXiv preprint arXiv:1910.09694, 2019.
arXiv:1910.09694

[43] Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, and Matthias Troyer. Defining and detecting quantum speedup. Science, 345 (6195): 420–424, 2014. ISSN 0036-8075. 10.1126/science.1252319.
https://doi.org/10.1126/science.1252319

[44] M Saffman. Quantum computing with atomic qubits and rydberg interactions: progress and challenges. Journal of Physics B: Atomic, Molecular and Optical Physics, 49 (20): 202001, oct 2016. 10.1088/0953-4075/49/20/202001.
https://doi.org/10.1088/0953-4075/49/20/202001

[45] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26 (5): 1484–1509, 1997. 10.1137/S0097539795293172.
https://doi.org/10.1137/S0097539795293172

[46] Kevin J Sung, Jiahao Yao, Matthew P Harrigan, Nicholas C Rubin, Zhang Jiang, Lin Lin, Ryan Babbush, and Jarrod R McClean. Using models to improve optimizers for variational quantum algorithms. Quantum Science and Technology, 5 (4): 044008, Oct 2020. ISSN 2058-9565. 10.1088/2058-9565/abb6d9.
https://doi.org/10.1088/2058-9565/abb6d9

[47] IBM Quantum team. Retrieved from https://quantum-computing.ibm.com. Ibmq, 2020.
https://quantum-computing.ibm.com

[48] G Wendin. Quantum information processing with superconducting circuits: a review. Reports on Progress in Physics, 80 (10): 106001, sep 2017. 10.1088/1361-6633/aa7e1a.
https://doi.org/10.1088/1361-6633/aa7e1a

[49] Madita Willsch, Dennis Willsch, Fengping Jin, Hans De Raedt, and Kristel Michielsen. Benchmarking the quantum approximate optimization algorithm. Quantum Information Processing, 19 (7), Jun 2020. ISSN 1573-1332. 10.1007/s11128-020-02692-8.
https://doi.org/10.1007/s11128-020-02692-8

[50] Stephen J. Wright. Continuous optimization (nonlinear and linear programming). In Nicholas J. Higham, Mark R. Dennis, Paul Glendinning, Paul A. Martin, Fadil Santosa, and Jared Tanner, editors, The Princeton Companion to Applied Mathematics, chapter 4, page 281–293. Princeton University Press, Princeton, 2015.

[51] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10 (2), Jun 2020. ISSN 2160-3308. 10.1103/physrevx.10.021067.
https://doi.org/10.1103/physrevx.10.021067

Cited by

[1] V. E. Zobov and I. S. Pichkovskiy, “Clustering by quantum annealing on three-level quantum elements qutrits”, arXiv:2102.09205.

[2] Adam Glos, Aleksandra Krawiec, and Zoltán Zimborás, “Space-efficient binary optimization for variational computing”, arXiv:2009.07309.

The above citations are from SAO/NASA ADS (last updated successfully 2021-05-08 00:27:05). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2021-05-08 00:27:03).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

Source: https://quantum-journal.org/papers/q-2021-05-04-454/

Time Stamp: May 4, 2021

Time Stamp: Jan 3, 2024

Qubit-efficient encoding schemes for binary optimisation problems

Republished By Plato

Abstract

Popular summary

► BibTeX data

► References

Cited by

More from Quantum Journal

Topological error correcting processes from fixed-point path integrals

Unbiasing time-dependent Variational Monte Carlo by projected quantum evolution

The minimal communication cost for simulating entangled qubits

Real-Time Krylov Theory for Quantum Computing Algorithms

Tight Cramér-Rao type bounds for multiparameter quantum metrology through conic programming

A probabilistic view of wave-particle duality for single photons

The quartic Blochnium: an anharmonic quasicharge superconducting qubit

20-Mode Universal Quantum Photonic Processor

Style-based quantum generative adversarial networks for Monte Carlo events

Designing the Quantum Channels Induced by Diagonal Gates

A review and reformulation of macroscopic realism: resolving its deficiencies using the framework of generalized probabilistic theories

About Us

Vertical Search & Ai

Platform

Stay Connected

Account