Solving various NP-hard problems using exponentially fewer qubits on a quantum computer
Top Cited Papers
- 30 May 2024
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 109 (5) , 052441
Abstract
NP-hard problems are not believed to be exactly solvable through general polynomial time algorithms. Hybrid quantum-classical algorithms to address such combinatorial problems have been of great interest in the past few years. Such algorithms are heuristic in nature and aim to obtain an approximate solution. Significant improvements in computational time and/or the ability to treat large problems are some of the principal promises of quantum computing in this regard. The hardware, however, is still in its infancy and the current noisy intermediate-scale quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions. An issue with quantum optimization algorithms such as the quantum approximate optimization algorithm is that they scale linearly with problem size. In this paper, we build upon a proprietary methodology which scales logarithmically with problem size—opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. To test the performance of the algorithm, we first find a way to apply it to a handful of NP-hard problems: Maximum Cut, Minimum Partition, Maximum Clique, Maximum Weighted Independent Set. Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.Keywords
All Related Versions
Funding Information
- Horizon 2020 (951821)
This publication has 38 references indexed in Scilit:
- The Variational Quantum Eigensolver: A review of methods and best practicesPhysics Reports, 2022
- Efficient Encoding of the Weighted MAX $k$-CUT on a Quantum Computer Using QAOASN Computer Science, 2021
- Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models4OR, 2019
- A variational eigenvalue solver on a photonic quantum processorNature Communications, 2014
- Survey of polynomial transformations between NP-complete problemsJournal of Computational and Applied Mathematics, 2011
- Measurement-based quantum computationNature Physics, 2009
- Efficient Quantum Algorithms for Simulating Sparse HamiltoniansCommunications in Mathematical Physics, 2006
- Finding good approximate vertex and edge partitions is NP-hardInformation Processing Letters, 1992
- Determining the total colouring number is np-hardDiscrete Mathematics, 1989
- Simulating physics with computersInternational Journal of Theoretical Physics, 1982