Please use this identifier to cite or link to this item:
Title: Qubit-efficient encoding schemes for binary optimisation problems
Authors: Tan, B.
Lemonde, M.-A.
Thanasilp, S.
Tangpanitanon, J.
Angelakis, D.G.
Issue Date: 26-Apr-2021
Publisher: Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
Citation: Tan, B., Lemonde, M.-A., Thanasilp, S., Tangpanitanon, J., Angelakis, D.G. (2021-04-26). Qubit-efficient encoding schemes for binary optimisation problems. Quantum 5. ScholarBank@NUS Repository.
Rights: Attribution 4.0 International
Abstract: We propose and analyze a set of variational quantum algorithms for solving quadratic unconstrained binary optimization problems where a problem consisting of nc classical variables can be implemented on O(log nc) 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 MaxCut 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. Our encoding scheme allows current generations of quantum hardware to explore the boundaries of classical intractability involving real world problem sizes, and can be implemented on currently available quantum hardware across various platforms, requiring only few dozens of qubits. © 2021 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften. All rights reserved.
Source Title: Quantum
ISSN: 2521-327X
DOI: 10.22331/q-2021-04-26-441
Rights: Attribution 4.0 International
Appears in Collections:Department Publications

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
10_22331_q-2021-04-26-441.pdf5.3 MBAdobe PDF


NoneLog In


checked on Oct 26, 2022

Page view(s)

checked on Dec 1, 2022

Google ScholarTM



This item is licensed under a Creative Commons License Creative Commons