Probabilistic information processing via quantum fluctuation

洋介大坪

Published Mar 24, 2014• 0 citations

Abstract

This thesis provides theoretical studies on a probabilistic information processing incorporated quantum fluctuations through statistical mechanical approaches.Quantum fluctuations cause transitions between states, which play same role as thermal fluctuations.Such an idea has been used in optimization problems for searching a ground state of a cost function.The algorithm is called quantum annealing (QA) in a manner analogous to simulated annealing.Simulated annealing is the conventional algorithm for finding the ground state by using the thermal fluctuations.QA has been applied to various optimization problems by solving the Schrödinger equation or carrying out Quantum Monte Carlo simulations on classical computers.However, what we call a quantum annealer with current superconducting devices has been launched by D-wave systems.For this situation, the algorithms by using the quantum fluctuations have received a lot of attention in recent years.With the developments in the research fields of the algorithms by making use of the quantum fluctuations, it is also interesting for us to consider the possible application of the quantum fluctuations to probabilistic information processing.Main problem of the probabilistic information processing in the context of this thesis is to recover the original information from damaged information, e.g., image restoration, error correcting codes, and CDMA multiuser demodulation.Such problems can be denoted as the infiniterange spin glass model, adopting the framework of Bayesian statistics.Then, we can apply statistical mechanical approaches to it in order to figure out the average-case performance of those systems.We examine the average-case performance of the probabilistic information processing in which quantum fluctuations is utilized to recover the original information in the context of the Bayesian inference.The quantum fluctuations are built into the system as transverse fields put in the infinite-range Ising spin glass model.We evaluate the performance measurement by using statistical mechanics which mean mean-field theory.Accordingly, we find the following properties on the quantum fluctuations in the probabilistic information processing

DOI: 10.15083/00007102

Related papers

Statistical mechanics of disordered quantum optimization

Chris R. Laumann

The classical statistical mechanical approach to complexity theory proceeds from the study of ensembles of computationally intractable optimization problems as a species of unusual disordered magnetic systems. Over the last thirty years, researchers have used this approach to supplement worst-case hardness results encoded by complexity theory with detailed information about thermodynamic and dynamic phase transitions in the structure of typical cases. This exchange of ideas between classical statistical mechanics and computer science enabled the development of important heuristic algorithms such as simulated annealing and survey propagation and further refined our understanding of glassiness and critical slowing in physical disordered systems. In this thesis, we map out an analogous program in the quantum context. The question is simple: what can quantum statistical mechanics reveal about the difficulty of solving hard quantum optimization problems? Or more directly, what makes those problems hard even for quantum computers? In this pursuit, we introduce the study of ensembles of optimization problems whose complexity status is intrinsically quantum mechanical (Part I) and develop techniques to study quantum spin glasses and the transverse field adiabatic algorithm applied to classically hard random optimization problems (Part II). In particular, we introduce the study of random quantum satisfiability (QSAT) and identify the coarse aspects of its phase diagram, including a new form of entanglement transition. We generalize the cavity method to the study of quantum models and use it to study the transverse field Ising glass and frustrated AKLT models on the Bethe lattice. We further apply the cavity method to extract Griffiths-McCoy singularities in a diluted (classical) ferromagnet and finally observe that there are no Goldstone bosons on the Bethe lattice.

Jan 1, 20101 citation

Quantum annealing in the transverse Ising model

Tadashi Kadowaki, Hidetoshi Nishimori

We introduce quantum fluctuations into the simulated annealing process of optimization problems, aiming at faster convergence to the optimal state. Quantum fluctuations cause transitions between states and thus play the same role as thermal fluctuations in the conventional approach. The idea is tested by the transverse Ising model, in which the transverse field is a function of time similar to the temperature in the conventional method. The goal is to find the ground state of the diagonal part of the Hamiltonian with high accuracy as quickly as possible. We have solved the time-dependent Schr\"odinger equation numerically for small size systems with various exchange interactions. Comparison with the results of the corresponding classical (thermal) method reveals that the quantum annealing leads to the ground state with much larger probability in almost all cases if we use the same annealing schedule.

arXiv:cond-mat/9804280Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsNov 1, 19982,336 citations

Study of Optimization Problems by Quantum Annealing

Tadashi Kadowaki

We introduce quantum fluctuations into the simulated annealing process of optimization problems, aiming at faster convergence to the optimal state. The idea is tested by the two models, the transverse Ising model and the traveling salesman problem (TSP). Adding the transverse field to the Ising model is a simple way to introduce quantum fluctuations. The strength of the transverse field is controlled as a function of time similarly to the temperature in the conventional method. TSP can be described by the Ising spin, so that we also apply the same technique to TSP. We directory solve the time-dependent Schrödinger equation for small-size systems and perform the quantum Monte Carlo simulation for large-size systems. Comparison with the results of the corresponding classical (thermal) method reveals that the quantum method leads to the ground state with much larger probability in almost all cases if we use the same annealing schedule of the control parameters. We also find that the relaxation time is quite short for quantum systems by numerical simulations. We consider this is one of the reasons why the annealing in quantum systems have a better performance of finding the optimal state in comparison with classical systems.

