Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for 3-Regular MAXCUT and Higher-Round Scaling Limits ...
We generalize Farhi et al.'s 0.6924-approximation result technique of the Max-Cut Quantum Approximate Optimization Algorithm (QAOA) on 3-regular graphs to obtain provable lower bounds on the approximation ratio for warm-started QAOA. Given an initialization angle $θ$, we consider warm-starts wh...
Main Authors: | , |
---|---|
Format: | Report |
Language: | unknown |
Published: |
arXiv
2024
|
Subjects: | |
Online Access: | https://dx.doi.org/10.48550/arxiv.2402.12631 https://arxiv.org/abs/2402.12631 |
id |
ftdatacite:10.48550/arxiv.2402.12631 |
---|---|
record_format |
openpolar |
spelling |
ftdatacite:10.48550/arxiv.2402.12631 2024-03-31T07:55:23+00:00 Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for 3-Regular MAXCUT and Higher-Round Scaling Limits ... Tate, Reuben Eidenbenz, Stephan 2024 https://dx.doi.org/10.48550/arxiv.2402.12631 https://arxiv.org/abs/2402.12631 unknown arXiv arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ Quantum Physics quant-ph Data Structures and Algorithms cs.DS Emerging Technologies cs.ET Combinatorics math.CO Optimization and Control math.OC FOS Physical sciences FOS Computer and information sciences FOS Mathematics article Preprint Article CreativeWork 2024 ftdatacite https://doi.org/10.48550/arxiv.2402.12631 2024-03-04T13:50:25Z We generalize Farhi et al.'s 0.6924-approximation result technique of the Max-Cut Quantum Approximate Optimization Algorithm (QAOA) on 3-regular graphs to obtain provable lower bounds on the approximation ratio for warm-started QAOA. Given an initialization angle $θ$, we consider warm-starts where the initial state is a product state where each qubit position is angle $θ$ away from either the north or south pole of the Bloch sphere; of the two possible qubit positions the position of each qubit is decided by some classically obtained cut encoded as a bitstring $b$. We illustrate through plots how the properties of $b$ and the initialization angle $θ$ influence the bound on the approximation ratios of warm-started QAOA. We consider various classical algorithms (and the cuts they produce which we use to generate the warm-start). Our results strongly suggest that there does not exist any choice of initialization angle that yields a (worst-case) approximation ratio that simultaneously beats standard QAOA and the ... Report South pole DataCite Metadata Store (German National Library of Science and Technology) South Pole |
institution |
Open Polar |
collection |
DataCite Metadata Store (German National Library of Science and Technology) |
op_collection_id |
ftdatacite |
language |
unknown |
topic |
Quantum Physics quant-ph Data Structures and Algorithms cs.DS Emerging Technologies cs.ET Combinatorics math.CO Optimization and Control math.OC FOS Physical sciences FOS Computer and information sciences FOS Mathematics |
spellingShingle |
Quantum Physics quant-ph Data Structures and Algorithms cs.DS Emerging Technologies cs.ET Combinatorics math.CO Optimization and Control math.OC FOS Physical sciences FOS Computer and information sciences FOS Mathematics Tate, Reuben Eidenbenz, Stephan Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for 3-Regular MAXCUT and Higher-Round Scaling Limits ... |
topic_facet |
Quantum Physics quant-ph Data Structures and Algorithms cs.DS Emerging Technologies cs.ET Combinatorics math.CO Optimization and Control math.OC FOS Physical sciences FOS Computer and information sciences FOS Mathematics |
description |
We generalize Farhi et al.'s 0.6924-approximation result technique of the Max-Cut Quantum Approximate Optimization Algorithm (QAOA) on 3-regular graphs to obtain provable lower bounds on the approximation ratio for warm-started QAOA. Given an initialization angle $θ$, we consider warm-starts where the initial state is a product state where each qubit position is angle $θ$ away from either the north or south pole of the Bloch sphere; of the two possible qubit positions the position of each qubit is decided by some classically obtained cut encoded as a bitstring $b$. We illustrate through plots how the properties of $b$ and the initialization angle $θ$ influence the bound on the approximation ratios of warm-started QAOA. We consider various classical algorithms (and the cuts they produce which we use to generate the warm-start). Our results strongly suggest that there does not exist any choice of initialization angle that yields a (worst-case) approximation ratio that simultaneously beats standard QAOA and the ... |
format |
Report |
author |
Tate, Reuben Eidenbenz, Stephan |
author_facet |
Tate, Reuben Eidenbenz, Stephan |
author_sort |
Tate, Reuben |
title |
Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for 3-Regular MAXCUT and Higher-Round Scaling Limits ... |
title_short |
Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for 3-Regular MAXCUT and Higher-Round Scaling Limits ... |
title_full |
Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for 3-Regular MAXCUT and Higher-Round Scaling Limits ... |
title_fullStr |
Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for 3-Regular MAXCUT and Higher-Round Scaling Limits ... |
title_full_unstemmed |
Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for 3-Regular MAXCUT and Higher-Round Scaling Limits ... |
title_sort |
guarantees on warm-started qaoa: single-round approximation ratios for 3-regular maxcut and higher-round scaling limits ... |
publisher |
arXiv |
publishDate |
2024 |
url |
https://dx.doi.org/10.48550/arxiv.2402.12631 https://arxiv.org/abs/2402.12631 |
geographic |
South Pole |
geographic_facet |
South Pole |
genre |
South pole |
genre_facet |
South pole |
op_rights |
arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
op_doi |
https://doi.org/10.48550/arxiv.2402.12631 |
_version_ |
1795037220842766336 |