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. 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:
• 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

• 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. Momentum-QNG is more effective to escape local minima and plateaus in the variational parameter space.
  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)
• 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)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• 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.