Continuous black-box optimization with quantum annealing and random subspace coding

• URL: http://arxiv.org/abs/2104.14778v1
• Date: Fri, 30 Apr 2021 06:19:07 GMT
• Title: Continuous black-box optimization with quantum annealing and random subspace coding
• Authors: Syun Izawa, Koki Kitai, Shu Tanaka, Ryo Tamura, Koji Tsuda
• Abstract summary: A black-box optimization algorithm such as Bayesian optimization finds extremum of an unknown function by alternating inference of the underlying function and optimization of an acquisition function. In a high-dimensional space, such algorithms perform poorly due to the difficulty of acquisition function optimization. We apply quantum annealing to overcome the difficulty in the continuous black-box optimization.
• Score: 2.839269856680851
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A black-box optimization algorithm such as Bayesian optimization finds extremum of an unknown function by alternating inference of the underlying function and optimization of an acquisition function. In a high-dimensional space, such algorithms perform poorly due to the difficulty of acquisition function optimization. Herein, we apply quantum annealing (QA) to overcome the difficulty in the continuous black-box optimization. As QA specializes in optimization of binary problems, a continuous vector has to be encoded to binary, and the solution of QA has to be translated back. Our method has the following three parts: 1) Random subspace coding based on axis-parallel hyperrectangles from continuous vector to binary vector. 2) A quadratic unconstrained binary optimization (QUBO) defined by acquisition function based on nonnegative-weighted linear regression model which is solved by QA. 3) A penalization scheme to ensure that the QA solution can be translated back. It is shown in benchmark tests that its performance using D-Wave Advantage$^{\rm TM}$ quantum annealer is competitive with a state-of-the-art method based on the Gaussian process in high-dimensional problems. Our method may open up a new possibility of quantum annealing and other QUBO solvers including quantum approximate optimization algorithm (QAOA) using a gated-quantum computers, and expand its range of application to continuous-valued problems.

Related papers

• Quantum molecular docking with quantum-inspired algorithm [4.959284967789063]
  We propose a novel quantum molecular docking (QMD) approach based on QA-inspired algorithm. We construct two binary encoding methods to efficiently discretize the degrees of freedom with exponentially reduced number of bits. We show that QMD has shown advantages over the search-based Auto Vina and the deep-learning DIFFDOCK in both re-docking and self-docking scenarios.
  arXiv  Detail & Related papers  (2024-04-12T06:24:45Z)
• GRAPE optimization for open quantum systems with time-dependent decoherence rates driven by coherent and incoherent controls [77.34726150561087]
  The GRadient Ascent Pulse Engineering (GRAPE) method is widely used for optimization in quantum control. We adopt GRAPE method for optimizing objective functionals for open quantum systems driven by both coherent and incoherent controls. The efficiency of the algorithm is demonstrated through numerical simulations for the state-to-state transition problem.
  arXiv  Detail & Related papers  (2023-07-17T13:37:18Z)
• Trainable Variational Quantum-Multiblock ADMM Algorithm for Generation Scheduling [0.0]
  This paper proposes a two-loop quantum solution algorithm for generation scheduling by quantum computing, machine learning, and distributed optimization. The aim is to facilitate noisy employing near-term quantum machines with a limited number of qubits to solve practical power system problems.
  arXiv  Detail & Related papers  (2023-03-28T21:31:39Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Accelerated Convergence of Contracted Quantum Eigensolvers through a Quasi-Second-Order, Locally Parameterized Optimization [0.0]
  A contracted quantum eigensolver (CQE) finds a solution to the many-electron Schr"odinger equation on a quantum computer. In this work, we accelerate the convergence of the CQE and its wavefunction ansatz via tools from classical optimization theory.
  arXiv  Detail & Related papers  (2022-05-03T18:48:04Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Improving the Quantum Approximate Optimization Algorithm with postselection [0.0]
  Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. We consider a well-studied quantum algorithm for optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable.
  arXiv  Detail & Related papers  (2020-11-10T22:17:50Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers [3.04585143845864]
  We present a decomposition-based approach to extend the applicability of current approaches to "quadratic plus convex" mixed binary optimization problems. We show that the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved with quantum algorithms) The validity of the approach is then showcased by numerical results obtained on several optimization problems via simulations with VQE and QAOA on the quantum circuits implemented in Qiskit.
  arXiv  Detail & Related papers  (2020-01-07T14:43:13Z)

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.