Session T30: Quantum Algorithms

Adiabatic Surface Code Quantum Computing

There are many approaches to constructing a quantum computer. In addition to the numerous different physical substrates available, there are a plethora of different underlying computational architectures from which to choose. Two major classes of architectures can be distinguished: those requiring a substantial external active control system to suppress errors, and those whose underlying physical construction eliminates much, if not all, of the need for such a control system. Here we focus on the latter class of architectures and address the question: ``How does one fault-tolerantly quantum compute on a system protected from decoherence by a static Hamiltonian?'' We present a solution that adiabatically interpolates between static Hamiltonians, each of which protects the quantum information stored in its ground space. Since each of these ground spaces can be described as a quantum error-correcting codespace, we call this process adiabatic code deformation. After describing a particular surface code (the toric code) and the way to encode information in code defects, we give explicit adiabatic interpolations that effect braids between defects, allowing for a CNOT gate between encoded qubits. We finish by describing how to extend our procedures to allow for universality.   

Quantum Random Walks and the Graph Isomorphism Problem

We investigate the quantum dynamics of particles on graphs (``quantum walk''), with the aim of developing quantum algorithms for determining whether or not two graphs are isomorphic. We investigate such walks on strongly regular graphs (SRGs), a class of graphs with high symmetry. We explore the effects of particle number and interaction range on a walk's ability to distinguish non-isomorphic graphs. We numerically find that both non-interacting three-boson and three-fermion continuous time walks have the same distinguishing power on a dataset of 70,712 pairs of SRGs, each distinguishing over 99.6\% of the pairs. We also find that increasing to four non-interacting particles further increases distinguishing power on this dataset. While increasing particle number increases distinguishing power, we prove that any walk of a fixed number of non-interacting particles cannot distinguish all SRGs. We numerically find that increasing particle number and increasing interaction range both result in increased distinguishing power of non-SRGs that are designed to be indistinguishable to the hard-core two-boson walk.   

Hamiltonian Simulation Using Linear Combinations of Unitary Operations

We present a new approach to simulating Hamiltonian dynamics based on implementing linear combinations of unitary operations rather than products of unitary operations. The resulting algorithm has superior performance to existing simulation algorithms based on product formulas and, most notably, scales better with the simulation error than any known Hamiltonian simulation technique. Our main tool is a general method to nearly deterministically implement linear combinations of similar unitary operations, which we show is optimal among a large class of methods.   

Measurement-Based Quantum Computation with Thermal States and Always-on Interactions

Quantum computation can be achieved by single-qubit measurements on an initial entangled state. It is often implicitly assumed that the interactions between spins can be switched off so that the dynamics of the measured spins does not affect the computation. We propose a model spin Hamiltonian so that measurement-based quantum computation can be accomplished on a thermal state with always-on interactions. Moreover, computational errors induced by thermal fluctuations can be corrected and thus the computation can be executed fault tolerantly if the temperature is below a threshold value.   

Quantum Computational Universality of the 2D Cai-Miyake-D\"ur-Briegel Quantum State

Universal quantum computation can be achieved by simply performing single-qubit measurements on a highly entangled resource state, such as cluster states. Cai, Miyake, D\"ur, and Briegel recently constructed a ground state of a two-dimensional quantum magnet by combining multiple Affleck-Kennedy-Lieb-Tasaki quasichains of mixed spin-3/2 and spin-1/2 entities and by mapping pairs of neighboring spin-1/2 particles to individual spin-3/2 particles [Phys. Rev. A {\bf 82}, 052309 (2010)]. They showed that this state enables universal quantum computation by constructing single- and two-qubit universal gates. Here, we give an alternative understanding of how this state gives rise to universal measurement-based quantum computation: by local operations, each quasichain can be converted to a one-dimensional cluster state and entangling gates between two neighboring logical qubits can be implemented by single-spin measurements. Furthermore, a two-dimensional cluster state can be distilled from the Cai-Miyake-D\"ur-Briegel state.   

