(Sub)Exponential Quantum Speedup for Optimization

• URL: http://arxiv.org/abs/2504.14841v1
• Date: Mon, 21 Apr 2025 03:44:46 GMT
• Title: (Sub)Exponential Quantum Speedup for Optimization
• Authors: Jiaqi Leng, Kewen Wu, Xiaodi Wu, Yufan Zheng,
• Abstract summary: We demonstrate provable (sub)exponential quantum speedups in both discrete and continuous optimization.<n>Our result builds on the Gily'en--Hastings--Vazirani (sub)exponential oracle separation for adiabatic quantum computing.
• Score: 6.420160601441722
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We demonstrate provable (sub)exponential quantum speedups in both discrete and continuous optimization, achieved through simple and natural quantum optimization algorithms, namely the quantum adiabatic algorithm for discrete optimization and quantum Hamiltonian descent for continuous optimization. Our result builds on the Gily\'en--Hastings--Vazirani (sub)exponential oracle separation for adiabatic quantum computing. With a sequence of perturbative reductions, we compile their construction into two standalone objective functions, whose oracles can be directly leveraged by the plain adiabatic evolution and Schr\"odinger operator evolution for discrete and continuous optimization, respectively.

Related papers

• 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)
• Optimizing Unitary Coupled Cluster Wave Functions on Quantum Hardware: Error Bound and Resource-Efficient Optimizer [0.0]
  We study the projective quantum eigensolver (PQE) approach to optimizing unitary coupled cluster wave functions on quantum hardware. The algorithm uses projections of the Schr"odinger equation to efficiently bring the trial state closer to an eigenstate of the Hamiltonian. We present numerical evidence of superiority over both the optimization introduced in arXiv:2102.00345 and VQE optimized using the Broyden Fletcher Goldfarb Shanno (BFGS) method.
  arXiv  Detail & Related papers  (2024-10-19T15:03:59Z)
• 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.<n>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)
• Multi-qubit quantum state preparation enabled by topology optimization [0.0]
  We inverse-design nanophotonic cavities enabling the preparation of pure states of pairs and triples of quantum emitters. Our findings open the way towards the efficient and fast preparation of multiqubit quantum states with engineered features.
  arXiv  Detail & Related papers  (2024-05-24T08:52:22Z)
• Photonic counterdiabatic quantum optimization algorithm [3.2174634059872154]
  We propose a hybrid quantum- approximate optimization algorithm for quantum computing that is tailored for continuous-variable problems. We conduct proof-of-principle experiments on an-photo quantum chip.
  arXiv  Detail & Related papers  (2023-07-27T13:33:33Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• A self-consistent field approach for the variational quantum eigensolver: orbital optimization goes adaptive [52.77024349608834]
  We present a self consistent field approach (SCF) within the Adaptive Derivative-Assembled Problem-Assembled Ansatz Variational Eigensolver (ADAPTVQE) This framework is used for efficient quantum simulations of chemical systems on nearterm quantum computers.
  arXiv  Detail & Related papers  (2022-12-21T23:15:17Z)
• Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
  We propose a new first-order optimization algorithm -- AcceleratedGradient-OptimisticGradient (AG-OG) Ascent. We show that AG-OG achieves the optimal convergence rate (up to a constant) for a variety of settings. We extend our algorithm to extend the setting and achieve the optimal convergence rate in both bi-SC-SC and bi-C-SC settings.
  arXiv  Detail & Related papers  (2022-10-31T17:59:29Z)
• Quantum Optimisation for Continuous Multivariable Functions by a Structured Search [0.0]
  Quantum variational algorithms leverage quantum superposition and entanglement to optimise over exponentially large solution spaces. We show that quantum variational algorithms can efficiently optimise continuous multivariable functions by exploiting general structural properties of a discretised continuous solution space.
  arXiv  Detail & Related papers  (2022-10-12T14:16:06Z)
• Digitized-Counterdiabatic Quantum Optimization [4.336065967298193]
  We propose digitized-diabatic quantum optimization (DCQO) to achieve enhancement over adiabatic quantum optimization for the general Ising spin-glass model. This is accomplished via the digitization of adiabatic quantum algorithms that are catalysed by the addition of non-stoquastic counterdiabatic terms.
  arXiv  Detail & Related papers  (2022-01-03T18:21:54Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Quantum Permutation Synchronization [88.4588059792167]
  We present QuantumSync, the quantum algorithm for solving a quantum vision problem in the context of computer vision. We show how to insert permutation constraints into a QUBO problem and to solve the constrained QUBO problem on the current generation of the abatic quantum DWave computer.
  arXiv  Detail & Related papers  (2021-01-19T17:51:02Z)
• 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)

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.