Accuracy and minor embedding in subqubo decomposition with fully connected large problems: a case study about the number partitioning problem

2019/07/01 by Asproni, Luca, Caputo, Davide, Silva, Blanca +2 · 1 citation
#FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.1907.01892

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.

Cited by

• Programmable 200 GOPS Hopfield-inspired photonic Ising machine

Related

• Testing a QUBO Formulation of Core-periphery Partitioning on a Quantum Annealer
• Optimizing the Optimizer: Decomposition Techniques for Quantum Annealing
• Efficient Combinatorial Optimization Using Quantum Annealing
• Quantum annealing applications, challenges and limitations for optimisation problems compared to classical solvers
• Divide-and-conquer embedding for QUBO quantum annealing