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 a 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 4-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 linear $\alpha \propto 1$ to quadratic $\alpha \propto 2$ scaling with the number of logical qubits.

References in corpus (1)

• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design

Cited by in corpus (6)

• Rydberg blockade based parity quantum optimization
• Modular Parity Quantum Approximate Optimization
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• A scalable 2-local architecture for quantum annealing of Ising models with arbitrary dimensions
• Four-body coupler for superconducting qubits based on Josephson parametric oscillators
• Improving success probability in the LHZ parity embedding by computing with quantum walks