Session B27: Focus Session: Adiabatic Quantum Computing II

On optimal methods for adiabatic quantum state transformations

Many problems in science could be solved by preparing the low-energy quantum state (or any eigenstate) of a Hamiltonian. A common example is the Boolean satisfiability problem, where each clause can be mapped to the energy of an interacting many-body system, and the problem reduces to minimizing the energy. In quantum computing, adiabatic quantum state transformations (ASTs) provide a tool for preparing the quantum state. ASTs are conventionally implemented via slow or adiabatic perturbations to the Hamiltonian, relying on the quantum adiabatic theorem. Nevertheless, more efficient implementations of ASTs exist. In this talk I will review recently developed methods for ASTs that are more efficient and require less assumptions on the Hamiltonians than the conventional implementation [1,2]. Such methods involve measurements of the states along the evolution path and have a best-case implementation cost of L/G, where L is the length of the (evolved) state path and G is a lower bound to the spectral gap of the Hamiltonians. I will show that this cost is optimal [3] and comment on results of the gap amplification problem, where the goal is to reduce the cost by increasing G [4].\\[4pt] [1] S. Boixo, E. Knill, and R.D. Somma, ``Quantum state preparation by phase randomization,'' Quant. Inf. Comp. 9, 833 (2009).\\[0pt] [2] S. Boixo, E. Knill, and R.D. Somma, ``Fast quantum algorithms for traversing paths of eigenstates,'' e-print arXiv:1005.3034 (2010).\\[0pt] [3] R.D. Somma and S. Boixo, ``Necessary condition for the quantum adiabatic approximation,'' Phys. Rev. A 81, 032308 (2010).\\[0pt] [4] R.D. Somma and S. Boixo, ``Spectral gap amplification,'' SIAM J. Comp. (2012).   

Quantum Adiabatic Markovian Master Equations

We develop from first principles Markovian master equations suited for studying the time evolution of a system evolving adiabatically while coupled weakly to a thermal bath. We derive two sets of equations in the adiabatic limit, one using the rotating wave approximation that results in a master equation in Lindblad form, the other without the rotating wave approximation but not in Lindblad form. We use our formalism to study the evolution of Ising spin Hamiltonians and compare to experimental results from the D-Wave One Rainier chip. In particular, we study an Ising Hamiltonian that gives markedly different predictions for the ground state spectrum when solved using classical thermal annealing versus quantum annealing, and our master equations give qualitatively consistent results with the results of the D-Wave chip.   

Quantum Simulation for Open-System Dynamics

Simulations are essential for predicting and explaining properties of physical and mathematical systems yet so far have been restricted to classical and closed quantum systems [1,2]. Although forays have been made into open-system quantum simulation [3], the strict algorithmic aspect has not been explored yet is necessary to account fully for resource consumption to deliver bounded-error answers to computational questions. An open-system quantum simulator would encompass classical and closed-system simulation and also solve outstanding problems concerning, e.g. dynamical phase transitions in non-equilibrium systems, establishing long-range order via dissipation, verifying the simulatability of open-system dynamics on a quantum Turing machine. We construct an efficient autonomous algorithm for designing an efficient quantum circuit to simulate many-body open-system dynamics described by a local Hamiltonian plus decoherence due to separate baths for each particle. The execution time and number of gates for the quantum simulator both scale polynomially with the system size.\\[4pt] [1] S. Lloyd, Science 273, 1073 (1996).\\[0pt] [2] D. W. Berry et al, Comm. Math. Phys. 270, 359 (2007).\\[0pt] [3] M. Kliesch et al, Phys. Rev. Lett. 107, 120501 (2011).   

Complexity of the Quantum Adiabatic Algorithm

The Quantum Adiabatic Algorithm (QAA) has been proposed as a mechanism for efficiently solving optimization problems on a quantum computer. Since adiabatic computation is analog in nature and does not require the design and use of quantum gates, it can be thought of as a simpler and perhaps more profound method for performing quantum computations that might also be easier to implement experimentally. While these features have generated substantial research in QAA, to date there is still a lack of solid evidence that the algorithm can outperform classical optimization algorihms. Here, we discuss several aspects of the quantum adiabatic algorithm: We analyze the efficiency of the algorithm on several ``hard'' (NP) computational problems. Studying the size dependence of the typical minimum energy gap of the Hamiltonians of these problems using quantum Monte Carlo methods, we find that while for most problems the minimum gap decreases exponentially with the size of the problem, indicating that the QAA is not more efficient than existing classical search algorithms, for other problems there is evidence to suggest that the gap may be polynomial near the phase transition. We also discuss applications of the QAA to ``real life'' problems and how they can be implemented on currently available (albeit prototypical) quantum hardware such as ``D-Wave One'', that impose serious restrictions as to which type of problems may be tested. Finally, we discuss different approaches to find improved implementations of the algorithm such as local adiabatic evolution, adaptive methods, local search in Hamiltonian space and others.   