Algorithmic Quantum Cooling

Efficient methods of cooling are essential for exploring the fundamental properties of low temperature physics. A remarkable cooling method is known as the evaporative cooling (or ``coffee'' cooling), where energetic particles are filtered away so as to lower the mean energy of the rest of the system. Inspired by the idea of evaporative cooling, we developed a method called algorithmic quantum cooling (AQC) for achieving the goal of cooling for any physical system which is simulable by a quantum computer. The novel feature of AQC is that the evolution of the state of the system is modeled as the movement of a one-dimensional classical random walk; the walker plays the role of the motion of the gas particles in an ordinary evaporative cooling. The implementation of this method is analogous to the setting of Maxwell's demon, where the experimentalist can monitor the heat-up or cool-down of the system, and apply feedback control to the resulting states. Here we cover the results of the connection of AQC with quantum non-demolition measurement, a scaling analysis of AQC, and the application of amplitude amplification to achieve quantum speedup. Experimental realization of AQC can be accomplished with currently available technologies.   

Progress on exploring practical applications of quantum annealing and D-Wave One

A D-Wave One quantum optimizer is currently being installed at the newly created USC-Lockheed Martin Quantum Computing Center. This chip implements quantum annealing at finite temperature as a computational resource, with 90 working qubits. Quantum annealing is a particularly simple branch of adiabatic quantum computation. We report work in progress on exploring practical applications of quantum annealing in general, and this chip in particular. Some of this work is done in collaboration with Aspuru-Guzik's group at Harvard.   

Adiabatic Quantum Anomaly Detection and Machine Learning

We present methods of anomaly detection and machine learning using adiabatic quantum computing. The machine learning algorithm is a boosting approach which seeks to optimally combine somewhat accurate classification functions to create a unified classifier which is much more accurate than its components. This algorithm then becomes the first part of the larger anomaly detection algorithm. In the anomaly detection routine, we first use adiabatic quantum computing to train two classifiers which detect two sets, the overlap of which forms the anomaly class. We call this the learning phase. Then, in the testing phase, the two learned classification functions are combined to form the final Hamiltonian for an adiabatic quantum computation, the low energy states of which represent the anomalies in a binary vector space.   

Universal Blind Quantum Computation

Blind Quantum Computing (BQC) allows a client to have a server carry out a quantum computation for them such that the client's inputs, outputs and computation remain private. Recently we proposed a universal unconditionally secure BQC scheme, based on the conceptual framework of the measurement-based quantum computing model, where the client only needs to be able to prepare single qubits in separable states randomly chosen from a finite set and send them to the server, who has the balance of the required quantum computational resources. Here we present a refinement of the scheme which vastly expands the class of quantum circuits which can be directly implemented as a blind computation, by introducing a new class of resource states which we term {\em dotted-complete graph states} and expanding the set of single qubit states the client is required to prepare. These two modifications significantly simplify the overall protocol and remove the previously present restriction that only nearest-neighbor circuits could be implemented as blind computations directly. As an added benefit, the refined protocol admits a substantially more intuitive and simplified verification mechanism, allowing the correctness of a blind computation to be verified with arbitrarily small probability of error.   

Experimental demonstration of blind quantum computing

Quantum computers are among the most promising applications of quantum-enhanced technologies. Quantum effects such as superposition and entanglement enable computational speed-ups that are unattainable using classical computers. The challenges in realising quantum computers suggest that in the near future, only a few facilities worldwide will be capable of operating such devices. In order to exploit these computers, users would seemingly have to give up their privacy. It was recently shown that this is not the case and that, via the universal blind quantum computation protocol, quantum mechanics provides a way to guarantee that the user's data remain private. Here, we demonstrate the first experimental version of this protocol using polarisation-entangled photonic qubits. We demonstrate various blind one- and two-qubit gate operations as well as blind versions of the Deutsch's and Grover's algorithms. When the technology to build quantum computers becomes available, this will become an important privacy-preserving feature of quantum information processing.   

