1
|
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
|
2
|
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
|
3
|
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
|
4
|
|
5
|
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
|
6
|
Abstract
This work focuses on expressing the TSP with Time Windows (TSPTW for short) as a quadratic unconstrained binary optimization (QUBO) problem. The time windows impose time constraints that a feasible solution must satisfy. These take the form of inequality constraints, which are known to be particularly difficult to articulate within the QUBO framework. This is, we believe, the first time this major obstacle is overcome and the TSPTW is cast in the QUBO formulation. We have every reason to anticipate that this development will lead to the actual execution of small scale TSPTW instances on the D-Wave platform.
Collapse
|
7
|
Suksmono AB, Minato Y. Finding Hadamard Matrices by a Quantum Annealing Machine. Sci Rep 2019; 9:14380. [PMID: 31591411 PMCID: PMC6779766 DOI: 10.1038/s41598-019-50473-w] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/25/2019] [Accepted: 09/10/2019] [Indexed: 11/28/2022] Open
Abstract
Finding a Hadamard matrix (H-matrix) among the set of all binary matrices of corresponding order is a hard problem, which potentially can be solved by quantum computing. We propose a method to formulate the Hamiltonian of finding H-matrix problem and address its implementation limitation on existing quantum annealing machine (QAM) that allows up to quadratic terms, whereas the problem naturally introduces higher order ones. For an M-order H-matrix, such a limitation increases the number of variables from M2 to (M3 + M2 - M)/2, which makes the formulation of the Hamiltonian too exhaustive to do by hand. We use symbolic computing techniques to manage this problem. Three related cases are discussed: (1) finding N < M orthogonal binary vectors, (2) finding M-orthogonal binary vectors, which is equivalent to finding a H-matrix, and (3) finding N-deleted vectors of an M-order H-matrix. Solutions of the problems by a 2-body simulated annealing software and by an actual quantum annealing hardware are also discussed.
Collapse
Affiliation(s)
- Andriyan Bayu Suksmono
- School of Electrical Engineering and Informatics, Institut Teknologi Bandung, Jl. Ganesha No.10, Bandung, Indonesia.
| | | |
Collapse
|
8
|
Okada S, Ohzeki M, Taguchi S. Efficient partition of integer optimization problems with one-hot encoding. Sci Rep 2019; 9:13036. [PMID: 31506502 PMCID: PMC6737027 DOI: 10.1038/s41598-019-49539-6] [Citation(s) in RCA: 26] [Impact Index Per Article: 5.2] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/12/2019] [Accepted: 08/27/2019] [Indexed: 12/03/2022] Open
Abstract
Quantum annealing is a heuristic algorithm for solving combinatorial optimization problems, and hardware for implementing this algorithm has been developed by D-Wave Systems Inc. The current version of the D-Wave quantum annealer can solve unconstrained binary optimization problems with a limited number of binary variables. However, the cost functions of several practical problems are defined by a large number of integer variables. To solve these problems using the quantum annealer, integer variables are generally binarized with one-hot encoding, and the binarized problem is partitioned into small subproblems. However, the entire search space of the binarized problem is considerably larger than that of the original integer problem and is dominated by infeasible solutions. Therefore, to efficiently solve large optimization problems with one-hot encoding, partitioning methods that extract subproblems with as many feasible solutions as possible are required. In this study, we propose two partitioning methods and demonstrate that they result in improved solutions.
Collapse
Affiliation(s)
- Shuntaro Okada
- Electronics R & I Division, DENSO CORPORATION, Tokyo, 108-0075, Japan.
- Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579, Japan.
| | - Masayuki Ohzeki
- Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579, Japan
- Institute of Innovative Research, Tokyo Institute of Technology, Yokohama, 226-8503, Japan
- Sigma-i Co. Ltd., Tokyo, 108-0075, Japan
| | | |
Collapse
|
9
|
Okada S, Ohzeki M, Terabe M, Taguchi S. Improving solutions by embedding larger subproblems in a D-Wave quantum annealer. Sci Rep 2019; 9:2098. [PMID: 30765767 PMCID: PMC6376019 DOI: 10.1038/s41598-018-38388-4] [Citation(s) in RCA: 19] [Impact Index Per Article: 3.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/07/2018] [Accepted: 12/27/2018] [Indexed: 11/18/2022] Open
Abstract
Quantum annealing is a heuristic algorithm that solves combinatorial optimization problems, and D-Wave Systems Inc. has developed hardware implementation of this algorithm. However, in general, we cannot embed all the logical variables of a large-scale problem, since the number of available qubits is limited. In order to handle a large problem, qbsolv has been proposed as a method for partitioning the original large problem into subproblems that are embeddable in the D-Wave quantum annealer, and it then iteratively optimizes the subproblems using the quantum annealer. Multiple logical variables in the subproblem are simultaneously updated in this iterative solver, and using this approach we expect to obtain better solutions than can be obtained by conventional local search algorithms. Although embedding of large subproblems is essential for improving the accuracy of solutions in this scheme, the size of the subproblems are small in qbsolv since the subproblems are basically embedded by using an embedding of a complete graph even for sparse problem graphs. This means that the resource of the D-Wave quantum annealer is not exploited efficiently. In this paper, we propose a fast algorithm for embedding larger subproblems, and we show that better solutions are obtained efficiently by embedding larger subproblems.
Collapse
Affiliation(s)
- Shuntaro Okada
- Electronics R & I Division, DENSO Corporation, Tokyo, 103-6015, Japan. .,Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579, Japan.
| | - Masayuki Ohzeki
- Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579, Japan.,Institute of Innovative Research, Tokyo Institute of Technology, Yokohama, 226-8503, Japan
| | - Masayoshi Terabe
- Electronics R & I Division, DENSO Corporation, Tokyo, 103-6015, Japan
| | | |
Collapse
|
10
|
Suksmono AB. Finding a Hadamard Matrix by Simulated Quantum Annealing. ENTROPY 2018; 20:e20020141. [PMID: 33265232 PMCID: PMC7512635 DOI: 10.3390/e20020141] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 01/02/2018] [Revised: 02/06/2018] [Accepted: 02/16/2018] [Indexed: 11/16/2022]
Abstract
Hard problems have recently become an important issue in computing. Various methods, including a heuristic approach that is inspired by physical phenomena, are being explored. In this paper, we propose the use of simulated quantum annealing (SQA) to find a Hadamard matrix, which is itself a hard problem. We reformulate the problem as an energy minimization of spin vectors connected by a complete graph. The computation is conducted based on a path-integral Monte-Carlo (PIMC) SQA of the spin vector system, with an applied transverse magnetic field whose strength is decreased over time. In the numerical experiments, the proposed method is employed to find low-order Hadamard matrices, including the ones that cannot be constructed trivially by the Sylvester method. The scaling property of the method and the measurement of residual energy after a sufficiently large number of iterations show that SQA outperforms simulated annealing (SA) in solving this hard problem.
Collapse
Affiliation(s)
- Andriyan Bayu Suksmono
- Telecommunication Engineering Scientific and Research Group (TESRG), School of Electrical Engineering and Informatics and The Research Center on Information and Communication Technology (PPTIK-ITB), Institut Teknologi Bandung, Jl. Ganesha No.10, Bandung 40132, Indonesia
| |
Collapse
|
11
|
Karimi H, Rosenberg G, Katzgraber HG. Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods. Phys Rev E 2017; 96:043312. [PMID: 29347481 DOI: 10.1103/physreve.96.043312] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/13/2017] [Indexed: 05/26/2023]
Abstract
We present and apply a general-purpose, multistart algorithm for improving the performance of low-energy samplers used for solving optimization problems. The algorithm iteratively fixes the value of a large portion of the variables to values that have a high probability of being optimal. The resulting problems are smaller and less connected, and samplers tend to give better low-energy samples for these problems. The algorithm is trivially parallelizable since each start in the multistart algorithm is independent, and could be applied to any heuristic solver that can be run multiple times to give a sample. We present results for several classes of hard problems solved using simulated annealing, path-integral quantum Monte Carlo, parallel tempering with isoenergetic cluster moves, and a quantum annealer, and show that the success metrics and the scaling are improved substantially. When combined with this algorithm, the quantum annealer's scaling was substantially improved for native Chimera graph problems. In addition, with this algorithm the scaling of the time to solution of the quantum annealer is comparable to the Hamze-de Freitas-Selby algorithm on the weak-strong cluster problems introduced by Boixo et al. Parallel tempering with isoenergetic cluster moves was able to consistently solve three-dimensional spin glass problems with 8000 variables when combined with our method, whereas without our method it could not solve any.
Collapse
Affiliation(s)
- Hamed Karimi
- 1QB Information Technologies (1QBit), 458-550 Burrard Street, Vancouver, British Columbia, Canada V6C 2B5
- Department of Computer Science, University of British Columbia, 2366 Main Mall, Vancouver, British Columbia, Canada V6T 1Z4
| | - Gili Rosenberg
- 1QB Information Technologies (1QBit), 458-550 Burrard Street, Vancouver, British Columbia, Canada V6C 2B5
| | - Helmut G Katzgraber
- 1QB Information Technologies (1QBit), 458-550 Burrard Street, Vancouver, British Columbia, Canada V6C 2B5
- 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
|
12
|
Social Milieu Oriented Routing: A New Dimension to Enhance Network Security in WSNs. SENSORS 2016; 16:247. [PMID: 26907277 PMCID: PMC4801623 DOI: 10.3390/s16020247] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 01/03/2016] [Revised: 02/14/2016] [Accepted: 02/16/2016] [Indexed: 11/17/2022]
Abstract
In large-scale wireless sensor networks (WSNs), in order to enhance network security, it is crucial for a trustor node to perform social milieu oriented routing to a target a trustee node to carry out trust evaluation. This challenging social milieu oriented routing with more than one end-to-end Quality of Trust (QoT) constraint has proved to be NP-complete. Heuristic algorithms with polynomial and pseudo-polynomial-time complexities are often used to deal with this challenging problem. However, existing solutions cannot guarantee the efficiency of searching; that is, they can hardly avoid obtaining partial optimal solutions during a searching process. Quantum annealing (QA) uses delocalization and tunneling to avoid falling into local minima without sacrificing execution time. This has been proven a promising way to many optimization problems in recently published literatures. In this paper, for the first time, with the help of a novel approach, that is, configuration path-integral Monte Carlo (CPIMC) simulations, a QA-based optimal social trust path (QA_OSTP) selection algorithm is applied to the extraction of the optimal social trust path in large-scale WSNs. Extensive experiments have been conducted, and the experiment results demonstrate that QA_OSTP outperforms its heuristic opponents.
Collapse
|
13
|
Inack EM, Pilati S. Simulated quantum annealing of double-well and multiwell potentials. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 92:053304. [PMID: 26651813 DOI: 10.1103/physreve.92.053304] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/28/2015] [Indexed: 06/05/2023]
Abstract
We analyze the performance of quantum annealing as a heuristic optimization method to find the absolute minimum of various continuous models, including landscapes with only two wells and also models with many competing minima and with disorder. The simulations performed using a projective quantum Monte Carlo (QMC) algorithm are compared with those based on the finite-temperature path-integral QMC technique and with classical annealing. We show that the projective QMC algorithm is more efficient than the finite-temperature QMC technique, and that both are inferior to classical annealing if this is performed with appropriate long-range moves. However, as the difficulty of the optimization problem increases, classical annealing loses efficiency, while the projective QMC algorithm keeps stable performance and is finally the most effective optimization tool. We discuss the implications of our results for the outstanding problem of testing the efficiency of adiabatic quantum computers using stochastic simulations performed on classical computers.
Collapse
Affiliation(s)
- E M Inack
- The Abdus Salam International Centre for Theoretical Physics, I-34151 Trieste, Italy
- SISSA, International School for Advanced Studies and INFN, Sezione di Trieste, I-34136 Trieste, Italy
| | - S Pilati
- The Abdus Salam International Centre for Theoretical Physics, I-34151 Trieste, Italy
| |
Collapse
|
14
|
Soley M, Markmann A, Batista VS. Steered quantum dynamics for energy minimization. J Phys Chem B 2015; 119:715-27. [PMID: 25122515 DOI: 10.1021/jp5046723] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/30/2022]
Abstract
We introduce a quantum optimal control algorithm for energy minimization that combines the diffeomorphic modulation under observable response preserving homotopy (D-MORPH) gradient and the Broyden Fletcher Goldfarb Shanno (BFGS) iterative scheme for nonlinear optimization. An extended set of controls defining the time-dependent mass, dipole moment, and external perturbational field are optimized to find an effective Hamiltonian that steers the dynamics of the system into the global minimum without getting trapped into local minima. The algorithm is illustrated as applied to energy minimization on rugged surfaces and golf potentials comparable to those previously explored for testing quantum annealing methodologies.
Collapse
Affiliation(s)
- Micheline Soley
- Department of Chemistry, Yale University , P.O. Box 208107, New Haven, Connecticut 06520-8107, United States
| | | | | |
Collapse
|
15
|
Clark KB. Basis for a neuronal version of Grover's quantum algorithm. Front Mol Neurosci 2014; 7:29. [PMID: 24860419 PMCID: PMC4029008 DOI: 10.3389/fnmol.2014.00029] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/15/2014] [Accepted: 03/31/2014] [Indexed: 11/25/2022] Open
Abstract
Grover's quantum (search) algorithm exploits principles of quantum information theory and computation to surpass the strong Church–Turing limit governing classical computers. The algorithm initializes a search field into superposed N (eigen)states to later execute nonclassical “subroutines” involving unitary phase shifts of measured states and to produce root-rate or quadratic gain in the algorithmic time (O(N1/2)) needed to find some “target” solution m. Akin to this fast technological search algorithm, single eukaryotic cells, such as differentiated neurons, perform natural quadratic speed-up in the search for appropriate store-operated Ca2+ response regulation of, among other processes, protein and lipid biosynthesis, cell energetics, stress responses, cell fate and death, synaptic plasticity, and immunoprotection. Such speed-up in cellular decision making results from spatiotemporal dynamics of networked intracellular Ca2+-induced Ca2+ release and the search (or signaling) velocity of Ca2+ wave propagation. As chemical processes, such as the duration of Ca2+ mobilization, become rate-limiting over interstore distances, Ca2+ waves quadratically decrease interstore-travel time from slow saltatory to fast continuous gradients proportional to the square-root of the classical Ca2+ diffusion coefficient, D1/2, matching the computing efficiency of Grover's quantum algorithm. In this Hypothesis and Theory article, I elaborate on these traits using a fire-diffuse-fire model of store-operated cytosolic Ca2+ signaling valid for glutamatergic neurons. Salient model features corresponding to Grover's quantum algorithm are parameterized to meet requirements for the Oracle Hadamard transform and Grover's iteration. A neuronal version of Grover's quantum algorithm figures to benefit signal coincidence detection and integration, bidirectional synaptic plasticity, and other vital cell functions by rapidly selecting, ordering, and/or counting optional response regulation choices.
Collapse
Affiliation(s)
- Kevin B Clark
- Research and Development Service, Veterans Affairs Greater Los Angeles Healthcare System Los Angeles, CA, USA ; Complex Biological Systems Alliance North Andover, MA, USA
| |
Collapse
|
16
|
Clark KB. Ciliates learn to diagnose and correct classical error syndromes in mating strategies. Front Microbiol 2013; 4:229. [PMID: 23966987 PMCID: PMC3746415 DOI: 10.3389/fmicb.2013.00229] [Citation(s) in RCA: 12] [Impact Index Per Article: 1.1] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/28/2013] [Accepted: 07/28/2013] [Indexed: 01/06/2023] Open
Abstract
Preconjugal ciliates learn classical repetition error-correction codes to safeguard mating messages and replies from corruption by “rivals” and local ambient noise. Because individual cells behave as memory channels with Szilárd engine attributes, these coding schemes also might be used to limit, diagnose, and correct mating-signal errors due to noisy intracellular information processing. The present study, therefore, assessed whether heterotrich ciliates effect fault-tolerant signal planning and execution by modifying engine performance, and consequently entropy content of codes, during mock cell–cell communication. Socially meaningful serial vibrations emitted from an ambiguous artificial source initiated ciliate behavioral signaling performances known to advertise mating fitness with varying courtship strategies. Microbes, employing calcium-dependent Hebbian-like decision making, learned to diagnose then correct error syndromes by recursively matching Boltzmann entropies between signal planning and execution stages via “power” or “refrigeration” cycles. All eight serial contraction and reversal strategies incurred errors in entropy magnitude by the execution stage of processing. Absolute errors, however, subtended expected threshold values for single bit-flip errors in three-bit replies, indicating coding schemes protected information content throughout signal production. Ciliate preparedness for vibrations selectively and significantly affected the magnitude and valence of Szilárd engine performance during modal and non-modal strategy corrective cycles. But entropy fidelity for all replies mainly improved across learning trials as refinements in engine efficiency. Fidelity neared maximum levels for only modal signals coded in resilient three-bit repetition error-correction sequences. Together, these findings demonstrate microbes can elevate survival/reproductive success by learning to implement classical fault-tolerant information processing in social contexts.
Collapse
Affiliation(s)
- Kevin B Clark
- Research and Development Service, Veterans Affairs Greater Los Angeles Healthcare System Los Angeles, CA, USA
| |
Collapse
|
17
|
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
|
18
|
Clark KB. Bose–Einstein condensates form in heuristics learned by ciliates deciding to signal ‘social’ commitments. Biosystems 2010; 99:167-78. [DOI: 10.1016/j.biosystems.2009.10.010] [Citation(s) in RCA: 8] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/19/2009] [Revised: 10/22/2009] [Accepted: 10/27/2009] [Indexed: 10/20/2022]
|
19
|
Morita S, Suzuki S, Nakamura T. Quantum-thermal annealing with a cluster-flip algorithm. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2009; 79:065701. [PMID: 19658557 DOI: 10.1103/physreve.79.065701] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/09/2009] [Indexed: 05/28/2023]
Abstract
A quantum-thermal annealing method using a cluster-flip algorithm is studied in the two-dimensional spin-glass model. The temperature (T) and the transverse field (Gamma) are decreased simultaneously with the same rate along a linear path on the T-Gamma plane. We found that the additional pulse of the transverse field to the frozen local spins produces a good approximate solution with a low computational cost.
Collapse
Affiliation(s)
- Satoshi Morita
- International School for Advanced Studies, Trieste 34151, Italy
| | | | | |
Collapse
|
20
|
Suzuki S, Nishimori H, Suzuki M. Quantum annealing of the random-field Ising model by transverse ferromagnetic interactions. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2007; 75:051112. [PMID: 17677027 DOI: 10.1103/physreve.75.051112] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/07/2007] [Indexed: 05/16/2023]
Abstract
We introduce transverse ferromagnetic interactions, in addition to a simple transverse field, to accelerate the convergence of quantum annealing of the random-field Ising model. The conventional approach using only the transverse-field term is known to be plagued by slow convergence when the true ground state has strong ferromagnetic characteristics for the random-field Ising model. The transverse ferromagnetic interactions are shown to improve the performance significantly in such cases. This conclusion is drawn from the analyses of the energy eigenvalues of instantaneous stationary states as well as by the very fast algorithm of Bethe-type mean-field annealing adopted to quantum systems. The present study highlights the importance of a flexible choice of the type of quantum fluctuations to achieve the best possible performance in quantum annealing. The existence of such flexibility is an outstanding advantage of quantum annealing over simulated annealing.
Collapse
Affiliation(s)
- Sei Suzuki
- Department of Physics, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo, Japan.
| | | | | |
Collapse
|
21
|
Stella L, Santoro GE. Quantum annealing of an Ising spin-glass by Green's function Monte Carlo. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2007; 75:036703. [PMID: 17500822 DOI: 10.1103/physreve.75.036703] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/05/2006] [Revised: 12/08/2006] [Indexed: 05/15/2023]
Abstract
We present an implementation of quantum annealing (QA) via lattice Green's function Monte Carlo (GFMC), focusing on its application to the Ising spin glass in transverse field. In particular, we study whether or not such a method is more effective than the path-integral Monte Carlo- (PIMC) based QA, as well as classical simulated annealing (CA), previously tested on the same optimization problem. We identify the issue of importance sampling, i.e., the necessity of possessing reasonably good (variational) trial wave functions, as the key point of the algorithm. We performed GFMC-QA runs using such a Boltzmann-type trial wave function, finding results for the residual energies that are qualitatively similar to those of CA (but at a much larger computational cost), and definitely worse than PIMC-QA. We conclude that, at present, without a serious effort in constructing reliable importance sampling variational wave functions for a quantum glass, GFMC-QA is not a true competitor of PIMC-QA.
Collapse
Affiliation(s)
- Lorenzo Stella
- International School for Advanced Studies (SISSA) and INFM Democritos National Simulation Center, Via Beirut 2-4, I-34014 Trieste, Italy
| | | |
Collapse
|
22
|
|
23
|
Santoro GE, Tosatti E. Optimization using quantum mechanics: quantum annealing through adiabatic evolution. ACTA ACUST UNITED AC 2006. [DOI: 10.1088/0305-4470/39/36/r01] [Citation(s) in RCA: 225] [Impact Index Per Article: 12.5] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/12/2022]
|