Sampling Frequency Thresholds for Quantum Advantage of Quantum
Approximate Optimization Algorithm
- URL: http://arxiv.org/abs/2206.03579v2
- Date: Tue, 25 Jul 2023 17:27:39 GMT
- Title: Sampling Frequency Thresholds for Quantum Advantage of Quantum
Approximate Optimization Algorithm
- Authors: Danylo Lykov, Jonathan Wurtz, Cody Poole, Mark Saffman, Tom Noel, Yuri
Alexeev
- Abstract summary: We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers.
We find that classical solvers are capable of producing high-quality approximate solutions in linear time complexity.
Other problems, such as different graphs, weighted MaxCut, maximum independent set, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.
- Score: 0.7046417074932257
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we compare the performance of the Quantum Approximate
Optimization Algorithm (QAOA) with state-of-the-art classical solvers such as
Gurobi and MQLib to solve the combinatorial optimization problem MaxCut on
3-regular graphs. The goal is to identify under which conditions QAOA can
achieve "quantum advantage" over classical algorithms, in terms of both
solution quality and time to solution. One might be able to achieve quantum
advantage on hundreds of qubits and moderate depth $p$ by sampling the QAOA
state at a frequency of order 10 kHz. We observe, however, that classical
heuristic solvers are capable of producing high-quality approximate solutions
in linear time complexity. In order to match this quality for $\textit{large}$
graph sizes $N$, a quantum device must support depth $p>11$. Otherwise, we
demonstrate that the number of required samples grows exponentially with $N$,
hindering the scalability of QAOA with $p\leq11$. These results put challenging
bounds on achieving quantum advantage for QAOA MaxCut on 3-regular graphs.
Other problems, such as different graphs, weighted MaxCut, maximum independent
set, and 3-SAT, may be better suited for achieving quantum advantage on
near-term quantum devices.
Related papers
- Recursive Quantum Relaxation for Combinatorial Optimization Problems [3.3053321430025258]
We show that some existing quantum optimization methods can be unified into a solver that finds the binary solution that is most likely measured from the optimal quantum state.
Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner using a tensor network technique, show that RQRAO outperforms the Goemans--Williamson method and is comparable to state-of-the-art classical solvers.
arXiv Detail & Related papers (2024-03-04T13:48:21Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - Single-Layer Digitized-Counterdiabatic Quantum Optimization for $p$-spin
Models [8.463477025989542]
We take advantage of a digitized-counterdiabatic quantum optimization (DCQO) algorithm to find an optimal solution of the $p$-spin model up to 4-local interactions.
By further optimizing parameters using variational methods, we solve with unit accuracy 2-spin, 3-spin, and 4-spin problems for $100%$, $93%$, and $83%$ of instances, respectively.
arXiv Detail & Related papers (2023-11-11T22:49:16Z) - Alleviating the quantum Big-$M$ problem [0.237499051649312]
Classically known as the "Big-$M$" problem, it affects the physical energy scale.
We take a systematic, encompassing look at the quantum big-$M$ problem, revealing NP-hardness in finding the optimal $M$.
We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks.
arXiv Detail & Related papers (2023-07-19T18:00:05Z) - NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization [0.0]
We present an approximate gradient-based quantum algorithm for hardware-efficient circuits with amplitude encoding.
We show how simple linear constraints can be directly incorporated into the circuit without additional modification of the objective function with penalty terms.
arXiv Detail & Related papers (2023-05-23T16:17:57Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution.
We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines.
Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
arXiv Detail & Related papers (2022-05-24T03:49:10Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity.
We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree.
These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
arXiv Detail & Related papers (2022-01-06T21:02:30Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard.
We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware.
The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.