On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks

• URL: http://arxiv.org/abs/2209.14501v2
• Date: Mon, 22 May 2023 04:56:11 GMT
• Title: On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Authors: Yizhou Liu, Weijie J. Su, Tongyang Li
• Abstract summary: We show that classical algorithms can't efficiently hit one well knowing the other well but Q can when given proper initial states the well. We construct a specific double-well landscape, where classical algorithms cannot efficiently hit one well knowing the other well but Q can when given proper initial states the well.
• Score: 31.228956832890393
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Classical algorithms are often not effective for solving nonconvex optimization problems where local minima are separated by high barriers. In this paper, we explore possible quantum speedups for nonconvex optimization by leveraging the global effect of quantum tunneling. Specifically, we introduce a quantum algorithm termed the quantum tunneling walk (QTW) and apply it to nonconvex problems where local minima are approximately global minima. We show that QTW achieves quantum speedup over classical stochastic gradient descents (SGD) when the barriers between different local minima are high but thin and the minima are flat. Based on this observation, we construct a specific double-well landscape, where classical algorithms cannot efficiently hit one target well knowing the other well but QTW can when given proper initial states near the known well. Finally, we corroborate our findings with numerical experiments.

Related papers

• Large-scale quantum annealing simulation with tensor networks and belief propagation [0.0]
  We show that quantum annealing for 3-regular graphs can be classically simulated even at scales of 1000 qubits and 5000000qubit gates. For non-degenerate instances, the unique solution can be read out from the final reduced single-qubit states. For degenerate problems, such as MaxCut, we introduce an approximate measurement simulation algorithm for graph tensor-network states.
  arXiv  Detail & Related papers  (2024-09-18T18:00:08Z)
• Solving The Travelling Salesman Problem Using A Single Qubit [0.0]
  The travelling salesman problem (TSP) is a popular NP-hard-combinatorial optimization problem. We present an algorithm that solves an arbitrary TSP using a single qubit by invoking the principle of quantum parallelism. The underlying framework of our algorithm is a quantum version of the classical Brachistochrone approach.
  arXiv  Detail & Related papers  (2024-07-24T12:06:37Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Quantum Bayesian Optimization [64.58749619145908]
  We introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm. It is the first BO algorithm able to achieve a regret upper bound of O(polylog T), which is significantly smaller than its regret lower bound of Omega(sqrt(T)) in the classical setting. Thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves a smaller regret than the quantum linear UCB algorithm.
  arXiv  Detail & Related papers  (2023-10-09T03:10:42Z)
• Training variational quantum algorithms with random gate activation [2.297921151044199]
  Variational quantum algorithms (VQAs) hold great potentials for near-term applications. VQAs suffer from severe barren plateau problem as well as have a large probability of being trapped in local minima. We propose a novel training algorithm with random quantum gate activation for VQAs to efficiently address these two issues.
  arXiv  Detail & Related papers  (2023-03-14T18:01:46Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Surviving The Barren Plateau in Variational Quantum Circuits with Bayesian Learning Initialization [0.0]
  Variational quantum-classical hybrid algorithms are seen as a promising strategy for solving practical problems on quantum computers in the near term. Here, we introduce the fast-and-slow algorithm, which uses gradients to identify a promising region in Bayesian space. Our results move variational quantum algorithms closer to their envisioned applications in quantum chemistry, optimization, and quantum simulation problems.
  arXiv  Detail & Related papers  (2022-03-04T17:48:57Z)
• 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)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  Variational quantum algorithms (VQAs) have the potential of utilizing near-term quantum machines to gain certain computational advantages. Modern VQAs suffer from cumbersome computational overhead, hampered by the tradition of employing a solitary quantum processor to handle large data. Here we devise an efficient distributed optimization scheme, called QUDIO, to address this issue.
  arXiv  Detail & Related papers  (2021-06-24T08:18:42Z)
• Optimal training of variational quantum algorithms without barren plateaus [0.0]
  Variational quantum algorithms (VQAs) promise efficient use of near-term quantum computers. We show how to optimally train a VQA for learning quantum states. We propose the application of Gaussian kernels for quantum machine learning.
  arXiv  Detail & Related papers  (2021-04-29T17:54:59Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.