Minimal constraints in the parity formulation of optimization problems

Abstract

As a means to solve optimization problems using quantum computers, the problem is typically recast into an Ising spin model whose ground-state is the solution of the optimization problem. An alternative to the Ising formulation is the Lechner–Hauke–Zoller model, which has the form of a lattice gauge model with nearest neighbor four-body constraints. Here we introduce a method to find the minimal strength of the constraints which are required to conserve the correct ground-state. Based on this, we derive upper and lower bounds for the minimal constraints strengths. We find that, depending on the problem class, the exponent ranges from constant α = 0 to quadratic α = 2 scaling with the number of logical qubits.

Keywords

• quantum optimization
• quantum annealing
• adiabatic quantum computation
• LHZ architecture
• Ising formulation of optimization problems