Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm

• URL: http://arxiv.org/abs/2504.01897v1
• Date: Wed, 02 Apr 2025 16:57:28 GMT
• Title: Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm
• Authors: Sivaprasad Omanakuttan, Zichang He, Zhiwei Zhang, Tianyi Hao, Arman Babakhani, Sami Boulebnane, Shouvanik Chakrabarti, Dylan Herman, Joseph Sullivan, Michael A. Perlin, Ruslan Shaydulin, Marco Pistoia,
• Abstract summary: We find that a quantum computer is unlikely to surpass classical state-of-the-art on optimization problems under realistic assumptions.<n>We further show that this restriction on classical solver energy consumption can be relaxed given optimistic but plausible reductions in physical error rates and fault-tolerance overheads.<n>These findings support the hypothesis that large-scale fault-tolerant quantum computers will be useful for optimization.
• Score: 6.328164687610608
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimization is often cited as a promising application of quantum computers. However, the low degree of provable quantum speedups has led prior rigorous end-to-end resource analyses to conclude that a quantum computer is unlikely to surpass classical state-of-the-art on optimization problems under realistic assumptions. In this work, we compile and analyze the Quantum Approximate Optimization Algorithm (QAOA) combined with Amplitude Amplification (AA) applied to random 8-SAT at the satisfiability threshold. Our compilation involves careful optimization of circuits for Hamiltonian simulation, which may be of independent interest. We use the analytical scaling of the time-to-solution for QAOA identified by PRX Quantum 5, 030348 (2024) and find that with QAOA depth $p=623$, QAOA+AA achieves a crossover with state-of-the-art classical heuristics at 179 variables and 14.99 hours of runtime when executed on a surface-code-based fault-tolerant quantum computer with 73.91 million physical qubits, a physical error rate of $10^{-3}$, and a $1~\mu$s code cycle time. Notably, we allow the classical solver to be parallelized as long as its total energy consumption is equal to that required for decoding in the surface code. We further show that this restriction on classical solver energy consumption can be relaxed given optimistic but plausible reductions in physical error rates and fault-tolerance overheads, enabling a crossover of 2.94 hours using 8.88 million physical qubits against a classical solver running on a supercomputer with $725,760$ CPU cores. These findings support the hypothesis that large-scale fault-tolerant quantum computers will be useful for optimization.

Related papers

• GroverGPT: A Large Language Model with 8 Billion Parameters for Quantum Searching [43.496857395654764]
  We explore the potential of leveraging Large Language Models to simulate the output of a quantum Turing machine.<n>A specialized model, GroverGPT, trained on over 15 trillion tokens.<n>It consistently outperformed OpenAI's GPT-4o (45% accuracy), achieving nearly 100% accuracy on 6- and 10-qubit datasets.<n>It also demonstrated strong generalization, surpassing 95% accuracy for systems with over 20 qubits when trained on 3- to 6-qubit data.
  arXiv  Detail & Related papers  (2024-12-30T20:23:10Z)
• Optimization by Decoded Quantum Interferometry [43.55132675053983]
  We introduce a quantum algorithm called Decoded Quantum Interferometry (DQI)<n>For approximating optimal fits to data over finite fields, DQI achieves a better approximation ratio than any time known to us.<n>We demonstrate this by benchmarking on an instance with over 30,000 variables.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer [0.3518016233072556]
  A superconducting quantum computer is used to investigate the performance of a hybrid quantum-classical algorithm.<n>We benchmark the quantum solver against similarly high-performing classicals.<n>A run-time analysis shows that the quantum solver on large-scale problems is competitive against Gurobi but short of others on a projected 100-qubit quantum computer.
  arXiv  Detail & Related papers  (2024-04-26T17:59:22Z)
• 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)
• Optimizing quantum gates towards the scale of logical qubits [78.55133994211627]
  A foundational assumption of quantum gates theory is that quantum gates can be scaled to large processors without exceeding the error-threshold for fault tolerance. Here we report on a strategy that can overcome such problems. We demonstrate it by choreographing the frequency trajectories of 68 frequency-tunablebits to execute single qubit while superconducting errors.
  arXiv  Detail & Related papers  (2023-08-04T13:39:46Z)
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  In this work, we integrate the potentials of quantum and classical techniques for optimization. We reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. We present numerous computational results from real quantum hardware.
  arXiv  Detail & Related papers  (2023-02-10T20:12:53Z)
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm [0.0]
  Trading fidelity for scale enables approximate classical simulators to run quantum circuits beyond exact methods. We characterize the fidelity for the quantum approximate optimization algorithm by the expectation value of the cost function it seeks to minimize. We benchmark the performance of quantum hardware in a realistic setup.
  arXiv  Detail & Related papers  (2022-06-13T17:45:59Z)
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm [0.7046417074932257]
  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.
  arXiv  Detail & Related papers  (2022-06-07T20:59:19Z)
• The QAOA with Few Measurements [4.713817702376467]
  The Approximate Quantum Optimization Algorithm (QAOA) was originally developed to solve optimization problems. Fully descriptive benchmarking techniques are often expensive for large numbers of qubits. Some experimental quantum computing platforms such as neutral atom quantum computers have slow repetition rates.
  arXiv  Detail & Related papers  (2022-05-13T18:42:20Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• 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)

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.