Classical Ising Models Realised on Optical Lattices

We describe a simple quantum algorithm acting on a register of qubits in $d$ spatial dimensions which computes statistical properties of $d+1$ dimensional classical Ising models. The algorithm works by measuring scattering matrix elements for quantum processes and Wick rotating to provide estimates for real partition functions of classical systems. This method can be implemented in a straightforward way in ensembles of qubits, e.g. three dimensional optical lattices with only nearest neighbor Ising like interactions. By measuring noise in the estimate useful information regarding location of critical points and scaling laws can be extracted for classical Ising models, possibly with inhomogeneity. Unlike the case of quantum simulation of quantum hamiltonians, this algorithm does not require Trotter expansion of the evolution operator and thus has the advantage of being amenable to fault tolerant gate design in a straightforward manner. Through this setting it is possible to study the quantum computational complexity of the estimation of a classical partition function for a 2D Ising model with non uniform couplings and magnetic fields. We provide examples for the $2$ dimensional case.   

Initialization and Readout of Spin Chains for Quantum Information Transport

Linear chains of spins acting as quantum wires are a promising approach to achieve scalable quantum information processors. Nuclear spins in apatite crystals closely emulate a one-dimensional spin chain, thus providing an ideal test-bed for the experimental study of quantum information transport by means of Nuclear Magnetic Resonance techniques. The natural dipolar interaction among the spins can be manipulated via the available collective NMR control to simulate the Hamiltonian capable of driving quantum transport. We present control protocols for initialization and readout of $^{19}$F spin chains in Fluorapatite, even in the absence of single-spin addressability. We experimentally prepare and read out desired initial states for transport tasks, such as the simulation of single-spin excitation transport and a two-spin encoded state for quantum information transfer. Our control schemes enable experimental characterization of quantum transport in spin chains and will allow further studies of protocols for perfect fidelity transfer.   

Dynamical decoupling and quantum error suppression in adiabatic quantum computation

Adiabatic quantum information processing, like other quantum computing paradigms, is susceptible to noise which can potentially spoil a computation. This talk will address two proposed methods to utilize stabilizer codes to combat such noise: dynamical decoupling and quantum error suppression. A combination of numerical and analytical techniques will illustrate the connections between these two approaches. The talk will conclude with a discussion of the practical advantages of dynamical decoupling over quantum error suppression.   

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. Here, we determine its efficiency by considering several constraint satisfaction (SAT) problems. We do this by studying the size dependence of their typical minimum energy gap using quantum Monte Carlo methods. We find that for most problems this gap decreases exponentially with the size of the problem, indicating that the QAA is not more efficient than existing classical search algorithms. However, for one specific problem, namely, MAX-2-XORSAT, there is evidence to suggest that the gap may be polynomial near the phase transition.   

Discrete-time quantum walks on the symmetric group (quantum card shuffling)

The next stage in uses of classical stochastic approaches, going beyond Markov chains (random walks on graphs), are walks on algebraic structures. The prime and classic example of such a problem is ``card shuffling,'' a walk on the permutation (symmetric) group. The richness of this non-Abelian group lends itself to modeling of complex phenomena, while it also quickly leads to rather complicated problems. The challenge of studying such quantum processes is no lesser, but the benefits can be expected to even outweigh the classical uses. We study a quantum analog of the classical ``top-to-random'' shuffle, where the top card is placed at random in the deck. We construct a ``coined'' DTQW on the permutation group: based on the action of a (unitary) ``coin'' operator in an additional (``coin'') space, (unitary) steps in the group space are taken, resulting in a (quantum) walk over group elements. We use general techniques for the eigenvalue problem of the combined coin and permutation operators, utilizing regularities in the block structure. We have reached preliminary solutions for low-dimensional cases. Currently we are integrating them into a more general solution, which will yield the first step in this deep and far-reaching, while challenging problem.