Quick Navigation

Overview Topics Abstract Importance Paper Tools References Reactions Discussion Publication Related

Topics

Quantum Optimization

A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem

arXiv

Authors: Edward Farhi, Jeffrey Goldstone, Sam Gutmann

Year

2014

Paper ID

45818

Status

Preprint

Abstract Read

~2 min

Abstract Words

132

Citations

N/A

Abstract

We apply our recent Quantum Approximate Optimization Algorithm to the combinatorial problem of bounded occurrence Max E3LIN2. The input is a set of linear equations each of which contains exactly three boolean variables and each equation says that the sum of the variables mod 2 is 0 or is 1. Every variable is in no more than D equations. A random string will satisfy 1/2 of the equations. We show that the level one QAOA will efficiently produce a string that satisfies left\(frac{1}{2} + frac{1}{101 D^1/2 l n D}right\) times the number of equations. A recent classical algorithm achieved left\(frac{1}{2} + frac{constant}{D^1/2}right\). We also show that in the typical case the quantum computer will output a string that satisfies left\(frac{1}{2}+ frac{1}{2sqrt{3e} D^1/2}right\) times the number of equations.

Why This Paper Matters

This paper contributes to the Quantum Optimization research area in the Quantum Articles archive.
It adds a 2014 reference point for readers tracking recent quantum research.
We apply our recent Quantum Approximate Optimization Algorithm to the combinatorial problem of bounded occurrence Max E3LIN2.

Paper Tools

Become a member to use research tools

Sign in to open papers, visit source links, share, cite, compare, copy DOI links, request category corrections, and build your reading list.

Become a member Sign in

Show Paper arXiv Publisher Share Cite This Paper Copy URL Compare Copy DOI Add to Reading List Category Correction Request

References & Citation Signals

[1] DOI https://doi.org/arXiv:1412.6062 [2] arXiv https://arxiv.org/abs/1412.6062 [3] Publisher https://arxiv.org/abs/1412.6062

Local Citation Graph (Related-Paper Links)

External citation index: OpenAlex citation signal

Community Reactions

Quick sentiment from readers on this paper.

Score: 0

Likes: 0 Dislikes: 0

Discussion & Reviews (Moderated)

Average Rating: 0.0 / 5 (0 ratings)

No written reviews yet.