1
|
Müller S, Phillipson F. Quantum annealing for nearest neighbour compliance problem. Sci Rep 2024; 14:23340. [PMID: 39375466 PMCID: PMC11458877 DOI: 10.1038/s41598-024-73882-y] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/30/2024] [Accepted: 09/23/2024] [Indexed: 10/09/2024] Open
Abstract
Quantum Computing has emerged as a promising alternative, utilising quantum mechanics for faster computations. This paper explores the nearest neighbour compliance (NNC) Problem in Gate-based Quantum Computers, where quantum gates are constrained to operate on physically adjacent qubits. The NNC problem aims to optimise the insertion of SWAP-gates to ensure compliance with these constraints while minimising their count. This work introduces Quantum Annealing to tackle the NNC problem, proposing two Quadratic Unconstrained Optimisation Problem formulations. The formulations are tested on a contemporary Quantum Annealer, and their performance is compared with previous methods. It shows that the prospect of using Quantum Annealing is promising, however, the current state of the hardware makes that finding the embedding is the limiting factor.
Collapse
Affiliation(s)
- Sven Müller
- School of Business and Economics, Maastricht University, Minderbroedersberg 4, 6211 LK, Maastricht, The Netherlands
| | - Frank Phillipson
- School of Business and Economics, Maastricht University, Minderbroedersberg 4, 6211 LK, Maastricht, The Netherlands.
- Applied Cryptography and Quantum Algorithms, TNO, Anna van Buerenplein 1, 2595 DA, The Hague, The Netherlands.
| |
Collapse
|
2
|
Endo K, Matsuda Y, Tanaka S, Muramatsu M. Novel real number representations in Ising machines and performance evaluation: Combinatorial random number sum and constant division. PLoS One 2024; 19:e0304594. [PMID: 38870161 PMCID: PMC11175401 DOI: 10.1371/journal.pone.0304594] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/13/2023] [Accepted: 05/14/2024] [Indexed: 06/15/2024] Open
Abstract
Quantum annealing machines are next-generation computers for solving combinatorial optimization problems. Although physical simulations are one of the most promising applications of quantum annealing machines, a method how to embed the target problem into the machines has not been developed except for certain simple examples. In this study, we focus on a method of representing real numbers using binary variables, or quantum bits. One of the most important problems for conducting physical simulation by quantum annealing machines is how to represent the real number with quantum bits. The variables in physical simulations are often represented by real numbers but real numbers must be represented by a combination of binary variables in quantum annealing, such as quadratic unconstrained binary optimization (QUBO). Conventionally, real numbers have been represented by assigning each digit of their binary number representation to a binary variable. Considering the classical annealing point of view, we noticed that when real numbers are represented in binary numbers, there are numbers that can only be reached by inverting several bits simultaneously under the restriction of not increasing a given Hamiltonian, which makes the optimization very difficult. In this work, we propose three new types of real number representation and compared these representations under the problem of solving linear equations. As a result, we found experimentally that the accuracy of the solution varies significantly depending on how the real numbers are represented. We also found that the most appropriate representation depends on the size and difficulty of the problem to be solved and that these differences show a consistent trend for two annealing solvers. Finally, we explain the reasons for these differences using simple models, the minimum required number of simultaneous bit flips, one-way probabilistic bit-flip energy minimization, and simulation of ideal quantum annealing machine.
Collapse
Affiliation(s)
- Katsuhiro Endo
- Research Center for Computational Design of Advanced Functional Materials, National Institute of Advanced Industrial Science and Technology (AIST), Tsukuba, Ibaraki Japan
- Quantum Computing Center, Keio University, Yokohama, Kanagawa, Japan
- Graduate School of Science and Technology, Keio University, Yokohama, Kanagawa, Japan
| | - Yoshiki Matsuda
- Fixstars, Tokyo, Japan
- Green Computing System Research Organization, Waseda University, Tokyo, Japan
| | - Shu Tanaka
- Quantum Computing Center, Keio University, Yokohama, Kanagawa, Japan
- Green Computing System Research Organization, Waseda University, Tokyo, Japan
- Department of Applied Physics and Physico-Informatics, Keio University, Yokohama, Kanagawa, Japan
- Human Biology-Microbiome-Quantum Research Center (WPI-Bio2Q), Keio University, Tokyo, Japan
| | - Mayu Muramatsu
- Quantum Computing Center, Keio University, Yokohama, Kanagawa, Japan
- Department of Mechanical Engineering, Keio University, Yokohama, Kanagawa, Japan
| |
Collapse
|
3
|
Chawla P, Singh S, Agarwal A, Srinivasan S, Chandrashekar CM. Multi-qubit quantum computing using discrete-time quantum walks on closed graphs. Sci Rep 2023; 13:12078. [PMID: 37495607 PMCID: PMC10372037 DOI: 10.1038/s41598-023-39061-1] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/19/2023] [Accepted: 07/19/2023] [Indexed: 07/28/2023] Open
Abstract
Universal quantum computation can be realised using both continuous-time and discrete-time quantum walks. We present a version based on single particle discrete-time quantum walk to realize multi-qubit computation tasks. The scalability of the scheme is demonstrated by using a set of walk operations on a closed lattice form to implement the universal set of quantum gates on multi-qubit system. We also present a set of experimentally realizable walk operations that can implement Grover's algorithm, quantum Fourier transformation and quantum phase estimation algorithms. An elementary implementation of error detection and correction is also presented. Analysis of space and time complexity of the scheme highlights the advantages of quantum walk based model for quantum computation on systems where implementation of quantum walk evolution operations is an inherent feature of the system.
Collapse
Affiliation(s)
- Prateek Chawla
- The Institute of Mathematical Sciences, C. I. T. Campus, Taramani, Chennai, 600113, India.
- Homi Bhabha National Institute, Training School Complex, Anushakti Nagar, Mumbai, 400094, India.
| | - Shivani Singh
- The Institute of Mathematical Sciences, C. I. T. Campus, Taramani, Chennai, 600113, India
- FNSPE, Czech Technical University in Prague, Brehova 7, 119 15, Praha 1, Prague, Czech Republic
| | - Aman Agarwal
- The Institute of Mathematical Sciences, C. I. T. Campus, Taramani, Chennai, 600113, India
- BITS-Pilani, K. K. BIrla Goa Campus, NH17B, Bypass Road, Zuarinagar, Goa, 403726, India
| | - Sarvesh Srinivasan
- The Institute of Mathematical Sciences, C. I. T. Campus, Taramani, Chennai, 600113, India
- Birla Institute of Technology and Science, Pilani Campus, Pilani, 333031, India
| | - C M Chandrashekar
- The Institute of Mathematical Sciences, C. I. T. Campus, Taramani, Chennai, 600113, India
- Homi Bhabha National Institute, Training School Complex, Anushakti Nagar, Mumbai, 400094, India
- Quantum Optics and Quantum Information, Department of Instrumentation and Applied Physics, Indian Institute of Science, Bengaluru, India
| |
Collapse
|
4
|
Weinberg SJ, Sanches F, Ide T, Kamiya K, Correll R. Supply chain logistics with quantum and classical annealing algorithms. Sci Rep 2023; 13:4770. [PMID: 36959248 PMCID: PMC10036469 DOI: 10.1038/s41598-023-31765-8] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/29/2022] [Accepted: 03/16/2023] [Indexed: 03/25/2023] Open
Abstract
Noisy intermediate-scale quantum (NISQ) hardware is almost universally incompatible with full-scale optimization problems of practical importance which can have many variables and unwieldy objective functions. As a consequence, there is a growing body of literature that tests quantum algorithms on miniaturized versions of problems that arise in an operations research setting. Rather than taking this approach, we investigate a problem of substantial commercial value, multi-truck vehicle routing for supply chain logistics, at the scale used by a corporation in their operations. Such a problem is too complex to be fully embedded on any near-term quantum hardware or simulator; we avoid confronting this challenge by taking a hybrid workflow approach: we iteratively assign routes for trucks by generating a new binary optimization problem instance one truck at a time. Each instance has [Formula: see text] quadratic binary variables, putting it in a range that is feasible for NISQ quantum computing, especially quantum annealing hardware. We test our methods using simulated annealing and the D-Wave Hybrid solver as a place-holder in wait of quantum hardware developments. After feeding the vehicle routes suggested by these runs into a highly realistic classical supply chain simulation, we find excellent performance for the full supply chain. Our work gives a set of techniques that can be adopted in contexts beyond vehicle routing to apply NISQ devices in a hybrid fashion to large-scale problems of commercial interest.
Collapse
Affiliation(s)
| | | | - Takanori Ide
- Aisin Corporation, Tokyo Research Center, Chiyoda-ku, Tokyo, Japan
| | | | | |
Collapse
|
5
|
Sinha A. Development of research network on Quantum Annealing Computation and Information using Google Scholar data. PHILOSOPHICAL TRANSACTIONS. SERIES A, MATHEMATICAL, PHYSICAL, AND ENGINEERING SCIENCES 2023; 381:20210413. [PMID: 36463919 DOI: 10.1098/rsta.2021.0413] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/05/2022] [Accepted: 09/08/2022] [Indexed: 06/17/2023]
Abstract
We build and analyse the network of 100 top-cited nodes (research papers and books from Google Scholar; the strength or citation of the nodes range from about 44 000 up to 100) starting in early 1980 until last year. These searched publications (papers and books) are based on Quantum Annealing Computation and Information categorized into four different sets: (A) Quantum/Transverse Field Spin Glass Model, (B) Quantum Annealing, (C) Quantum Adiabatic Computation and (D) Quantum Computation Information in the title or abstract of the searched publications. We fitted the growth in the annual number of publication ([Formula: see text]) in each of these four categories, A-D, to the form [Formula: see text] where [Formula: see text] denotes the time in years. We found the scaling time [Formula: see text] to be of the order of about 10 years for categories A and C, whereas [Formula: see text] is of the order of about 5 years for categories B and D. This article is part of the theme issue 'Quantum annealing and computation: challenges and perspectives'.
Collapse
Affiliation(s)
- Antika Sinha
- Department of Computer Science, Asutosh College, Kolkata, West Bengal 700026, India
| |
Collapse
|
6
|
Suzuki S, Oshiyama H, Shibata N. Statistics of the number of defects after quantum annealing in a thermal environment. PHILOSOPHICAL TRANSACTIONS. SERIES A, MATHEMATICAL, PHYSICAL, AND ENGINEERING SCIENCES 2023; 381:20210411. [PMID: 36463929 DOI: 10.1098/rsta.2021.0411] [Citation(s) in RCA: 1] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/25/2022] [Accepted: 09/30/2022] [Indexed: 06/17/2023]
Abstract
We study the statistics of the kink number generated by quantum annealing in a one-dimensional transverse Ising model coupled to a bosonic thermal bath. Using the freezing ansatz for quantum annealing in the thermal environment, we show the relation between the ratio of the second to the first cumulant of the kink number distribution and the average kink density. The theoretical result is confirmed thoroughly by numerical simulation using the non-Markovian infinite time-evolving block decimation which we proposed recently. The simulation using D-Wave's quantum annealer is also discussed. This article is part of the theme issue 'Quantum annealing and computation: challenges and perspectives'.
Collapse
Affiliation(s)
- Sei Suzuki
- Department of Liberal Arts, Saitama Medical University, Moroyama, Saitama, Japan
| | - Hiroki Oshiyama
- Department of Information Sciences, Tohoku University, Sendai, Japan
| | | |
Collapse
|
7
|
Rajak A, Suzuki S, Dutta A, Chakrabarti BK. Quantum annealing: an overview. PHILOSOPHICAL TRANSACTIONS. SERIES A, MATHEMATICAL, PHYSICAL, AND ENGINEERING SCIENCES 2023; 381:20210417. [PMID: 36463923 DOI: 10.1098/rsta.2021.0417] [Citation(s) in RCA: 8] [Impact Index Per Article: 8.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/04/2022] [Accepted: 08/22/2022] [Indexed: 06/17/2023]
Abstract
In this review, after providing the basic physical concept behind quantum annealing (or adiabatic quantum computation), we present an overview of some recent theoretical as well as experimental developments pointing to the issues which are still debated. With a brief discussion on the fundamental ideas of continuous and discontinuous quantum phase transitions, we discuss the Kibble-Zurek scaling of defect generation following a ramping of a quantum many body system across a quantum critical point. In the process, we discuss associated models, both pure and disordered, and shed light on implementations and some recent applications of the quantum annealing protocols. Furthermore, we discuss the effect of environmental coupling on quantum annealing. Some possible ways to speed up the annealing protocol in closed systems are elaborated upon: we especially focus on the recipes to avoid discontinuous quantum phase transitions occurring in some models where energy gaps vanish exponentially with the system size. This article is part of the theme issue 'Quantum annealing and computation: challenges and perspectives'.
Collapse
Affiliation(s)
- Atanu Rajak
- Department of Physics, Presidency University, Kolkata 700073, India
| | - Sei Suzuki
- Department of Liberal Arts, Saitama Medical University, Moroyama, Saitama 350-0495, Japan
| | - Amit Dutta
- Indian Institute of Technology Kanpur, Kanpur 208016, India
| | - Bikas K Chakrabarti
- Saha Institute of Nuclear Physics, 1/AF Bidhannagar, Kolkata 700064, India
- Indian Statistical Institute, 203 B. T. Road, Kolkata 700108, India
| |
Collapse
|
8
|
Chakrabarti BK, Leschke H, Ray P, Shirai T, Tanaka S. Quantum annealing and computation: challenges and perspectives. PHILOSOPHICAL TRANSACTIONS. SERIES A, MATHEMATICAL, PHYSICAL, AND ENGINEERING SCIENCES 2023; 381:20210419. [PMID: 36463926 PMCID: PMC9719792 DOI: 10.1098/rsta.2021.0419] [Citation(s) in RCA: 1] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/11/2022] [Accepted: 10/11/2022] [Indexed: 06/17/2023]
Abstract
In the introductory article of this theme issue, we provide an overview of quantum annealing and computation with a very brief summary of the individual contributions to this issue made by experts as well as a few young researchers. We hope the readers will get the touch of the excitement as well as the perspectives in this unusually active field and important developments there. This article is part of the theme issue 'Quantum annealing and computation: challenges and perspectives'.
Collapse
Affiliation(s)
- Bikas K. Chakrabarti
- Saha Institute of Nuclear Physics, Kolkata 700064, India
- Indian Statistical Institute, Kolkata 700108, India
| | - Hajo Leschke
- Institut für Theoretische Physik, Universität Erlangen-Nürnberg, 91058 Erlangen, Germany
| | - Purusattam Ray
- The Institute of Mathematical Sciences, Taramani, Chennai 600113, India
| | - Tatsuhiko Shirai
- Department of Computer Science and Communications Engineering, Waseda University, Tokyo 169-8555, Japan
| | - Shu Tanaka
- Department of Applied Physics and Physico-Informatics, Keio University, Yokohama 223-8522, Japan
| |
Collapse
|
9
|
Kadowaki T, Nishimori H. Greedy parameter optimization for diabatic quantum annealing. PHILOSOPHICAL TRANSACTIONS. SERIES A, MATHEMATICAL, PHYSICAL, AND ENGINEERING SCIENCES 2023; 381:20210416. [PMID: 36463922 PMCID: PMC9719795 DOI: 10.1098/rsta.2021.0416] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/12/2023]
Abstract
A shorter processing time is desirable for quantum computation to minimize the effects of noise. We propose a simple procedure to variationally determine a set of parameters in the transverse-field Ising model for quantum annealing (QA) appended with a field along the [Formula: see text]-axis. The method consists of greedy optimization of the signs of coefficients of the [Formula: see text]-field term based on the outputs of short annealing processes. We test the idea in the ferromagnetic system with all-to-all couplings and spin-glass problems, and find that the method outperforms the traditional form of QA and simulated annealing in terms of the success probability and the time to solution, in particular, in the case of shorter annealing times, achieving the goal of improved performance while avoiding noise. The non-stoquastic [Formula: see text] term can be eliminated by a rotation in the spin space, resulting in a non-trivial diabatic control of the coefficients in the stoquastic transverse-field Ising model, which may be feasible for experimental realization. This article is part of the theme issue 'Quantum annealing and computation: challenges and perspectives'.
Collapse
Affiliation(s)
| | - Hidetoshi Nishimori
- Institute of Innovative Research, Tokyo Institute of Technology, Yokohama, Kanagawa 226-8503, Japan
- Graduate School of Information Sciences, Tohoku University, Sendai, Miyagi 980-8579, Japan
- RIKEN Interdisciplinary Theoretical and Mathematical Sciences Program (iTHEMS), Wako, Saitama 351-0198, Japan
| |
Collapse
|
10
|
Menke T, Banner WP, Bergamaschi TR, Di Paolo A, Vepsäläinen A, Weber SJ, Winik R, Melville A, Niedzielski BM, Rosenberg D, Serniak K, Schwartz ME, Yoder JL, Aspuru-Guzik A, Gustavsson S, Grover JA, Hirjibehedin CF, Kerman AJ, Oliver WD. Demonstration of Tunable Three-Body Interactions between Superconducting Qubits. PHYSICAL REVIEW LETTERS 2022; 129:220501. [PMID: 36493437 DOI: 10.1103/physrevlett.129.220501] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/17/2022] [Accepted: 10/17/2022] [Indexed: 06/17/2023]
Abstract
Nonpairwise multiqubit interactions present a useful resource for quantum information processors. Their implementation would facilitate more efficient quantum simulations of molecules and combinatorial optimization problems, and they could simplify error suppression and error correction schemes. Here, we present a superconducting circuit architecture in which a coupling module mediates two-local and three-local interactions between three flux qubits by design. The system Hamiltonian is estimated via multiqubit pulse sequences that implement Ramsey-type interferometry between all neighboring excitation manifolds in the system. The three-local interaction is coherently tunable over several MHz via the coupler flux biases and can be turned off, which is important for applications in quantum annealing, analog quantum simulation, and gate-model quantum computation.
Collapse
Affiliation(s)
- Tim Menke
- Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
- Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
- Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA
| | - William P Banner
- Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| | - Thomas R Bergamaschi
- Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| | - Agustin Di Paolo
- Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| | - Antti Vepsäläinen
- Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| | - Steven J Weber
- Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts 02421-6426, USA
| | - Roni Winik
- Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| | - Alexander Melville
- Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts 02421-6426, USA
| | - Bethany M Niedzielski
- Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts 02421-6426, USA
| | - Danna Rosenberg
- Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts 02421-6426, USA
| | - Kyle Serniak
- Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts 02421-6426, USA
| | - Mollie E Schwartz
- Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts 02421-6426, USA
| | - Jonilyn L Yoder
- Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts 02421-6426, USA
| | - Alán Aspuru-Guzik
- Departments of Chemistry and Computer Science, University of Toronto, Toronto, Ontario M5G 1Z8, Canada
- Vector Institute for Artificial Intelligence, Toronto, Ontario M5S 1M1, Canada
- Canadian Institute for Advanced Research, Toronto, Ontario M5G 1Z8, Canada
| | - Simon Gustavsson
- Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| | - Jeffrey A Grover
- Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| | - Cyrus F Hirjibehedin
- Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts 02421-6426, USA
| | - Andrew J Kerman
- Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts 02421-6426, USA
| | - William D Oliver
- Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
- Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
- Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
- Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts 02421-6426, USA
| |
Collapse
|
11
|
Hybrid quantum-classical solution for electric vehicle charger placement problem. Soft comput 2022. [DOI: 10.1007/s00500-022-07478-x] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/26/2022]
|
12
|
Acampora G, Cataudella V, Hegde PR, Lucignano P, Passarelli G, Vitiello A. Memetic algorithms for mapping p-body interacting systems in effective quantum 2-body Hamiltonians. Appl Soft Comput 2021. [DOI: 10.1016/j.asoc.2021.107634] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/21/2022]
|
13
|
Li L, Liu H, Huang N, Wang Z. Accuracy-enhanced coherent Ising machine using the quantum adiabatic theorem. OPTICS EXPRESS 2021; 29:18530-18539. [PMID: 34154108 DOI: 10.1364/oe.426476] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/30/2021] [Accepted: 05/17/2021] [Indexed: 06/13/2023]
Abstract
The coherent Ising machine (CIM) implemented by degenerate optical parametric oscillator (DOPO) networks is a novel optical platform to accelerate computation of hard combinatorial optimization problems. Nevertheless, with the increase of the problem size, the probability of the machine being trapped by local minima increases exponentially. According to the quantum adiabatic theorem, a physical system will remain in its instantaneous ground state if the time-dependent Hamiltonian varies slowly enough. Here, we propose a method to help the machine partially avoid getting stuck in local minima by introducing quantum adiabatic evolution to the ground-state-search process of the CIM, which we call A-CIM. Numerical simulation results demonstrate that A-CIM can obtain improved solution accuracy in solving MAXCUT problems of vertices ranging from 10 to 2000 than CIM. The proposed machine that is based on quantum adiabatic theorem is expected to solve optimization problems more correctly.
Collapse
|
14
|
Calvanese Strinati M, Bello L, Dalla Torre EG, Pe'er A. Can Nonlinear Parametric Oscillators Solve Random Ising Models? PHYSICAL REVIEW LETTERS 2021; 126:143901. [PMID: 33891458 DOI: 10.1103/physrevlett.126.143901] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 11/30/2020] [Accepted: 03/10/2021] [Indexed: 06/12/2023]
Abstract
We study large networks of parametric oscillators as heuristic solvers of random Ising models. In these networks, known as coherent Ising machines, the model to be solved is encoded in the coupling between the oscillators, and a solution is offered by the steady state of the network. This approach relies on the assumption that mode competition steers the network to the ground-state solution of the Ising model. By considering a broad family of frustrated Ising models, we show that the most efficient mode does not correspond generically to the ground state of the Ising model. We infer that networks of parametric oscillators close to threshold are intrinsically not Ising solvers. Nevertheless, the network can find the correct solution if the oscillators are driven sufficiently above threshold, in a regime where nonlinearities play a predominant role. We find that for all probed instances of the model, the network converges to the ground state of the Ising model with a finite probability.
Collapse
Affiliation(s)
- Marcello Calvanese Strinati
- Department of Physics, Bar-Ilan University, 52900 Ramat-Gan, Israel
- Dipartimento di Fisica, Università di Roma "La Sapienza," Piazzale Aldo Moro 5, I-00185 Rome, Italy
| | - Leon Bello
- Department of Physics and QUEST Center of Quantum Science and Technology, Bar-Ilan University, 52900 Ramat-Gan, Israel
| | | | - Avi Pe'er
- Department of Physics and QUEST Center of Quantum Science and Technology, Bar-Ilan University, 52900 Ramat-Gan, Israel
| |
Collapse
|
15
|
Abstract
We have developed a framework for using quantum annealing computation to evaluate a key quantity in ionic diffusion in solids, the correlation factor. Existing methods can only calculate the correlation factor analytically in the case of physically unrealistic models, making it difficult to relate microstructural information about diffusion path networks obtainable by current ab initio techniques to macroscopic quantities such as diffusion coefficients. We have mapped the problem into a quantum spin system described by the Ising Hamiltonian. By applying our framework in combination with ab initio technique, it is possible to understand how diffusion coefficients are controlled by temperatures, pressures, atomic substitutions, and other factors. We have calculated the correlation factor in a simple case with a known exact result by a variety of computational methods, including simulated quantum annealing on the spin models, the classical random walk, the matrix description, and quantum annealing on D-Wave with hybrid solver . This comparison shows that all the evaluations give consistent results with each other, but that many of the conventional approaches require infeasible computational costs. Quantum annealing is also currently infeasible because of the cost and scarcity of qubits, but we argue that when technological advances alter this situation, quantum annealing will easily outperform all existing methods.
Collapse
|
16
|
Chakrabarti BK, Sinha A. Development of Econophysics: A Biased Account and Perspective from Kolkata. ENTROPY (BASEL, SWITZERLAND) 2021; 23:254. [PMID: 33672245 PMCID: PMC7926551 DOI: 10.3390/e23020254] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 01/28/2021] [Revised: 02/14/2021] [Accepted: 02/19/2021] [Indexed: 11/21/2022]
Abstract
We present here a somewhat personalized account of the emergence of econophysics as an attractive research topic in physical, as well as social, sciences. After a rather detailed storytelling about our endeavors from Kolkata, we give a brief description of the main research achievements in a simple and non-technical language. We also briefly present, in technical language, a piece of our recent research result. We conclude our paper with a brief perspective.
Collapse
Affiliation(s)
- Bikas K. Chakrabarti
- Saha Institute of Nuclear Physics, Kolkata 700064, India;
- S. N. Bose National Center for Basic Sciences, Kolkata 700106, India
- Economic Research Unit, Indian Statistical Institute, Kolkata 700108, India
| | - Antika Sinha
- Saha Institute of Nuclear Physics, Kolkata 700064, India;
- Department of Computer Science, Asutosh College, Kolkata 700026, India
| |
Collapse
|
17
|
Koshka Y, Novotny MA. Comparison of Use of a 2000 Qubit D-Wave Quantum Annealer and MCMC for Sampling, Image Reconstruction, and Classification. IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE 2021. [DOI: 10.1109/tetci.2018.2871466] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/09/2022]
|
18
|
Statistical Physics for Medical Diagnostics: Learning, Inference, and Optimization Algorithms. Diagnostics (Basel) 2020; 10:diagnostics10110972. [PMID: 33228143 PMCID: PMC7699346 DOI: 10.3390/diagnostics10110972] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/06/2020] [Revised: 11/16/2020] [Accepted: 11/17/2020] [Indexed: 02/03/2023] Open
Abstract
It is widely believed that cooperation between clinicians and machines may address many of the decisional fragilities intrinsic to current medical practice. However, the realization of this potential will require more precise definitions of disease states as well as their dynamics and interactions. A careful probabilistic examination of symptoms and signs, including the molecular profiles of the relevant biochemical networks, will often be required for building an unbiased and efficient diagnostic approach. Analogous problems have been studied for years by physicists extracting macroscopic states of various physical systems by examining microscopic elements and their interactions. These valuable experiences are now being extended to the medical field. From this perspective, we discuss how recent developments in statistical physics, machine learning and inference algorithms are coming together to improve current medical diagnostic approaches.
Collapse
|
19
|
Ostilli M. Absence of small-world effects at the quantum level and stability of the quantum critical point. Phys Rev E 2020; 102:052126. [PMID: 33327165 DOI: 10.1103/physreve.102.052126] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/25/2019] [Accepted: 10/31/2020] [Indexed: 06/12/2023]
Abstract
The small-world effect is a universal feature used to explain many different phenomena like percolation, diffusion, and consensus. Starting from any regular lattice of N sites, the small-world effect can be attained by rewiring randomly an O(N) number of links or by superimposing an equivalent number of new links onto the system. In a classical system this procedure is known to change radically its critical point and behavior, the new system being always effectively mean-field. Here, we prove that at the quantum level the above scenario does not apply: when an O(N) number of new couplings are randomly superimposed onto a quantum Ising chain, its quantum critical point and behavior both remain unchanged. In other words, at zero temperature quantum fluctuations destroy any small-world effect. This exact result sheds new light on the significance of the quantum critical point as a thermodynamically stable feature of nature that has no analogy at the classical level and essentially prevents a naive application of network theory to quantum systems. The derivation is obtained by combining the quantum-classical mapping with a simple topological argument.
Collapse
Affiliation(s)
- Massimo Ostilli
- Instituto de Física, Universidade Federal da Bahia, Salvador 40170-115, Brazil
| |
Collapse
|
20
|
Hauke P, Katzgraber HG, Lechner W, Nishimori H, Oliver WD. Perspectives of quantum annealing: methods and implementations. REPORTS ON PROGRESS IN PHYSICS. PHYSICAL SOCIETY (GREAT BRITAIN) 2020; 83:054401. [PMID: 32235066 DOI: 10.1088/1361-6633/ab85b8] [Citation(s) in RCA: 48] [Impact Index Per Article: 12.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/02/2023]
Abstract
Quantum annealing is a computing paradigm that has the ambitious goal of efficiently solving large-scale combinatorial optimization problems of practical importance. However, many challenges have yet to be overcome before this goal can be reached. This perspectives article first gives a brief introduction to the concept of quantum annealing, and then highlights new pathways that may clear the way towards feasible and large scale quantum annealing. Moreover, since this field of research is to a strong degree driven by a synergy between experiment and theory, we discuss both in this work. An important focus in this article is on future perspectives, which complements other review articles, and which we hope will motivate further research.
Collapse
Affiliation(s)
- Philipp Hauke
- INO-CNR BEC Center and Department of Physics, University of Trento, 38123Povo (TN), Italy. Kirchhoff-Institute for Physics, Heidelberg University, 69120 Heidelberg, Germany. Institute for Theoretical Physics, Heidelberg University, 69120 Heidelberg, Germany
| | | | | | | | | |
Collapse
|
21
|
Quantum computing based hybrid solution strategies for large-scale discrete-continuous optimization problems. Comput Chem Eng 2020. [DOI: 10.1016/j.compchemeng.2019.106630] [Citation(s) in RCA: 59] [Impact Index Per Article: 14.8] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/08/2023]
|
22
|
Cruz-Santos W, Venegas-Andraca SE, Lanzagorta M. A QUBO Formulation of Minimum Multicut Problem Instances in Trees for D-Wave Quantum Annealers. Sci Rep 2019; 9:17216. [PMID: 31748576 PMCID: PMC6868218 DOI: 10.1038/s41598-019-53585-5] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/30/2019] [Accepted: 10/31/2019] [Indexed: 11/10/2022] Open
Abstract
Quantum annealing algorithms were introduced to solve combinatorial optimization problems by taking advantage of quantum fluctuations to escape local minima in complex energy landscapes typical of NP − hard problems. In this work, we propose using quantum annealing for the theory of cuts, a field of paramount importance in theoretical computer science. We have proposed a method to formulate the Minimum Multicut Problem into the QUBO representation, and the technical difficulties faced when embedding and submitting a problem to the quantum annealer processor. We show two constructions of the quadratic unconstrained binary optimization functions for the Minimum Multicut Problem and we review several tradeoffs between the two mappings and provide numerical scaling analysis results from several classical approaches. Furthermore, we discuss some of the expected challenges and tradeoffs in the implementation of our mapping in the current generation of D-Wave machines.
Collapse
Affiliation(s)
- William Cruz-Santos
- CU-UAEM Valle de Chalco, Hermenegildo Galeana 3, Valle de Chalco, Estado de México, 56615, Mexico
| | - Salvador E Venegas-Andraca
- Tecnologico de Monterrey, Escuela de Ingenieria y Ciencias, Ave. Eugenio Garza Sada 2501, Monterrey, NL, 64849, Mexico.
| | - Marco Lanzagorta
- US Naval Research Laboratory, 4555 Overlook Ave. SW, Washington, DC, 20375, USA
| |
Collapse
|
23
|
Zhu Z, Ochoa AJ, Katzgraber HG. Fair sampling of ground-state configurations of binary optimization problems. Phys Rev E 2019; 99:063314. [PMID: 31330750 DOI: 10.1103/physreve.99.063314] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/18/2019] [Indexed: 11/07/2022]
Abstract
Although many efficient heuristics have been developed to solve binary optimization problems, these typically produce correlated solutions for degenerate problems. Most notably, transverse-field quantum annealing-the heuristic employed in current commercially available quantum annealing machines-has been shown to often be exponentially biased when sampling the solution space. Here we present an approach to sample ground-state (or low-energy) configurations for binary optimization problems. The method samples degenerate states with almost equal probability and is based on a combination of parallel tempering Monte Carlo with isoenergetic cluster moves. We illustrate the approach using two-dimensional Ising spin glasses, as well as spin glasses on the D-Wave Systems quantum annealer chimera topology. In addition, a simple heuristic to approximate the number of solutions of a degenerate problem is introduced.
Collapse
Affiliation(s)
- Zheng Zhu
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Andrew J Ochoa
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Helmut G Katzgraber
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA.,Microsoft Quantum, Microsoft, Redmond, Washington 98052, USA.,Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
| |
Collapse
|
24
|
Ochoa AJ, Jacob DC, Mandrà S, Katzgraber HG. Feeding the multitude: A polynomial-time algorithm to improve sampling. Phys Rev E 2019; 99:043306. [PMID: 31108684 DOI: 10.1103/physreve.99.043306] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/25/2018] [Indexed: 11/07/2022]
Abstract
A wide variety of optimization techniques, both exact and heuristic, tend to be biased samplers. This means that when attempting to find multiple uncorrelated solutions of a degenerate Boolean optimization problem a subset of the solution space tends to be favored while, in the worst case, some solutions can never be accessed by the algorithm used. Here we present a simple postprocessing technique that improves sampling for any optimization approach, either quantum or classical. More precisely, starting from a pool of a few optimal configurations, the algorithm generates potentially new solutions via rejection-free cluster updates at zero temperature. Although the method is not ergodic and there is no guarantee that all the solutions can be found, fair sampling is typically improved. We illustrate the effectiveness of our method by improving the exponentially biased data produced by the D-Wave 2X quantum annealer [S. Mandrà et al., Phys. Rev. Lett. 118, 070502 (2017)PRLTAO0031-900710.1103/PhysRevLett.118.070502], as well as data from three-dimensional Ising spin glasses. As part of the study, we also show that sampling is improved when suboptimal states are included and discuss sampling at a finite fixed temperature.
Collapse
Affiliation(s)
- Andrew J Ochoa
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Darryl C Jacob
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Salvatore Mandrà
- Quantum Artificial Intelligence Laboratory, NASA Ames Research Center, Moffett Field, California 94035, USA.,Stinger Ghaffarian Technologies, Inc., 7701 Greenbelt Road, Greenbelt, Maryland 20770, USA
| | - Helmut G Katzgraber
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA.,Microsoft Quantum, Microsoft, Redmond, Washington 98052, USA.,Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
| |
Collapse
|
25
|
Hamerly R, Inagaki T, McMahon PL, Venturelli D, Marandi A, Onodera T, Ng E, Langrock C, Inaba K, Honjo T, Enbutsu K, Umeki T, Kasahara R, Utsunomiya S, Kako S, Kawarabayashi KI, Byer RL, Fejer MM, Mabuchi H, Englund D, Rieffel E, Takesue H, Yamamoto Y. Experimental investigation of performance differences between coherent Ising machines and a quantum annealer. SCIENCE ADVANCES 2019; 5:eaau0823. [PMID: 31139743 PMCID: PMC6534389 DOI: 10.1126/sciadv.aau0823] [Citation(s) in RCA: 42] [Impact Index Per Article: 8.4] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 05/04/2018] [Accepted: 04/17/2019] [Indexed: 05/05/2023]
Abstract
Physical annealing systems provide heuristic approaches to solving combinatorial optimization problems. Here, we benchmark two types of annealing machines-a quantum annealer built by D-Wave Systems and measurement-feedback coherent Ising machines (CIMs) based on optical parametric oscillators-on two problem classes, the Sherrington-Kirkpatrick (SK) model and MAX-CUT. The D-Wave quantum annealer outperforms the CIMs on MAX-CUT on cubic graphs. On denser problems, however, we observe an exponential penalty for the quantum annealer [exp(-αDW N 2)] relative to CIMs [exp(-αCIM N)] for fixed anneal times, both on the SK model and on 50% edge density MAX-CUT. This leads to a several orders of magnitude time-to-solution difference for instances with over 50 vertices. An optimal-annealing time analysis is also consistent with a substantial projected performance difference. The difference in performance between the sparsely connected D-Wave machine and the fully-connected CIMs provides strong experimental support for efforts to increase the connectivity of quantum annealers.
Collapse
Affiliation(s)
- Ryan Hamerly
- Research Laboratory of Electronics, Massachusetts Institute of Technology, 50 Vassar Street, Cambridge, MA 02139, USA
- National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan
- Corresponding author. (R.H.); (T.I.); (P.L.M.)
| | - Takahiro Inagaki
- NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
- Corresponding author. (R.H.); (T.I.); (P.L.M.)
| | - Peter L. McMahon
- National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
- School of Applied and Engineering Physics, Cornell University, Ithaca, NY 14853, USA
- Corresponding author. (R.H.); (T.I.); (P.L.M.)
| | - Davide Venturelli
- NASA Ames Research Center Quantum Artificial Intelligence Laboratory (QuAIL), Mail Stop 269-1, Moffett Field, CA 94035, USA
- USRA Research Institute for Advanced Computer Science (RIACS), 615 National Avenue, Mountain View, CA 94035, USA
| | - Alireza Marandi
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
- California Institute of Technology, Pasadena, CA 91125, USA
| | - Tatsuhiro Onodera
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
| | - Edwin Ng
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
| | - Carsten Langrock
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
| | - Kensuke Inaba
- NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
| | - Toshimori Honjo
- NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
| | - Koji Enbutsu
- NTT Device Technology Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
| | - Takeshi Umeki
- NTT Device Technology Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
| | - Ryoichi Kasahara
- NTT Device Technology Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
| | - Shoko Utsunomiya
- National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan
| | - Satoshi Kako
- National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan
| | - Ken-ichi Kawarabayashi
- National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan
| | - Robert L. Byer
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
| | - Martin M. Fejer
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
| | - Hideo Mabuchi
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
| | - Dirk Englund
- Research Laboratory of Electronics, Massachusetts Institute of Technology, 50 Vassar Street, Cambridge, MA 02139, USA
| | - Eleanor Rieffel
- NASA Ames Research Center Quantum Artificial Intelligence Laboratory (QuAIL), Mail Stop 269-1, Moffett Field, CA 94035, USA
| | - Hiroki Takesue
- NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
| | - Yoshihisa Yamamoto
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
- ImPACT Program, Japan Science and Technology Agency, Gobancho 7, Chiyoda-ku, Tokyo 102-0076, Japan
| |
Collapse
|
26
|
Mostafavi F, Yuan L, Ramezani H. Eigenstates Transition without Undergoing an Adiabatic Process. PHYSICAL REVIEW LETTERS 2019; 122:050404. [PMID: 30821988 DOI: 10.1103/physrevlett.122.050404] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/02/2018] [Indexed: 06/09/2023]
Abstract
We introduce a class of non-Hermitian Hamiltonians that offers a dynamical approach to a shortcut to adiabaticity (DASA). In particular, in our proposed 2×2 Hamiltonians, one eigenvalue is absolutely real and the other one is complex. This specific form of eigenvalues helps us to exponentially decay the population in an undesired eigenfunction or amplify the population in the desired state while keeping the probability amplitude in the other eigenfunction conserved. This provides us with a powerful method to have a diabatic process with the same outcome as its corresponding adiabatic process. In contrast to standard shortcuts to adiabaticity, our Hamiltonians have a much simpler form with a lower thermodynamic cost. Furthermore, we show that DASA can be extended to higher dimensions using the parameters associated with our 2×2 Hamiltonians. Our proposed Hamiltonians not only have application in DASA but also can be used for tunable mode selection and filtering in acoustics, electronics, and optics.
Collapse
Affiliation(s)
- Fatemeh Mostafavi
- Department of Physics and Astronomy, University of Texas Rio Grande Valley, Brownsville, Texas 78520, USA
| | - Luqi Yuan
- School of Physics and Astronomy, Shanghai Jiao Tong University, Shanghai 200240, China
| | - Hamidreza Ramezani
- Department of Physics and Astronomy, University of Texas Rio Grande Valley, Brownsville, Texas 78520, USA
| |
Collapse
|
27
|
Cruz-Santos W, Venegas-Andraca SE, Lanzagorta M. A QUBO Formulation of the Stereo Matching Problem for D-Wave Quantum Annealers. ENTROPY 2018; 20:e20100786. [PMID: 33265874 PMCID: PMC7512348 DOI: 10.3390/e20100786] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.8] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 08/06/2018] [Revised: 10/08/2018] [Accepted: 10/08/2018] [Indexed: 11/16/2022]
Abstract
In this paper, we propose a methodology to solve the stereo matching problem through quantum annealing optimization. Our proposal takes advantage of the existing Min-Cut/Max-Flow network formulation of computer vision problems. Based on this network formulation, we construct a quadratic pseudo-Boolean function and then optimize it through the use of the D-Wave quantum annealing technology. Experimental validation using two kinds of stereo pair of images, random dot stereograms and gray-scale, shows that our methodology is effective.
Collapse
Affiliation(s)
- William Cruz-Santos
- CU-UAEM Valle de Chalco, Hermenegildo Galeana 3, Valle de Chalco 56615, Estado de México, Mexico
| | - Salvador E. Venegas-Andraca
- Tecnologico de Monterrey, Escuela de Ingenieria y Ciencias. Ave., Eugenio Garza Sada 2501, Monterrey 64849, NL, Mexico
- Correspondence: or ; Tel.: +52-55-5864-5555
| | - Marco Lanzagorta
- US Naval Research Laboratory, 4555 Overlook Ave., SW Washington, DC 20375, USA
| |
Collapse
|
28
|
Bottarelli L, Bicego M, Denitto M, Di Pierro A, Farinelli A, Mengoni R. Biclustering with a quantum annealer. Soft comput 2018. [DOI: 10.1007/s00500-018-3034-z] [Citation(s) in RCA: 8] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/25/2022]
|
29
|
Lebedev ME, Dolinina DA, Hong KB, Lu TC, Kavokin AV, Alodjants AP. Exciton-polariton Josephson junctions at finite temperatures. Sci Rep 2017; 7:9515. [PMID: 28842628 PMCID: PMC5572052 DOI: 10.1038/s41598-017-09824-8] [Citation(s) in RCA: 7] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/20/2017] [Accepted: 07/31/2017] [Indexed: 11/09/2022] Open
Abstract
We consider finite temperature effects in a non-standard Bose-Hubbard model for an exciton- polariton Josephson junction (JJ) that is characterised by complicated potential energy landscapes (PEL) consisting of sets of barriers and wells. We show that the transition between thermal activation (classical) and tunneling (quantum) regimes exhibits universal features of the first and second order phase transition (PT) depending on the PEL for two polariton condensates that might be described as transition from the thermal to the quantum annealing regime. In the presence of dissipation the relative phase of two condensates exhibits non-equilibrium PT from the quantum regime characterized by efficient tunneling of polaritons to the regime of permanent Josephson or Rabi oscillations, where the tunneling is suppressed, respectively. This analysis paves the way for the application of coupled polariton condensates for the realisation of a quantum annealing algorithm in presently experimentally accessible semiconductor microcavities possessing high (105 and more) Q-factors.
Collapse
Affiliation(s)
- M E Lebedev
- ITMO University, St. Petersburg, 197101, Russia
| | | | - Kuo-Bin Hong
- Department of Photonics, National Chiao Tung University, Hsinchu, 300, Taiwan
| | - Tien-Chang Lu
- Department of Photonics, National Chiao Tung University, Hsinchu, 300, Taiwan
| | - A V Kavokin
- Spin Optics Laboratory, St. Petersburg State University, Ul'anovskaya, Peterhof, St. Petersburg, 198504, Russia
- School of Physics and Astronomy, University of Southampton, SO17 1BJ, Southampton, United Kingdom
- Istituto CNR-SPIN, Viale del Politecnico 1, I-00133, Rome, Italy
| | - A P Alodjants
- ITMO University, St. Petersburg, 197101, Russia.
- Vladimir State University named after A. G. and N. G. Stoletovs, Gorkii Street 87, Vladimir, Russia.
| |
Collapse
|
30
|
Koshka Y, Perera D, Hall S, Novotny MA. Determination of the Lowest-Energy States for the Model Distribution of Trained Restricted Boltzmann Machines Using a 1000 Qubit D-Wave 2X Quantum Computer. Neural Comput 2017; 29:1815-1837. [PMID: 28562219 DOI: 10.1162/neco_a_00974] [Citation(s) in RCA: 9] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/04/2022]
Abstract
The possibility of using a quantum computer D-Wave 2X with more than 1000 qubits to determine the global minimum of the energy landscape of trained restricted Boltzmann machines is investigated. In order to overcome the problem of limited interconnectivity in the D-Wave architecture, the proposed RBM embedding combines multiple qubits to represent a particular RBM unit. The results for the lowest-energy (the ground state) and some of the higher-energy states found by the D-Wave 2X were compared with those of the classical simulated annealing (SA) algorithm. In many cases, the D-Wave machine successfully found the same RBM lowest-energy state as that found by SA. In some examples, the D-Wave machine returned a state corresponding to one of the higher-energy local minima found by SA. The inherently nonperfect embedding of the RBM into the Chimera lattice explored in this work (i.e., multiple qubits combined into a single RBM unit were found not to be guaranteed to be all aligned) and the existence of small, persistent biases in the D-Wave hardware may cause a discrepancy between the D-Wave and the SA results. In some of the investigated cases, introduction of a small bias field into the energy function or optimization of the chain-strength parameter in the D-Wave embedding successfully addressed difficulties of the particular RBM embedding. With further development of the D-Wave hardware, the approach will be suitable for much larger numbers of RBM units.
Collapse
Affiliation(s)
- Yaroslav Koshka
- Department of Electrical and Computer Engineering, Emerging Materials Research Laboratory, HPC[Formula: see text] Distributed Analytics and Security Institute, Mississippi State University, Mississippi State, MS 39762, U.S.A.
| | - Dilina Perera
- HPC[Formula: see text] Distributed Analytics and Security Institute, Mississippi State University, Mississippi State, MS 39762, U.S.A.
| | - Spencer Hall
- HPC[Formula: see text] Distributed Analytics and Security Institute, Mississippi State University, Mississippi State, MS 39762, U.S.A.
| | - M A Novotny
- Department of Physics and Astronomy, HPC[Formula: see text] Center for Computational Sciences, Mississippi State University, Mississippi State, MS 39762, U.S.A., and Faculty of Mathematica and Physics, Charles University Ke Karlovu 5 121 16 Prague, Czech Republic
| |
Collapse
|
31
|
Mandrà S, Zhu Z, Katzgraber HG. Exponentially Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians. PHYSICAL REVIEW LETTERS 2017; 118:070502. [PMID: 28256849 DOI: 10.1103/physrevlett.118.070502] [Citation(s) in RCA: 8] [Impact Index Per Article: 1.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/30/2016] [Indexed: 05/28/2023]
Abstract
We study the performance of the D-Wave 2X quantum annealing machine on systems with well-controlled ground-state degeneracy. While obtaining the ground state of a spin-glass benchmark instance represents a difficult task, the gold standard for any optimization algorithm or machine is to sample all solutions that minimize the Hamiltonian with more or less equal probability. Our results show that while naive transverse-field quantum annealing on the D-Wave 2X device can find the ground-state energy of the problems, it is not well suited in identifying all degenerate ground-state configurations associated with a particular instance. Even worse, some states are exponentially suppressed, in agreement with previous studies on toy model problems [New J. Phys. 11, 073021 (2009)NJOPFM1367-263010.1088/1367-2630/11/7/073021]. These results suggest that more complex driving Hamiltonians are needed in future quantum annealing machines to ensure a fair sampling of the ground-state manifold.
Collapse
Affiliation(s)
- Salvatore Mandrà
- Department of Chemistry and Chemical Biology, Harvard University, 12 Oxford Street, Cambridge, Massachusetts 02138, USA
- NASA Ames Research Center Quantum Artificial Intelligence Laboratory (QuAIL), Mail Stop 269-1, Moffett Field, California 94035, USA
- Stinger Ghaffarian Technologies Inc., 7701 Greenbelt Road, Suite 400, Greenbelt, Maryland 20770, USA
| | - Zheng Zhu
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Helmut G Katzgraber
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
- Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
| |
Collapse
|
32
|
Nishimori H, Takada K. Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stoquastic Hamiltonians. ACTA ACUST UNITED AC 2017. [DOI: 10.3389/fict.2017.00002] [Citation(s) in RCA: 62] [Impact Index Per Article: 8.9] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/13/2022]
|
33
|
Quantum Monte Carlo simulation of a particular class of non-stoquastic Hamiltonians in quantum annealing. Sci Rep 2017; 7:41186. [PMID: 28112244 PMCID: PMC5253731 DOI: 10.1038/srep41186] [Citation(s) in RCA: 17] [Impact Index Per Article: 2.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/12/2016] [Accepted: 12/12/2016] [Indexed: 12/02/2022] Open
Abstract
Quantum annealing is a generic solver of the optimization problem that uses fictitious quantum fluctuation. Its simulation in classical computing is often performed using the quantum Monte Carlo simulation via the Suzuki–Trotter decomposition. However, the negative sign problem sometimes emerges in the simulation of quantum annealing with an elaborate driver Hamiltonian, since it belongs to a class of non-stoquastic Hamiltonians. In the present study, we propose an alternative way to avoid the negative sign problem involved in a particular class of the non-stoquastic Hamiltonians. To check the validity of the method, we demonstrate our method by applying it to a simple problem that includes the anti-ferromagnetic XX interaction, which is a typical instance of the non-stoquastic Hamiltonians.
Collapse
|
34
|
Allawala A, Marston JB. Statistics of the stochastically forced Lorenz attractor by the Fokker-Planck equation and cumulant expansions. Phys Rev E 2016; 94:052218. [PMID: 27967014 DOI: 10.1103/physreve.94.052218] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/07/2016] [Indexed: 06/06/2023]
Abstract
We investigate the Fokker-Planck description of the equal-time statistics of the three-dimensional Lorenz attractor with additive white noise. The invariant measure is found by computing the zero (or null) mode of the linear Fokker-Planck operator as a problem of sparse linear algebra. Two variants are studied: a self-adjoint construction of the linear operator and the replacement of diffusion with hyperdiffusion. We also access the low-order statistics of the system by a perturbative expansion in equal-time cumulants. A comparison is made to statistics obtained by the standard approach of accumulation via direct numerical simulation. Theoretical and computational aspects of the Fokker-Planck and cumulant expansion methods are discussed.
Collapse
Affiliation(s)
- Altan Allawala
- Department of Physics, Box 1843, Brown University, Providence, Rhode Island 02912-1893, USA
| | - J B Marston
- Department of Physics, Box 1843, Brown University, Providence, Rhode Island 02912-1893, USA
| |
Collapse
|
35
|
Nishimura K, Nishimori H, Ochoa AJ, Katzgraber HG. Retrieving the ground state of spin glasses using thermal noise: Performance of quantum annealing at finite temperatures. Phys Rev E 2016; 94:032105. [PMID: 27739776 DOI: 10.1103/physreve.94.032105] [Citation(s) in RCA: 13] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/20/2016] [Indexed: 11/07/2022]
Abstract
We study the problem to infer the ground state of a spin-glass Hamiltonian using data from another Hamiltonian with interactions disturbed by noise from the original Hamiltonian, motivated by the ground-state inference in quantum annealing on a noisy device. It is shown that the average Hamming distance between the inferred spin configuration and the true ground state is minimized when the temperature of the noisy system is kept at a finite value, and not at zero temperature. We present a spin-glass generalization of a well-established result that the ground state of a purely ferromagnetic Hamiltonian is best inferred at a finite temperature in the sense of smallest Hamming distance when the original ferromagnetic interactions are disturbed by noise. We use the numerical transfer-matrix method to establish the existence of an optimal finite temperature in one- and two-dimensional systems. Our numerical results are supported by mean-field calculations, which give an explicit expression of the optimal temperature to infer the spin-glass ground state as a function of variances of the distributions of the original interactions and the noise. The mean-field prediction is in qualitative agreement with numerical data. Implications on postprocessing of quantum annealing on a noisy device are discussed.
Collapse
Affiliation(s)
- Kohji Nishimura
- Department of Physics, Tokyo Institute of Technology, Oh-okayama, Meguro-ku, Tokyo 152-8551, Japan
| | - Hidetoshi Nishimori
- Department of Physics, Tokyo Institute of Technology, Oh-okayama, Meguro-ku, Tokyo 152-8551, Japan
| | - Andrew J Ochoa
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Helmut G Katzgraber
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA.,Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
| |
Collapse
|
36
|
Wild DS, Gopalakrishnan S, Knap M, Yao NY, Lukin MD. Adiabatic Quantum Search in Open Systems. PHYSICAL REVIEW LETTERS 2016; 117:150501. [PMID: 27768379 DOI: 10.1103/physrevlett.117.150501] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/11/2016] [Indexed: 06/06/2023]
Abstract
Adiabatic quantum algorithms represent a promising approach to universal quantum computation. In isolated systems, a key limitation to such algorithms is the presence of avoided level crossings, where gaps become extremely small. In open quantum systems, the fundamental robustness of adiabatic algorithms remains unresolved. Here, we study the dynamics near an avoided level crossing associated with the adiabatic quantum search algorithm, when the system is coupled to a generic environment. At zero temperature, we find that the algorithm remains scalable provided the noise spectral density of the environment decays sufficiently fast at low frequencies. By contrast, higher order scattering processes render the algorithm inefficient at any finite temperature regardless of the spectral density, implying that no quantum speedup can be achieved. Extensions and implications for other adiabatic quantum algorithms will be discussed.
Collapse
Affiliation(s)
- Dominik S Wild
- Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA
| | - Sarang Gopalakrishnan
- Department of Physics and Walter Burke Institute, California Institute of Technology, Pasadena, California 91125, USA
- Department of Engineering Science and Physics, CUNY College of Staten Island, Staten Island, New York 10134, USA
| | - Michael Knap
- Department of Physics, Walter Schottky Institute, and Institute for Advanced Study, Technical University of Munich, 85748 Garching, Germany
| | - Norman Y Yao
- Department of Physics, University of California, Berkeley, California 94720, USA
| | - Mikhail D Lukin
- Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA
| |
Collapse
|
37
|
Steiger DS, Rønnow TF, Troyer M. Heavy Tails in the Distribution of Time to Solution for Classical and Quantum Annealing. PHYSICAL REVIEW LETTERS 2015; 115:230501. [PMID: 26684103 DOI: 10.1103/physrevlett.115.230501] [Citation(s) in RCA: 9] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 05/21/2015] [Indexed: 06/05/2023]
Abstract
For many optimization algorithms the time to solution depends not only on the problem size but also on the specific problem instance and may vary by many orders of magnitude. It is then necessary to investigate the full distribution and especially its tail. Here, we analyze the distributions of annealing times for simulated annealing and simulated quantum annealing (by path integral quantum Monte Carlo simulation) for random Ising spin glass instances. We find power-law distributions with very heavy tails, corresponding to extremely hard instances, but far broader distributions-and thus worse performance for hard instances-for simulated quantum annealing than for simulated annealing. Fast, nonadiabatic, annealing schedules can improve the performance of simulated quantum annealing for very hard instances by many orders of magnitude.
Collapse
Affiliation(s)
| | - Troels F Rønnow
- Theoretische Physik, ETH Zurich, 8093 Zurich, Switzerland
- Nokia Technologies, Broers Building, 21 JJ Thomson Avenue, CB3 0FA Cambridge, United Kingdom
| | | |
Collapse
|
38
|
Okuyama M, Yamanaka Y, Nishimori H, Rams MM. Anomalous behavior of the energy gap in the one-dimensional quantum XY model. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 92:052116. [PMID: 26651656 DOI: 10.1103/physreve.92.052116] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/04/2015] [Indexed: 06/05/2023]
Abstract
We reexamine the well-studied one-dimensional spin-1/2 XY model to reveal its nontrivial energy spectrum, in particular the energy gap between the ground state and the first excited state. In the case of the isotropic XY model, the XX model, the gap behaves very irregularly as a function of the system size at a second order transition point. This is in stark contrast to the usual power-law decay of the gap and is reminiscent of the similar behavior at the first order phase transition in the infinite-range quantum XY model. The gap also shows nontrivial oscillatory behavior for the phase transitions in the anisotropic model in the incommensurate phase. We observe a close relation between this anomalous behavior of the gap and the correlation functions. These results, those for the isotropic case in particular, are important from the viewpoint of quantum annealing where the efficiency of computation is strongly affected by the size dependence of the energy gap.
Collapse
Affiliation(s)
- Manaka Okuyama
- Department of Physics, Tokyo Institute of Technology, Oh-okayama, Meguro-ku, Tokyo 152-8551, Japan
| | - Yuuki Yamanaka
- Department of Physics, Tokyo Institute of Technology, Oh-okayama, Meguro-ku, Tokyo 152-8551, Japan
| | - Hidetoshi Nishimori
- Department of Physics, Tokyo Institute of Technology, Oh-okayama, Meguro-ku, Tokyo 152-8551, Japan
| | - Marek M Rams
- Institute of Physics, Jagiellonian University, Łojasiewicza 11, 30-348 Kraków, Poland
| |
Collapse
|
39
|
Nava M, Quhe R, Palazzesi F, Tiwary P, Parrinello M. de Broglie Swapping Metadynamics for Quantum and Classical Sampling. J Chem Theory Comput 2015; 11:5114-9. [DOI: 10.1021/acs.jctc.5b00818] [Citation(s) in RCA: 8] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/29/2022]
Affiliation(s)
- Marco Nava
- Department
of Chemistry and Applied Biosciences, ETH Zurich, and Facoltà
di Informatica, Istituto di Scienze Computazionali, Università della Svizzera Italiana, Via G. Buffi 13, 6900 Lugano, Ticino, Switzerland
| | - Ruge Quhe
- Department
of Chemistry and Applied Biosciences, ETH Zurich, and Facoltà
di Informatica, Istituto di Scienze Computazionali, Università della Svizzera Italiana, Via G. Buffi 13, 6900 Lugano, Ticino, Switzerland
- State Key Laboratory of Information Photonics and Optical Communications & School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
| | - Ferruccio Palazzesi
- Department
of Chemistry and Applied Biosciences, ETH Zurich, and Facoltà
di Informatica, Istituto di Scienze Computazionali, Università della Svizzera Italiana, Via G. Buffi 13, 6900 Lugano, Ticino, Switzerland
| | - Pratyush Tiwary
- Department
of Chemistry and Applied Biosciences, ETH Zurich, and Facoltà
di Informatica, Istituto di Scienze Computazionali, Università della Svizzera Italiana, Via G. Buffi 13, 6900 Lugano, Ticino, Switzerland
- Department
of Chemistry, Columbia University, 3000 Broadway, New York, New York 10027, United States
| | - Michele Parrinello
- Department
of Chemistry and Applied Biosciences, ETH Zurich, and Facoltà
di Informatica, Istituto di Scienze Computazionali, Università della Svizzera Italiana, Via G. Buffi 13, 6900 Lugano, Ticino, Switzerland
| |
Collapse
|
40
|
Hashizume Y, Koizumi T, Akitaya K, Nakajima T, Okamura S, Suzuki M. Singular-value decomposition using quantum annealing. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 92:023302. [PMID: 26382541 DOI: 10.1103/physreve.92.023302] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/21/2015] [Indexed: 06/05/2023]
Abstract
In the present study, we demonstrate how to perform, using quantum annealing, the singular value decomposition and the principal component analysis. Quantum annealing gives a way to find a ground state of a system, while the singular value decomposition requires the maximum eigenstate. The key idea is to transform the sign of the final Hamiltonian, and the maximum eigenstate is obtained by quantum annealing. Furthermore, the adiabatic time scale is obtained by the approximation focusing on the maximum eigenvalue.
Collapse
Affiliation(s)
- Yoichiro Hashizume
- Department of Applied Physics, Tokyo University of Science, Tokyo 125-8585, Japan
| | - Takashi Koizumi
- Department of Applied Physics, Tokyo University of Science, Tokyo 125-8585, Japan
| | - Kento Akitaya
- Department of Applied Physics, Tokyo University of Science, Tokyo 125-8585, Japan
| | - Takashi Nakajima
- Department of Applied Physics, Tokyo University of Science, Tokyo 125-8585, Japan
| | - Soichiro Okamura
- Department of Applied Physics, Tokyo University of Science, Tokyo 125-8585, Japan
| | - Masuo Suzuki
- Computational Astrophysics Laboratory, RIKEN, 2-1 Hirosawa, Wako, Saitama 351-0198, Japan
| |
Collapse
|
41
|
Liu CW, Polkovnikov A, Sandvik AW. Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs. PHYSICAL REVIEW LETTERS 2015; 114:147203. [PMID: 25910158 DOI: 10.1103/physrevlett.114.147203] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/25/2014] [Indexed: 06/04/2023]
Abstract
We discuss an Ising spin glass where each S=1/2 spin is coupled antiferromagnetically to three other spins (3-regular graphs). Inducing quantum fluctuations by a time-dependent transverse field, we use out-of-equilibrium quantum Monte Carlo simulations to study dynamic scaling at the quantum glass transition. Comparing the dynamic exponent and other critical exponents with those of the classical (temperature-driven) transition, we conclude that quantum annealing is less efficient than classical simulated annealing in bringing the system into the glass phase. Quantum computing based on the quantum annealing paradigm is therefore inferior to classical simulated annealing for this class of problems. We also comment on previous simulations where a parameter is changed with the simulation time, which is very different from the true Hamiltonian dynamics simulated here.
Collapse
Affiliation(s)
- Cheng-Wei Liu
- Department of Physics, Boston University, 590 Commonwealth Avenue, Boston, Massachusetts 02215, USA
| | - Anatoli Polkovnikov
- Department of Physics, Boston University, 590 Commonwealth Avenue, Boston, Massachusetts 02215, USA
| | - Anders W Sandvik
- Department of Physics, Boston University, 590 Commonwealth Avenue, Boston, Massachusetts 02215, USA
| |
Collapse
|
42
|
Quhe R, Nava M, Tiwary P, Parrinello M. Path Integral Metadynamics. J Chem Theory Comput 2015; 11:1383-8. [DOI: 10.1021/ct501002a] [Citation(s) in RCA: 17] [Impact Index Per Article: 1.9] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/30/2022]
Affiliation(s)
- Ruge Quhe
- Department
of Chemistry and Applied Biosciences, ETH Zurich, and Facoltà
di Informatica, Istituto di Scienze Computazionali, Università della Svizzera Italiana, Via G. Buffi 13, 6900 Lugano, Switzerland
- State
Key Laboratory of Mesoscopic Physics, Department of Physics and Academy
for Advanced Interdisciplinary Studies, Peking University, Beijing 100871, P. R. China
| | - Marco Nava
- Department
of Chemistry and Applied Biosciences, ETH Zurich, and Facoltà
di Informatica, Istituto di Scienze Computazionali, Università della Svizzera Italiana, Via G. Buffi 13, 6900 Lugano, Switzerland
| | - Pratyush Tiwary
- Department
of Chemistry and Applied Biosciences, ETH Zurich, and Facoltà
di Informatica, Istituto di Scienze Computazionali, Università della Svizzera Italiana, Via G. Buffi 13, 6900 Lugano, Switzerland
| | - Michele Parrinello
- Department
of Chemistry and Applied Biosciences, ETH Zurich, and Facoltà
di Informatica, Istituto di Scienze Computazionali, Università della Svizzera Italiana, Via G. Buffi 13, 6900 Lugano, Switzerland
| |
Collapse
|
43
|
An adiabatic quantum algorithm and its application to DNA motif model discovery. Inf Sci (N Y) 2015. [DOI: 10.1016/j.ins.2014.10.057] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/23/2022]
|
44
|
Nishimori H, Tsuda J, Knysh S. Comparative study of the performance of quantum annealing and simulated annealing. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 91:012104. [PMID: 25679567 DOI: 10.1103/physreve.91.012104] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/01/2014] [Indexed: 06/04/2023]
Abstract
Relations of simulated annealing and quantum annealing are studied by a mapping from the transition matrix of classical Markovian dynamics of the Ising model to a quantum Hamiltonian and vice versa. It is shown that these two operators, the transition matrix and the Hamiltonian, share the eigenvalue spectrum. Thus, if simulated annealing with slow temperature change does not encounter a difficulty caused by an exponentially long relaxation time at a first-order phase transition, the same is true for the corresponding process of quantum annealing in the adiabatic limit. One of the important differences between the classical-to-quantum mapping and the converse quantum-to-classical mapping is that the Markovian dynamics of a short-range Ising model is mapped to a short-range quantum system, but the converse mapping from a short-range quantum system to a classical one results in long-range interactions. This leads to a difference in efficiencies that simulated annealing can be efficiently simulated by quantum annealing but the converse is not necessarily true. We conclude that quantum annealing is easier to implement and is more flexible than simulated annealing. We also point out that the present mapping can be extended to accommodate explicit time dependence of temperature, which is used to justify the quantum-mechanical analysis of simulated annealing by Somma, Batista, and Ortiz. Additionally, an alternative method to solve the nonequilibrium dynamics of the one-dimensional Ising model is provided through the classical-to-quantum mapping.
Collapse
Affiliation(s)
- Hidetoshi Nishimori
- Department of Physics, Tokyo Institute of Technology, Oh-okayama, Meguro-ku, Tokyo 152-8551, Japan
| | - Junichi Tsuda
- Department of Physics, Tokyo Institute of Technology, Oh-okayama, Meguro-ku, Tokyo 152-8551, Japan
| | - Sergey Knysh
- QuAIL, NASA Ames Research Center, Moffett Field, California 94035, USA and SGT Inc., 7701 Greenbelt Road, Suite 400, Greenbelt, Maryland 20770, USA
| |
Collapse
|
45
|
Abstract
We study quantum dynamics of the adiabatic search algorithm with the equivalent two-level system. Its adiabatic and non-adiabatic evolution is studied and visualized as trajectories of Bloch vectors on a Bloch sphere. We find the change in the non-adiabatic transition probability from exponential decay for the short running time to inverse-square decay in asymptotic running time. The scaling of the critical running time is expressed in terms of the Lambert W function. We derive the transitionless driving Hamiltonian for the adiabatic search algorithm, which makes a quantum state follow the adiabatic path. We demonstrate that a uniform transitionless driving Hamiltonian, approximate to the exact time-dependent driving Hamiltonian, can alter the non-adiabatic transition probability from the inverse square decay to the inverse fourth power decay with the running time. This may open up a new but simple way of speeding up adiabatic quantum dynamics.
Collapse
Affiliation(s)
- Sangchul Oh
- Qatar Environment and Energy Research Institute, Qatar Foundation, Doha, Qatar
| | - Sabre Kais
- Qatar Environment and Energy Research Institute, Qatar Foundation, Doha, Qatar
| |
Collapse
|
46
|
Babbush R, Perdomo-Ortiz A, O'Gorman B, Macready W, Aspuru-Guzik A. Construction of Energy Functions for Lattice Heteropolymer Models: Efficient Encodings for Constraint Satisfaction Programming and Quantum Annealing. ADVANCES IN CHEMICAL PHYSICS 2014. [DOI: 10.1002/9781118755815.ch05] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 03/05/2023]
|
47
|
Russomanno A, Silva A, Santoro GE. Periodic steady regime and interference in a periodically driven quantum system. PHYSICAL REVIEW LETTERS 2012; 109:257201. [PMID: 23368490 DOI: 10.1103/physrevlett.109.257201] [Citation(s) in RCA: 28] [Impact Index Per Article: 2.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/02/2012] [Revised: 11/16/2012] [Indexed: 06/01/2023]
Abstract
We study the coherent dynamics of a quantum many-body system subject to a time-periodic driving. We argue that in many cases, destructive interference in time makes most of the quantum averages time periodic, after an initial transient. We discuss in detail the case of a quantum Ising chain periodically driven across the critical point, finding that, as a result of quantum coherence, the system never reaches an infinite temperature state. Floquet resonance effects are moreover observed in the frequency dependence of the various observables, which display a sequence of well-defined peaks or dips. Extensions to nonintegrable systems are discussed.
Collapse
|
48
|
Titiloye O, Crispin A. Parameter tuning patterns for random graph coloring with quantum annealing. PLoS One 2012; 7:e50060. [PMID: 23166818 PMCID: PMC3498173 DOI: 10.1371/journal.pone.0050060] [Citation(s) in RCA: 16] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/17/2012] [Accepted: 10/19/2012] [Indexed: 11/18/2022] Open
Abstract
Quantum annealing is a combinatorial optimization technique inspired by quantum mechanics. Here we show that a spin model for the k-coloring of large dense random graphs can be field tuned so that its acceptance ratio diverges during Monte Carlo quantum annealing, until a ground state is reached. We also find that simulations exhibiting such a diverging acceptance ratio are generally more effective than those tuned to the more conventional pattern of a declining and/or stagnating acceptance ratio. This observation facilitates the discovery of solutions to several well-known benchmark k-coloring instances, some of which have been open for almost two decades.
Collapse
Affiliation(s)
- Olawale Titiloye
- School of Computing, Mathematics and Digital Technology, Manchester Metropolitan University, Manchester, United Kingdom
- * E-mail:
| | - Alan Crispin
- School of Computing, Mathematics and Digital Technology, Manchester Metropolitan University, Manchester, United Kingdom
| |
Collapse
|
49
|
Perdomo-Ortiz A, Dickson N, Drew-Brook M, Rose G, Aspuru-Guzik A. Finding low-energy conformations of lattice protein models by quantum annealing. Sci Rep 2012; 2:571. [PMID: 22891157 PMCID: PMC3417777 DOI: 10.1038/srep00571] [Citation(s) in RCA: 96] [Impact Index Per Article: 8.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/10/2012] [Accepted: 07/16/2012] [Indexed: 12/02/2022] Open
Abstract
Lattice protein folding models are a cornerstone of computational biophysics. Although these models are a coarse grained representation, they provide useful insight into the energy landscape of natural proteins. Finding low-energy threedimensional structures is an intractable problem even in the simplest model, the Hydrophobic-Polar (HP) model. Description of protein-like properties are more accurately described by generalized models, such as the one proposed by Miyazawa and Jernigan (MJ), which explicitly take into account the unique interactions among all 20 amino acids. There is theoretical and experimental evidence of the advantage of solving classical optimization problems using quantum annealing over its classical analogue (simulated annealing). In this report, we present a benchmark implementation of quantum annealing for lattice protein folding problems (six different experiments up to 81 superconducting quantum bits). This first implementation of a biophysical problem paves the way towards studying optimization problems in biophysics and statistical mechanics using quantum devices.
Collapse
Affiliation(s)
- Alejandro Perdomo-Ortiz
- Department of Chemistry and Chemical Biology, Harvard University, 12 Oxford Street, Cambridge, MA 02138, USA
| | - Neil Dickson
- D-Wave Systems, Inc., 100-4401 Still Creek Drive, Burnaby, British Columbia V5C 6G9, Canada
| | - Marshall Drew-Brook
- D-Wave Systems, Inc., 100-4401 Still Creek Drive, Burnaby, British Columbia V5C 6G9, Canada
| | - Geordie Rose
- D-Wave Systems, Inc., 100-4401 Still Creek Drive, Burnaby, British Columbia V5C 6G9, Canada
| | - Alán Aspuru-Guzik
- Department of Chemistry and Chemical Biology, Harvard University, 12 Oxford Street, Cambridge, MA 02138, USA
| |
Collapse
|
50
|
Foini L, Semerjian G, Zamponi F. Solvable model of quantum random optimization problems. PHYSICAL REVIEW LETTERS 2010; 105:167204. [PMID: 21231005 DOI: 10.1103/physrevlett.105.167204] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/25/2010] [Revised: 09/14/2010] [Indexed: 05/30/2023]
Abstract
We study the quantum version of a simplified model of optimization problems, where quantum fluctuations are introduced by a transverse field acting on the qubits. We find a complex low-energy spectrum of the quantum Hamiltonian, characterized by an abrupt condensation transition and a continuum of level crossings as a function of the transverse field. We expect this complex structure to have deep consequences on the behavior of quantum algorithms attempting to find solutions to these problems.
Collapse
Affiliation(s)
- Laura Foini
- LPTENS, CNRS UMR 8549, associée à l'UPMC Paris 06, 24 Rue Lhomond, 75005 Paris, France
| | | | | |
Collapse
|