Benchmark test of Black-box optimization using D-Wave quantum annealer
arXiv:2103.12320 · doi:10.7566/JPSJ.90.064001
Abstract
In solving optimization problems, objective functions generally need to be minimized or maximized. However, objective functions cannot always be formulated explicitly in a mathematical form for complicated problem settings. Although several regression techniques infer the approximate forms of objective functions, they are at times expensive to evaluate. Optimal points of "black-box" objective functions are computed in such scenarios, while effectively using a small number of clues. Recently, an efficient method by use of inference by sparse prior for a black-box objective function with binary variables has been proposed. In this method, a surrogate model was proposed in the form of a quadratic unconstrained binary optimization (QUBO) problem, and was iteratively solved to obtain the optimal solution of the black-box objective function. In the present study, we employ the D-Wave 2000Q quantum annealer, which can solve QUBO by driving the binary variables by quantum fluctuations. The D-Wave 2000Q quantum annealer does not necessarily output the ground state at the end of the protocol due to freezing effect during the process. We investigate effects from the output of the D-Wave quantum annealer in performing black-box optimization. We demonstrate a benchmark test by employing the sparse Sherrington-Kirkpatrick (SK) model as the black-box objective function, by introducing a parameter controlling the sparseness of the interaction coefficients. Comparing the results of the D-Wave quantum annealer to those of the simulated annealing (SA) and semidefinite programming (SDP), our results by the D-Wave quantum annealer and SA exhibit superiority in black-box optimization with SDP. On the other hand, we did not find any advantage of the D-Wave quantum annealer over the simulated annealing. As far as in our case, any effects by quantum fluctuation are not found.
22 pages, 4 figures
References in corpus (24)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Theory of Quantum Annealing of an Ising Spin Glass
- Mathematical Foundation of Quantum Annealing
- Quantum Boltzmann Machine
- A simple sampler for the horseshoe estimator
- Quantum annealing of the Traveling Salesman Problem
- Efficient partition of integer optimization problems with one-hot encoding
- Expanding the horizon of automated metamaterials discovery via quantum annealing
- Quantum Speedup by Quantum Annealing
- Searching for quantum speedup in quasistatic quantum annealers
- Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
- Quantum annealing with antiferromagnetic fluctuations
- Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
- Efficiency of quantum versus classical annealing in non-convex learning problems
- Residual Energies after Slow Quantum Annealing
- Quantum annealing with Jarzynski equality
- Experimental and Theoretical Study of Thermodynamic Effects in a Quantum Annealer
- Statistical-mechanical analysis of compressed sensing for Hamiltonian estimation of Ising spin glass
- Nonequilibrium work on spin glasses in longitudinal and transverse fields
- Dynamics of Order Parameters of Non-stoquastic Hamiltonians in the Adaptive Quantum Monte Carlo Method
- Efficient quantum and simulated annealing of Potts models using a half-hot constraint
- Nonequilibrium work performed in quantum annealing
- Message-passing algorithm of quantum annealing with nonstoquastic Hamiltonian
Cited by in corpus (18)
- Travel time optimization on multi-AGV routing by reverse annealing
- Application of QUBO solver using black-box optimization to structural design for resonance avoidance
- Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
- NIMS-OS: An automation software to implement a closed loop between artificial intelligence and robotic experiments in materials science
- Comparing the effects of Boltzmann machines as associative memory in Generative Adversarial Networks between classical and quantum sampling
- Virtual Screening of Chemical Space based on Quantum Annealing
- Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing
- Phase transition of Frustrated Ising model via D-wave Quantum Annealing Machine
- Lossy compression of matrices by black-box optimisation of mixed integer nonlinear programming
- Exploration of new chemical materials using black-box optimization with the D-wave quantum annealer
- Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing
- Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing
- Online calibration scheme for training restricted Boltzmann machines with quantum annealing
- Random Postprocessing for Combinatorial Bayesian Optimization
- Subgradient Method using Quantum Annealing for Inequality-Constrained Binary Optimization Problems
- Impact of Fixing Spins in a Quantum Annealer with Energy Rescaling
- Subsampling Factorization Machine Annealing
- Statistical quality assessment of Ising-based annealer outputs