Accuracy and minor embedding in subqubo decomposition with fully connected large problems: a case study about the number partitioning problem
Authors:
Open Access
- 19 March 2020
- journal article
- research article
- Published by Springer Nature in Quantum Machine Intelligence
- Vol. 2 (1) , 1-7
Abstract
In this work, we investigate the capabilities of a hybrid quantum-classical procedure to explore the solution space using the D-Wave 2000QTMquantum annealer device. Here, we study the ability of the quantum hardware to solve the number partitioning problem, a well-known NP-hard optimization model that poses some challenges typical of those encountered in real-world applications. This represents one of the most complex scenario in terms of qubits connectivity and, by increasing the input problem size, we analyze the scaling properties of the quantum-classical workflow. We find remarkable results in most instances of the model; for the most complex ones, we investigate further the D-Wave Hybrid suite. Specifically, we were able to find the optimal solutions even in the worst cases by fine-tuning the parameters that schedule the annealing time and allowing a pause in the annealing cycle.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Compiling quantum circuits to realistic hardware architectures using temporal plannersQuantum Science and Technology, 2018
- Traffic Flow Optimization Using a Quantum AnnealerFrontiers in ICT, 2017
- Coherent Ising machines—optical neural networks operating at the quantum limitnpj Quantum Information, 2017
- A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera GraphScientific Reports, 2016
- Maximum-Entropy Inference with a Programmable AnnealerScientific Reports, 2016
- Error-corrected quantum annealing with hundreds of qubitsNature Communications, 2014
- Ising formulations of many NP problemsFrontiers in Physics, 2014
- A new modeling and solution approach for the set-partitioning problemComputers & Operations Research, 2008
- A Generalization of Linear Cryptanalysis and the Applicability of Matsui’s Piling-up Lemma1995
- Probabilistic Analysis of Packing and Partitioning Algorithms (E. G. Coffman, Jr. and George S. Lueker)SIAM Review, 1993