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 (18)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Adiabatic Quantum Computing
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Defining and detecting quantum speedup
• Perspectives of quantum annealing: Methods and implementations
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• A Coherent Quantum Annealer with Rydberg Atoms
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Training A Quantum Optimizer
• Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• The Sherrington-Kirkpatrick model: an overview
• Rapid counter-diabatic sweeps in lattice gauge adiabatic quantum computing
• Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
• Quantum phase transition with inhomogeneous driving in the Lechner-Hauke-Zoller model
• On the dynamics of Simulated Quantum Annealing in random Ising chains

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