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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 01, 2021
- Source ID
- 10.1088/1367-2630/ac1897
Entities
People
- Martin Lanthaler
- Wolfgang Lechner
Organizations
- Austrian Science Fund
- Defense Advanced Research Projects Agency