Quantum Adiabatic Computation, where the mathematics is trying to tell us something

Lecturer:     Prof. Edmond Jonckheere, University of Southern California
Date and time: 2nd November 2015, 6:00 p.m.
Place: lecture room T9:105, FIT CTU in Prague, 9 Thákurova Street
Language: English

Share event on logo_FB Facebook#FITpcpS

Adiabatic Quantum Computations (AQC) endeavors to solve Quadratic Unconstrained Binary Optimization (QUBO) problems, e.g., satisfiability (SAT) problems, by mapping the QUBO problem to the problem of finding the ground state of an Ising chain. Starting from the ground state of a simple Ising problem, a continuation method, implemented by solving the Schrödinger equation with time-varying Hamiltonian, moves the easily computable ground eigenstate to the ground eigenstate of the difficult problem. The so-called “gap,” where the ground and the first excited energy level curves come dangerously close, requires the integration of Schrödinger equation to be slowed down, to remain “adiabatic.” As a first hard question, we ask, Why does this gap occur in the first place? Unbeknown outside the mathematical community is that it occurs because of a differential topological feature—the emergence of swallow tail  ingularities in the matrix numerical range formulation of the adiabatic problem. In a remarkable paper by von Neumann where he anticipated AQC, he “nailed” the case of a “mild gap,” where the two curves are coming close in a slow and smooth fashion. Those days, differential topology was in its infancy and the more recent work of such mathematical giants as Arnold, Mather, Golubitsky, Guillemin, and many others reveals that the two curves could have quite different morphologies, including a computationally dangerous “super-steep” gap. The difference between mild, steep, and super-steep gap is differential topological and we will endeavor to develop a topological invariant anticipating the steep gap. The various morphologies of the curves are easily visually observed, but the mathematics sneaks more insidiously when it comes to the numerically observed “extreme sensitivity” of the ground level of an Ising chain to data perturbation, a problem that is haunting the developers of the D-Wave adiabatic computer. In mathematical language, it turns out that the extreme sensitivity is an oversimplification of the well-known differential topological issue of stability of maps: The energy map of an Ising chain is topologically unstable, meaning that the curves are not smoothly deformed under data perturbation, but their morphology is completely shattered! Finally, it will be shown that a super-steep gap is symptomatic of the adiabatic path tunneling through a barrier to reach the minimum.  To paraphrase Max Tegmark from MIT, who said that “all structures that exist mathematically exist also physically,” the physical existence of the swallow tail singularity is the quantum mechanical tunneling.


Last modified: 11.3.2016, 15:05