arXiv:quant-ph/0205020May 5, 200239 citations

Quantum annealing and digital quantum ground state preparation algorithms

Glen Bigan Mbeng

The recent advances in the world of quantum technologies have prompted the development of various quantum-based algorithms, some of which are suitable to run on available quantum devices. Two leading candidates in this area are Quantum Annealing (QA) and hybrid quantum-classical variational algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA). In the first part of the Thesis, we re-examine the issue of whether Simulated Quantum Annealing (SQA) with Path Integral Monte Carlo has anything to do with the coherent QA Schrödinger dynamics. We do that by studying the random quantum Ising Chain in a transverse field. In the second part of the Thesis we address the issue of schedule optimization in both {em digitized}-QA and QAOA. Traditional schedule optimization in QA requires spectral information on the problem (e.g., location of the minimum gaps), which is in most cases inaccessible. On the other hand, in QAOA, the issue of schedule optimization --- alias, the optimization of the variational parameters --- is often an expensive task that constitutes a bottleneck for the algorithm. We show that, by combining the framework of QAOA and digitized-QA, optimal digitized-QA protocols can be constructed efficiently. When using this approach, the computational cost of schedule optimization is also significantly reduced, leading to a computational advantage both over a linear-schedule QA, and over an unstructured QAOA search. While studying these issues, we also developed rigorous variational bounds that provide insight on the best possible performance that one can hope to obtain from a digital QAOA circuit.

Oct 24, 20192 citations

平均場模型の量子アニーリングにおける量子相転移の制御

優也関, Yuya Seki

The present thesis studies statistical-mechanical properties of mean-field models to reveal an effect of various types of quantum fluctuations against the efficiency of quantum annealing.Quantum annealing is a quantum computation model to search the ground state of Ising spin systems by taking advantage of quantum fluctuations.The quantum fluctuations are usually induced by the transverse-field term.However, it has been reported that the quantum annealing with the transverse-field term has a difficulty of exponentially long running time for certain problems.For example, quantum annealing cannot find even the ground state of a simple ferromagnetic system.The difficulty is closely related to the phenomena of quantum phase transitions.Quantum annealing typically requires exponentially long time to find the ground state of a system, if the system undergoes a first-order quantum phase transition in the thermodynamics limit.Hence, avoiding firstorder quantum phase transitions is a critical issue for quantum annealing.A solution to avoid the difficulty mentioned above is to use a degree of freedom of quantum annealing.Although many studies adopt the transverse-field term to induce quantum fluctuations, there is no restriction to use the term.The present thesis shows that the difficulty for the simple ferromagnetic system can be avoided by using transverse antiferromagnetic interactions.Furthermore, the antiferromagnetic term turns out to be also effective for a random spin system.We next focus on the macroscopic degeneracy of the ground states of the antiferromagnetic term.In order to reveal the effect of the macroscopic degeneracy, the Wajnflasz-Pick model is analyzed.The Wajnflasz-Pick model is interesting also in terms of providing an alternative way to control the order of quantum phase transitions.iii I would like to thank my supervisor Prof. Hidetoshi Nishimori for his guidance and revisions of the thesis and the papers we co-authored.The studies in the present thesis could not have been accomplished without his insightful advice.I am also grateful to Dr. Kazutaka Takahashi for fruitful discussions.I would like to

Mar 1, 20160 citations

Optimization Via Open System Quantum Annealing

Sergio Boixo, Robert F. Lucas, Daniel A. Lidar +2 more

Abstract : Many computationally challenging problems can be reduced to Quadratic Unconstrained Binary Optimization (QUBO), which can be solved by a quantum evolution from a strong transverse field to a spin glass Hamiltonian (also known as quantum annealing or QA). We have examined open system QA, using theoretical and experimental techniques to deepen our understanding of open system QA by situating it in the context of related, well studied classical and quantum problems. We have explored and elucidated the significance of tunneling in QA with Path Integral Monte Carlo. We have also provided signatures of quantum behavior of QA against closely related simulated annealing implementations, analytically, numerically, and experimentally. We have carried out a comprehensive comparison of geometrically-local open-system QA and classical solvers for computationally hard problems such as MAX-2-SAT. We have exploited and further developed a graph-theoretical mapping between the Ising spin glass partition function and circuit model decision problems, discovered in a previous ARO Quantum Algorithms funded project. We have made significant progress on error correction techniques for QA, both theoretically and experimentally, and in demonstration of quantum speedup.

Jan 7, 20160 citations