Accuracy and minor embedding in subqubo decomposition with fully connected large problems: a case study about the number partitioning problem
Authors:
Preprint
Abstract
In this work we investigate the capabilities of a hybrid quantum-classical procedure to explore the solution space using the D-Wave $2000Q^{TM}$ Quantum 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 analyse 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 11 references indexed in Scilit:
- Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum AnnealersPhysical Review Applied, 2019
- Quantum annealing for combinatorial clusteringQuantum Information Processing, 2018
- Traffic Flow Optimization Using a Quantum AnnealerFrontiers in ICT, 2017
- A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera GraphScientific Reports, 2016
- What is the Computational Value of Finite-Range Tunneling?Physical Review X, 2016
- Maximum-Entropy Inference with a Programmable AnnealerScientific Reports, 2016
- Quantum Optimization of Fully Connected Spin GlassesPhysical Review X, 2015
- Error-corrected quantum annealing with hundreds of qubitsNature Communications, 2014
- A new modeling and solution approach for the set-partitioning problemComputers & Operations Research, 2008
- Probabilistic Analysis of Packing and Partitioning Algorithms (E. G. Coffman, Jr. and George S. Lueker)SIAM Review, 1993