Power law scaling for the adiabatic algorithm for search engine ranking

An important method for search engine result ranking works by finding the principal eigenvector of the ``Google matrix." Recently, a quantum algorithm for this problem and evidence of an exponential speedup for some scale-free networks were presented. Here, we show that the run-time depends on features of the graphs other than the degree distribution, and can be altered sufficiently to rule out a general exponential speedup. For a sample of graphs with degree distributions that more closely resemble the Web than in the previous work, the proposed algorithm does not appear to run exponentially faster than the classical one.   

Frustration and ground state entanglement in 2D lattices

We investigate frustrated 2D lattice systems with an Ising-type interaction using exact diagonalization and Tensor Network techniques. The geometric frustration in these systems is controlled by the couplings of the Hamiltonian. We study the ground state entanglement for the combination of model parameters inducing a higher degree of frustrated interactions, showing relations between the frustration and the amount of quantum correlations present along different partitions of the lattice. Using the connection between ground state entanglement and the classical simulation of quantum systems, these results point to scenarios where simulating local systems is supposed to be hard.   

Cycloid trajectory for a spin in a rotating magnetic field

A cycloid is a curve traced by a point on the rim of a circle rolling on a straight (or in general, a base) line. In classical mechanics, it is known as the solution of two famous problems: the brachistochrone (least-time) curve and tautochrone (equal-time) curve. Here we show that a cycloid is the quantum trajectory on the Bloch sphere when a spin is dragged along by a rotating magnetic field. Here an imaginary circle, whose radius is determined by how fast the magnetic field is rotating, rolls on the base line of the rotating magnetic field on the Bloch sphere. If the magnetic field rotates slower, the radius of the rolling circle shrinks (to a point at the adiabatic limit, when the trajectory traces a circle that spans a solid angle proportional to the Berry phase). We find that like classical cycloid curves, the curtate cycloid on a Bloch sphere is generated for initial states within a circle on the Bloch sphere surface, and a prolate cycloid results from initial states outside of this circle. If the initial state is given by the center of the circle, the quantum trajectory is a line of a constant latitude on the Bloch sphere, parallel to the curve of the rotating magnetic field.   

Fibonacci wires

We show that models for one-dimensional quantum chains with local interactions can exhibit non-Abelian end modes, going beyond Kitaev's Majorana chain. We describe a model for a special case of $\rm{SU(2)}_k$ anyons, in particular Fibonacci anyons, and show how braiding of non-Abelian end modes can be done in networks of such chains.   

Dynamical scaling in infinitely correlated many-body systems through a quantum phase transition

We assess dynamical scaling of many two-level systems (TLSs) infinitely correlated, either through a mediating radiation mode as in the Dicke Model, or through a direct interaction between TLSs as in the Lipkin-Meshkov-Glick model. Those models are characterized by the presence of a Quantum Phase Transition (QPT) in the thermodynamic limit, and they belong to the same universality class. The assessment is done by means of exact computational simulations of finite-size systems under linear rampings of the interaction parameter crossing the quantum critical point. Our results exhibit significant differences with respect to previous works on dynamical scaling across QPTs in the near-adiabatic regime, which have focused on spin-chain models where correlation lengths can be defined. We have confirmed that in infinitely correlated models an effective system size can play the role of the correlation length in traditional scaling arguments. However, due to the infinite correlation among TLSs, the standard Kibble-Zurek mechanism is not realized as the system cannot fully enter an adiabatic evolution during the ordered phase. Also, in the two-level approximation, a suitable deviation from the standard Landau-Zener protocol must be performed in order to obtain scaling collapse.   

Phase transition detection using Renyi entropy in quantum and classical systems

By extending the calculation of the Renyi entropy from quantum models [Phys. Rev. B 82, 100409(R) (2010)] to classical modes, we introduce a general procedure to calculate the Renyi mutual information in Monte Carlo simulations. Examining an array of quantum and classical models we show that the mutual information is able to detect general finite temperature phase transitions from different universality classes without knowledge of the specific order parameter or any special thermodynamic estimators. We demonstrate this technique on a standard symmetry breaking phase transition, the classical Ising model and anisotropic Heisenberg model, and a vortex-unbinding transition without a local order parameter, the classical and quantum XY model, and present the details necessary to implement this procedure on other models [arXiv:1210.2403].