Improving Quantum Optimization to Achieve Quadratic Time Complexity

• URL: http://arxiv.org/abs/2501.13469v1
• Date: Thu, 23 Jan 2025 08:33:26 GMT
• Title: Improving Quantum Optimization to Achieve Quadratic Time Complexity
• Authors: Ji Jiang, Peisheng Huang, Zhiyi Wu, Xuandong Sun, Zechen Guo, Wenhui Huang, Libo Zhang, Yuxuan Zhou, Jiawei Zhang, Weijie Guo, Xiayu Linpeng, Song Liu, Wenhui Ren, Ziyu Tao, Ji Chu, Jingjing Niu, Youpeng Zhong, Dapeng Yu,
• Abstract summary: We introduce Penta-O, a level-wise parameter-setting strategy that eliminates the classical outer loop, maintains minimal sampling overhead, and ensures non-decreasing performance.<n>For a $p$-level QAOA, Penta-O achieves an unprecedented time complexity of $mathcalO(p2)$ and a sampling overhead proportional to $5p+1$.
• Score: 13.190476985206043
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for achieving quantum advantage in combinatorial optimization. However, its variational framework presents a long-standing challenge in selecting circuit parameters. In this work, we prove that the energy expectation produced by QAOA can be expressed as a trigonometric function of the final-level mixer parameter. Leveraging this insight, we introduce Penta-O, a level-wise parameter-setting strategy that eliminates the classical outer loop, maintains minimal sampling overhead, and ensures non-decreasing performance. This method is broadly applicable to the generic quadratic unconstrained binary optimization formulated as the Ising model. For a $p$-level QAOA, Penta-O achieves an unprecedented quadratic time complexity of $\mathcal{O}(p^2)$ and a sampling overhead proportional to $5p+1$. Through experiments and simulations, we demonstrate that QAOA enhanced by Penta-O achieves near-optimal performance with exceptional circuit depth efficiency. Our work provides a versatile tool for advancing variational quantum algorithms.

Related papers

• Iterative Interpolation Schedules for Quantum Approximate Optimization Algorithm [1.845978975395919]
  We present an iterative method that exploits the smoothness of optimal parameter schedules by expressing them in a basis of functions. We demonstrate our method achieves better performance with fewer optimization steps than current approaches. For the largest LABS instance, we achieve near-optimal merit factors with schedules exceeding 1000 layers, an order of magnitude beyond previous methods.
  arXiv  Detail & Related papers  (2025-04-02T12:53:21Z)
• Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
  We present a new method for calculating expectation values of operators that can be expressed as a linear combination of unitary (LCU) operators. This method is general for any quantum algorithm and is of particular interest in the acceleration of variational quantum algorithms.
  arXiv  Detail & Related papers  (2025-03-03T17:15:23Z)
• Application of Langevin Dynamics to Advance the Quantum Natural Gradient Optimization Algorithm [47.47843839099175]
  A Quantum Natural Gradient (QNG) algorithm for optimization of variational quantum circuits has been proposed recently. In this study, we employ the Langevin equation with a QNG force to demonstrate that its discrete-time solution gives a generalized form, which we call Momentum-QNG.
  arXiv  Detail & Related papers  (2024-09-03T15:21:16Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Efficient and Robust Parameter Optimization of the Unitary Coupled-Cluster Ansatz [4.607081302947026]
  We propose sequential optimization with approximate parabola (SOAP) for parameter optimization of unitary coupled-cluster ansatz on quantum computers. Numerical benchmark studies on molecular systems demonstrate that SOAP achieves significantly faster convergence and greater robustness to noise. SOAP is further validated through experiments on a superconducting quantum computer using a 2-qubit model system.
  arXiv  Detail & Related papers  (2024-01-10T03:30:39Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  We propose a faster digital quantum algorithm for portfolio optimization using the digitized-counterdiabatic quantum optimization (DCQO) paradigm. Our approach notably reduces the circuit depth requirement of the algorithm and enhances the solution accuracy, making it suitable for current quantum processors. We experimentally demonstrate the advantages of our protocol using up to 20 qubits on an IonQ trapped-ion quantum computer.
  arXiv  Detail & Related papers  (2023-08-29T17:53:08Z)
• Quantum approximate optimization via learning-based adaptive optimization [5.399532145408153]
  Quantum approximate optimization algorithm (QAOA) is designed to solve objective optimization problems. Our results demonstrate that the algorithm greatly outperforms conventional approximations in terms of speed, accuracy, efficiency and stability. This work helps to unlock the full power of QAOA and paves the way toward achieving quantum advantage in practical classical tasks.
  arXiv  Detail & Related papers  (2023-03-27T02:14:56Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm [0.0]
  We propose a strategy to give high approximation ratio on average, even at large circuit depths, by initializing QAOA with the optimal parameters obtained from the previous depths. We test our strategy on the Max-cut problem of certain classes of graphs such as the 3-regular graphs and the Erd"os-R'enyi graphs.
  arXiv  Detail & Related papers  (2021-08-11T15:44:16Z)
• Mixer-Phaser Ans\"atze for Quantum Optimization with Hard Constraints [1.011960004698409]
  We introduce parametrized circuit ans"atze and present the results of a numerical study comparing their performance with a standard Quantum Alternating Operator Ansatz approach. The ans"atze are inspired by mixing and phase separation in the QAOA, and also motivated by compilation considerations with the aim of running on near-term superconducting quantum processors.
  arXiv  Detail & Related papers  (2021-07-13T04:50:56Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)
• Accelerating Quantum Approximate Optimization Algorithm using Machine Learning [6.735657356113614]
  We propose a machine learning based approach to accelerate quantum approximate optimization algorithm (QAOA) implementation. QAOA is a quantum-classical hybrid algorithm to prove the so-called quantum supremacy. We show that the proposed approach can curtail the number of optimization iterations by up to 65.7%) from an analysis performed with 264 flavors of graphs.
  arXiv  Detail & Related papers  (2020-02-04T02:21:00Z)

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.