Source author record

Daniel A. Lidar

Daniel A. Lidar appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

quant-ph physics.chem-ph cond-mat.other math-ph math.MP cond-mat cond-mat.stat-mech cond-mat.mes-hall cond-mat.mtrl-sci cond-mat.str-el adap-org cond-mat.dis-nn cond-mat.supr-con Machine Learning math.CO math.OC nlin.AO physics.comp-ph physics.soc-ph

Catalog footprint

What is connected

81works

19topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers

With current semiconductor technology reaching its physical limits, special-purpose hardware has emerged as an option to tackle specific computing-intensive challenges. Optimization in the form of solving Quadratic Unconstrained Binary Optimization (QUBO) problems, or equivalently Ising spin glasses, has been the focus of several new dedicated hardware platforms. These platforms come in many different flavors, from highly-efficient hardware implementations on digital-logic of established algorithms to proposals of analog hardware implementing new algorithms. In this work, we use a mapping of a specific class of linear equations whose solutions can be found efficiently, to a hard constraint satisfaction problem (3-regular 3-XORSAT, or an Ising spin glass) with a 'golf-course' shaped energy landscape, to benchmark several of these different approaches. We perform a scaling and prefactor analysis of the performance of Fujitsu's Digital Annealer Unit (DAU), the D-Wave Advantage quantum annealer, a Virtual MemComputing Machine, Toshiba's Simulated Bifurcation Machine (SBM), the SATonGPU algorithm from Bernaschi et al., and our implementation of parallel tempering. We identify the SATonGPU and DAU as currently having the smallest scaling exponent for this benchmark, with SATonGPU having a small scaling advantage and in addition having by far the smallest prefactor thanks to its use of massive parallelism. Our work provides an objective assessment and a snapshot of the promise and limitations of dedicated optimization hardware relative to a particular class of optimization problems.

preprint2022arXiv

Breakdown of the weak coupling limit in quantum annealing

Reverse annealing is a variant of quantum annealing, in which the system is prepared in a classical state, reverse-annealed to an inversion point, and then forward-annealed. We report on reverse annealing experiments using the D-Wave 2000Q device, with a focus on the $p=2$ $p$-spin problem, which undergoes a second order quantum phase transition with a gap that closes polynomially in the number of spins. We concentrate on the total and partial success probabilities, the latter being the probabilities of finding each of two degenerate ground states of all spins up or all spins down, the former being their sum. The empirical partial success probabilities exhibit a strong asymmetry between the two degenerate ground states, depending on the initial state of the reverse anneal. To explain these results, we perform open-system simulations using master equations in the limits of weak and strong coupling to the bath. The former, known as the adiabatic master equation (AME), with decoherence in the instantaneous energy eigenbasis, predicts perfect symmetry between the two degenerate ground states, thus failing to agree with the experiment. In contrast, the latter, known as the polaron transformed Redfield equation (PTRE), is in close agreement with experiment. Thus our results present a challenge to the sufficiency of the weak system-bath coupling limit in describing the dynamics of current experimental quantum annealers, at least for reverse annealing on timescales of a microsecond or longer.

preprint2022arXiv

Customized quantum annealing schedules

In a typical quantum annealing protocol, the system starts with a transverse field Hamiltonian which is gradually turned off and replaced by a longitudinal Ising Hamiltonian. The ground state of the Ising Hamiltonian encodes the solution to the computational problem of interest, and the state overlap with this ground state gives the success probability of the annealing protocol. The form of the annealing schedule can have a significant impact on the ground state overlap at the end of the anneal, so precise control over these annealing schedules can be a powerful tool for increasing success probabilities of annealing protocols. Here we show how superconducting circuits, in particular capacitively shunted flux qubits (CSFQs), can be used to construct quantum annealing systems by providing tools for mapping circuit flux biases to Pauli coefficients. We use this mapping to find customized annealing schedules: appropriate circuit control biases that yield a desired annealing schedule, while accounting for the physical limitations of the circuitry. We then provide examples and proposals that utilize this capability to improve quantum annealing performance.

preprint2022arXiv

HOQST: Hamiltonian Open Quantum System Toolkit

We present an open-source software package called "Hamiltonian Open Quantum System Toolkit" (HOQST), a collection of tools for the investigation of open quantum system dynamics in Hamiltonian quantum computing, including both quantum annealing and the gate-model of quantum computing. It features the key master equations (MEs) used in the field, suitable for describing the reduced system dynamics of an arbitrary time-dependent Hamiltonian with either weak or strong coupling to infinite-dimensional quantum baths. This includes the Redfield ME, the polaron-transformed Redfield ME, the adiabatic ME, the coarse-grained ME, and the universal Lindblad ME. HOQST also includes the stochastic Schrodinger equation with spin-fluctuators. We present an overview of the theories behind the various MEs and provide examples to illustrate typical workflows in HOQST. We present an example that shows that HOQST can provide order of magnitude speedups compared to QuTiP, for problems with time-dependent Hamiltonians. The package is ready to be deployed on high-performance computing (HPC) clusters and is aimed at providing reliable open-system analysis tools for noisy intermediate-scale quantum (NISQ) devices. The HOQST Github repository (https://github.com/USCqserver/OpenQuantumTools.jl) provides the starting point for users. Detailed information can be found in the README file.

preprint2022arXiv

Standard quantum annealing outperforms adiabatic reverse annealing with decoherence

We study adiabatic reverse annealing (ARA) in an open system. In the closed system (unitary) setting, this annealing protocol allows avoidance of first-order quantum phase transitions of selected models, resulting in an exponential speedup compared with standard quantum annealing, provided that the initial state of the algorithm is close in Hamming distance to the target one. Here, we show that decoherence can significantly modify this conclusion: by resorting to the adiabatic master equation approach, we simulate the dynamics of the ferromagnetic $p$-spin model with $p=3$ under independent and collective dephasing. For both models of decoherence, we show that the performance of open system ARA is far less sensitive to the choice of the initial state than its unitary counterpart, and, most significantly, that open system ARA by and large loses its time to solution advantage compared to standard quantum annealing. These results suggest that as a stand-alone strategy, ARA is unlikely to experimentally outperform standard "forward" quantum annealing, and that error mitigation strategies will likely be required in order to realize the benefits of ARA in realistic, noisy settings.

preprint2021arXiv

Anneal-path correction in flux qubits

Quantum annealers require accurate control and optimized operation schemes to reduce noise levels, in order to eventually demonstrate a computational advantage over classical algorithms. We study a high coherence four-junction capacitively shunted flux qubit (CSFQ), using dispersive measurements to extract system parameters and model the device. Josephson junction asymmetry inherent to the device causes a deleterious nonlinear cross-talk when annealing the qubit. We implement a nonlinear annealing path to correct the asymmetry in-situ, resulting in a substantial increase in the probability of the qubit being in the correct state given an applied flux bias. We also confirm the multi-level structure of our CSFQ circuit model by annealing it through small spectral gaps and observing quantum signatures of energy level crossings. Our results demonstrate an anneal-path correction scheme designed and implemented to improve control accuracy for high-coherence and high-control quantum annealers, which leads to an enhancement of success probability in annealing protocols.

preprint2021arXiv

Demonstration of long-range correlations via susceptibility measurements in a one-dimensional superconducting Josephson spin chain

Spin chains have long been considered an effective medium for long-range interactions, entanglement generation, and quantum state transfer. In this work, we explore the properties of a spin chain implemented with superconducting flux circuits, designed to act as a connectivity medium between two superconducting qubits. The susceptibility of the chain is probed and shown to support long-range, cross chain correlations. In addition, interactions between the two end qubits, mediated by the coupler chain, are demonstrated. This work has direct applicability in near term quantum annealing processors as a means of generating long-range, coherent coupling between qubits.

preprint2020arXiv

Improved Boltzmann machines with error corrected quantum annealing

Boltzmann machines are the basis of several deep learning methods that have been successfully applied to both supervised and unsupervised machine learning tasks. These models assume that a dataset is generated according to a Boltzmann distribution, and the goal of the training procedure is to learn the set of parameters that most closely match the input data distribution. Training such models is difficult due to the intractability of traditional sampling techniques, and proposals using quantum annealers for sampling hope to mitigate the sampling cost. However, real physical devices will inevitably be coupled to the environment, and the strength of this coupling affects the effective temperature of the distributions from which a quantum annealer samples. To counteract this problem, error correction schemes that can effectively reduce the temperature are needed if there is to be some benefit in using quantum annealing for problems at a larger scale, where we might expect the effective temperature of the device to not be sufficiently low. To this end, we have applied nested quantum annealing correction (NQAC) to do unsupervised learning with a small bars and stripes dataset, and to do supervised learning with a coarse-grained MNIST dataset. For both datasets we demonstrate improved training and a concomitant effective temperature reduction at higher noise levels relative to the unencoded case. We also find better performance overall with longer anneal times and offer an interpretation of the results based on a comparison to simulated quantum annealing and spin vector Monte Carlo. A counterintuitive aspect of our results is that the output distribution generally becomes less Gibbs-like with increasing nesting level and increasing anneal times, which shows that improved training performance can be achieved without equilibration to the target Gibbs distribution.

preprint2020arXiv

Lecture Notes on the Theory of Open Quantum Systems

This is a self-contained set of lecture notes covering various aspects of the theory of open quantum system, at a level appropriate for a one-semester graduate course. The main emphasis is on completely positive maps and master equations, both Markovian and non-Markovian.

preprint2020arXiv

Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond

The number of topological defects created in a system driven through a quantum phase transition exhibits a power-law scaling with the driving time. This universal scaling law is the key prediction of the Kibble-Zurek mechanism (KZM), and testing it using a hardware-based quantum simulator is a coveted goal of quantum information science. Here we provide such a test using quantum annealing. Specifically, we report on extensive experimental tests of topological defect formation via the one-dimensional transverse-field Ising model on two different D-Wave quantum annealing devices. We find that the quantum simulator results can indeed be explained by the KZM for open-system quantum dynamics with phase-flip errors, with certain quantitative deviations from the theory likely caused by factors such as random control errors and transient effects. In addition, we probe physics beyond the KZM by identifying signatures of universality in the distribution and cumulants of the number of kinks and their decay, and again find agreement with the quantum simulator results. This implies that the theoretical predictions of the generalized KZM theory, which assumes isolation from the environment, applies beyond its original scope to an open system. We support this result by extensive numerical computations. To check whether an alternative, classical interpretation of these results is possible, we used the spin-vector Monte Carlo model, a candidate classical description of the D-Wave device. We find that the degree of agreement with the experimental data from the D-Wave annealing devices is better for the KZM, a quantum theory, than for the classical spin-vector Monte Carlo model, thus favoring a quantum description of the device. Our work provides an experimental test of quantum critical dynamics in an open quantum system, and paves the way to new directions in quantum simulation experiments.

preprint2020arXiv

Why and when is pausing beneficial in quantum annealing?

Recent empirical results using quantum annealing hardware have shown that mid anneal pausing has a surprisingly beneficial impact on the probability of finding the ground state for of a variety of problems. A theoretical explanation of this phenomenon has thus far been lacking. Here we provide an analysis of pausing using a master equation framework, and derive conditions for the strategy to result in a success probability enhancement. The conditions, which we identify through numerical simulations and then prove to be sufficient, require that relative to the pause duration the relaxation rate is large and decreasing right after crossing the minimum gap, small and decreasing at the end of the anneal, and is also cumulatively small over this interval, in the sense that the system does not thermally equilibrate. This establishes that the observed success probability enhancement can be attributed to incomplete quantum relaxation, i.e., is a form of beneficial non-equilibrium coupling to the environment.

preprint2019arXiv

Reverse quantum annealing of the $p$-spin model with relaxation

In reverse quantum annealing, the initial state is an eigenstate of the final problem Hamiltonian and the transverse field is cycled rather than strictly decreased as in standard (forward) quantum annealing. We present a numerical study of the reverse quantum annealing protocol applied to the $p$-spin model ($p=3$), including pausing, in an open system setting accounting for dephasing in the energy eigenbasis, which results in thermal relaxation. We consider both independent and collective dephasing and demonstrate that in both cases the open system dynamics substantially enhances the performance of reverse annealing. Namely, including dephasing overcomes the failure of purely closed system reverse annealing to converge to the ground state of the $p$-spin model. We demonstrate that pausing further improves the success probability. The collective dephasing model leads to somewhat better performance than independent dephasing. The protocol we consider corresponds closely to the one implemented in the current generation of commercial quantum annealers, and our results help to explain why recent experiments demonstrated enhanced success probabilities under reverse annealing and pausing.

preprint2016arXiv

Adiabaticity in open quantum systems

We provide a rigorous generalization of the quantum adiabatic theorem for open systems described by a Markovian master equation with time-dependent Liouvillian $\mathcal{L}(t)$. We focus on the finite system case relevant for adiabatic quantum computing and quantum annealing. Adiabaticity is defined in terms of closeness to the instantaneous steady state. While the general result is conceptually similar to the closed system case, there are important differences. Namely, a system initialized in the zero-eigenvalue eigenspace of $\mathcal{L}(t)$ will remain in this eigenspace with a deviation that is inversely proportional to the total evolution time $T$. In the case of a finite number of level crossings the scaling becomes $T^{-η}$ with an exponent $η$ that we relate to the rate of the gap closing. For master equations that describe relaxation to thermal equilibrium, we show that the evolution time $T$ should be long compared to the corresponding minimum inverse gap squared of $\mathcal{L}(t)$. Our results are illustrated with several examples.

preprint2016arXiv

Eigenstate Tracking in Open Quantum Systems

Keeping a quantum system in a given instantaneous eigenstate is a control problem with numerous applications, e.g., in quantum information processing. The problem is even more challenging in the setting of open quantum systems, where environment-mediated transitions introduce additional decoherence channels. Adiabatic passage is a well established solution, but requires a sufficiently slow evolution time that is dictated by the adiabatic theorem. Here we develop a systematic projection theory formulation for the transitionless evolution of general open quantum systems described by time-local master equations. We derive a time-convolutionless dynamical equation for the target instantaneous eigenstate of a given time-dependent Hamiltonian. A transitionless dynamics then arises in terms of a competition between the average Hamiltonian gap and the decoherence rate, which implies optimal adiabaticity timescales. We show how eigenstate tracking can be accomplished via control pulses, without explicitly incorporating counter-diabatic driving, thus offering an alternative route to shortcuts to adiabaticity. We examine rectangular pulses, chaotic signals, and white noise, and find that, remarkably, the effectiveness of eigenstate tracking hardly depends on the details of the control functions. In all cases the control protocol keeps the system in the desired instantaneous eigenstate throughout the entire evolution, along an accelerated adiabatic path.

preprint2016arXiv

Mean Field Analysis of Quantum Annealing Correction

Quantum annealing correction (QAC) is a method that combines encoding with energy penalties and decoding to suppress and correct errors that degrade the performance of quantum annealers in solving optimization problems. While QAC has been experimentally demonstrated to successfully error-correct a range of optimization problems, a clear understanding of its operating mechanism has been lacking. Here we bridge this gap using tools from quantum statistical mechanics. We study analytically tractable models using a mean-field analysis, specifically the $p$-body ferromagnetic infinite-range transverse-field Ising model as well as the quantum Hopfield model. We demonstrate that for $p=2$, where the phase transition is of second order, QAC pushes the transition to increasingly larger transverse field strengths. For $p\ge3$, where the phase transition is of first order, QAC softens the closing of the gap for small energy penalty values and prevents its closure for sufficiently large energy penalty values. Thus QAC provides protection from excitations that occur near the quantum critical point. We find similar results for the Hopfield model, thus demonstrating that our conclusions hold in the presence of disorder.

preprint2016arXiv

Optimally Stopped Optimization

We combine the fields of heuristic optimization and optimal stopping. We propose a strategy for benchmarking randomized optimization algorithms that minimizes the expected total cost for obtaining a good solution with an optimal number of calls to the solver. To do so, rather than letting the objective function alone define a cost to be minimized, we introduce a further cost-per-call of the algorithm. We show that this problem can be formulated using optimal stopping theory. The expected cost is a flexible figure of merit for benchmarking probabilistic solvers that can be computed when the optimal solution is not known, and that avoids the biases and arbitrariness that affect other measures. The optimal stopping formulation of benchmarking directly leads to a real-time, optimal-utilization strategy for probabilistic optimizers with practical impact. We apply our formulation to benchmark simulated annealing on a class of MAX2SAT problems. We also compare the performance of a D-Wave 2X quantum annealer to the HFS solver, a specialized classical heuristic algorithm designed for low tree-width graphs. On a set of frustrated-loop instances with planted solutions defined on up to N = 1098 variables, the D-Wave device is two orders of magnitude faster than the HFS solver, and, modulo known caveats related to suboptimal annealing times, exhibits identical scaling with problem size.

preprint2016arXiv

Simulated Quantum Annealing with Two All-to-All Connectivity Schemes

Quantum annealing aims to exploit quantum mechanics to speed up the search for the solution to optimization problems. Most problems exhibit complete connectivity between the logical spin variables after they are mapped to the Ising spin Hamiltonian of quantum annealing. To account for hardware constraints of current and future physical quantum annealers, methods enabling the embedding of fully connected graphs of logical spins into a constant-degree graph of physical spins are therefore essential. Here, we compare the recently proposed embedding scheme for quantum annealing with all-to-all connectivity due to Lechner, Hauke and Zoller (LHZ) [Science Advances 1 (2015)] to the commonly used minor embedding (ME) scheme. Using both simulated quantum annealing and parallel tempering simulations, we find that for a set of instances randomly chosen from a class of fully connected, random Ising problems, the ME scheme outperforms the LHZ scheme when using identical simulation parameters, despite the fault tolerance of the latter to weakly correlated spin-flip noise. This result persists even after we introduce several decoding strategies for the LHZ scheme, including a minimum-weight decoding algorithm that results in substantially improved performance over the original LHZ scheme. We explain the better performance of the ME scheme in terms of more efficient spin updates, which allows it to better tolerate the correlated spin-flip errors that arise in our model of quantum annealing. Our results leave open the question of whether the performance of the two embedding schemes can be improved using scheme-specific parameters and new error correction approaches.

preprint2015arXiv

A general framework for complete positivity

Complete positivity of quantum dynamics is often viewed as a litmus test for physicality, yet it is well known that correlated initial states need not give rise to completely positive evolutions. This observation spurred numerous investigations over the past two decades attempting to identify necessary and sufficient conditions for complete positivity. Here we describe a complete and consistent mathematical framework for the discussion and analysis of complete positivity for correlated initial states of open quantum systems. This formalism is built upon a few simple axioms and is sufficiently general to contain all prior methodologies going back to Pechakas, PRL (1994). The key observation is that initial system-bath states with the same reduced state on the system must evolve under all admissible unitary operators to system-bath states with the same reduced state on the system, in order to ensure that the induced dynamical maps on the system are well-defined. Once this consistency condition is imposed, related concepts like the assignment map and the dynamical maps are uniquely defined. In general, the dynamical maps may not be applied to arbitrary system states, but only to those in an appropriately defined physical domain. We show that the constrained nature of the problem gives rise to not one but three inequivalent types of complete positivity. Using this framework we elucidate the limitations of recent attempts to provide conditions for complete positivity using quantum discord and the quantum data-processing inequality. The problem remains open, and may require fresh perspectives and new mathematical tools. The formalism presented herein may be one step in that direction.

preprint2015arXiv

Beyond Complete Positivity

We provide a general and consistent formulation for linear subsystem quantum dynamical maps, developed from a minimal set of postulates, primary among which is a relaxation of the usual, restrictive assumption of uncorrelated initial system-bath states. We describe the space of possibilities admitted by this formulation, namely that, far from being limited to only completely positive (CP) maps, essentially any $\mathbb{C}$-linear, Hermiticity-preserving, trace-preserving subsystem map can arise as a legitimate subsystem dynamical map from a joint unitary evolution of a system coupled to a bath. The price paid for this added generality is a trade-off between the set of admissible initial states and the allowed set of joint system-bath unitary evolutions. As an application we present a simple example of a non-CP map constructed as a subsystem dynamical map that violates some fundamental inequalities in quantum information theory, such as the quantum data processing inequality.

preprint2015arXiv

Consistency Tests of Classical and Quantum Models for a Quantum Annealer

Recently the question of whether the D-Wave processors exhibit large-scale quantum behavior or can be described by a classical model has attracted significant interest. In this work we address this question by studying a 503 qubit D-Wave Two device in the "black box" model, i.e., by studying its input-output behavior. Our work generalizes an approach introduced in Boixo et al. [Nat. Commun. 4, 2067 (2013)], and uses groups of up to 20 qubits to realize a transverse Ising model evolution with a ground state degeneracy whose distribution acts as a sensitive probe that distinguishes classical and quantum models for the D-Wave device. Our findings rule out all classical models proposed to date for the device and provide evidence that an open system quantum dynamical description of the device that starts from a quantized energy level structure is well justified, even in the presence of relevant thermal excitations and a small value of the ratio of the single-qubit decoherence time to the annealing time.

preprint2015arXiv

Decoherence in adiabatic quantum computation

Recent experiments with increasingly larger numbers of qubits have sparked renewed interest in adiabatic quantum computation, and in particular quantum annealing. A central question that is repeatedly asked is whether quantum features of the evolution can survive over the long time-scales used for quantum annealing relative to standard measures of the decoherence time. We reconsider the role of decoherence in adiabatic quantum computation and quantum annealing using the adiabatic quantum master equation formalism. We restrict ourselves to the weak-coupling and singular-coupling limits, which correspond to decoherence in the energy eigenbasis and in the computational basis, respectively. We demonstrate that decoherence in the instantaneous energy eigenbasis does not necessarily detrimentally affect adiabatic quantum computation, and in particular that a short single-qubit $T_2$ time need not imply adverse consequences for the success of the quantum adiabatic algorithm. We further demonstrate that boundary cancellation methods, designed to improve the fidelity of adiabatic quantum computing in the closed system setting, remain beneficial in the open system setting. To address the high computational cost of master equation simulations, we also demonstrate that a quantum Monte Carlo algorithm that explicitly accounts for a thermal bosonic bath can be used to interpolate between classical and quantum annealing. Our study highlights and clarifies the significantly different role played by decoherence in the adiabatic and circuit models of quantum computing.

preprint2015arXiv

Nested Quantum Annealing Correction

We present a general error-correcting scheme for quantum annealing that allows for the encoding of a logical qubit into an arbitrarily large number of physical qubits. Given any Ising model optimization problem, the encoding replaces each logical qubit by a complete graph of degree $C$, representing the distance of the error-correcting code. A subsequent minor-embedding step then implements the encoding on the underlying hardware graph of the quantum annealer. We demonstrate experimentally that the performance of a D-Wave Two quantum annealing device improves as $C$ grows. We show that the performance improvement can be interpreted as arising from an effective increase in the energy scale of the problem Hamiltonian, or equivalently, an effective reduction in the temperature at which the device operates. The number $C$ thus allows us to control the amount of protection against thermal and control errors, and in particular, to trade qubits for a lower effective temperature that scales as $C^{-η}$, with $η\leq 2$. This effective temperature reduction is an important step towards scalable quantum annealing.

preprint2015arXiv

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 (secular) approximation that results in a master equation in Lindblad form, the other without the rotating wave approximation but not in Lindblad form. The two equations make markedly different predictions depending on whether or not the Lamb shift is included. Our analysis keeps track of the various time- and energy-scales associated with the various approximations we make, and thus allows for a systematic inclusion of higher order corrections, in particular beyond the adiabatic limit. We use our formalism to study the evolution of an Ising spin chain in a transverse field and coupled to a thermal bosonic bath, for which we identify four distinct evolution phases. While we do not expect this to be a generic feature, in one of these phases dissipation acts to increase the fidelity of the system state relative to the adiabatic ground state.

preprint2015arXiv

Quantum annealing correction for random Ising problems

We demonstrate that the performance of a quantum annealer on hard random Ising optimization problems can be substantially improved using quantum annealing correction (QAC). Our error correction strategy is tailored to the D-Wave Two device. We find that QAC provides a statistically significant enhancement in the performance of the device over a classical repetition code, improving as a function of problem size as well as hardness. Moreover, QAC provides a mechanism for overcoming the precision limit of the device, in addition to correcting calibration errors. Performance is robust even to missing qubits. We present evidence for a constructive role played by quantum effects in our experiments by contrasting the experimental results with the predictions of a classical model of the device. Our work demonstrates the importance of error correction in appropriately determining the performance of quantum annealers.

preprint2015arXiv

Quantum Annealing Correction with Minor Embedding

Quantum annealing provides a promising route for the development of quantum optimization devices, but the usefulness of such devices will be limited in part by the range of implementable problems as dictated by hardware constraints. To overcome constraints imposed by restricted connectivity between qubits, a larger set of interactions can be approximated using minor embedding techniques whereby several physical qubits are used to represent a single logical qubit. However, minor embedding introduces new types of errors due to its approximate nature. We introduce and study quantum annealing correction schemes designed to improve the performance of quantum annealers in conjunction with minor embedding, thus leading to a hybrid scheme defined over an encoded graph. We argue that this scheme can be efficiently decoded using an energy minimization technique provided the density of errors does not exceed the per-site percolation threshold of the encoded graph. We test the hybrid scheme using a D-Wave Two processor on problems for which the encoded graph is a 2-level grid and the Ising model is known to be NP-hard. The problems we consider are frustrated Ising model problem instances with "planted" (a priori known) solutions. Applied in conjunction with optimized energy penalties and decoding techniques, we find that this approach enables the quantum annealer to solve minor embedded instances with significantly higher success probability than it would without error correction. Our work demonstrates that quantum annealing correction can and should be used to improve the robustness of quantum annealing not only for natively embeddable problems, but also when minor embedding is used to extend the connectivity of physical devices.

preprint2015arXiv

Quantum speed limits for leakage and decoherence

We introduce state-independent, non-perturbative Hamiltonian quantum speed limits for population leakage and fidelity loss, for a gapped open system interacting with a reservoir. These results hold in the presence of initial correlations between the system and the reservoir, under the sole assumption that their interaction and its commutator with the reservoir Hamiltonian are norm-bounded. The reservoir need not be thermal and can be time-dependent. We study the significance of energy mismatch between the system and the local degrees of freedom of the reservoir which directly interact with the system. We demonstrate that, in general, by increasing the system gap we may reduce this energy mismatch, and consequently drive the system and the reservoir into resonance, which can accelerate fidelity loss, irrespective of the thermal properties or state of the reservoir. This implies that quantum error suppression strategies based on increasing the gap are not uniformly beneficial. Our speed limits also yield an elementary lower bound on the relaxation time of spin systems.

preprint2015arXiv

Reexamination of the evidence for entanglement in the D-Wave processor

A recent experiment [Lanting et al., PRX, (2014)] claimed to provide evidence of up to $8$-qubit entanglement in a D-Wave quantum annealing device. However, entanglement was measured using qubit tunneling spectroscopy, a technique that provides indirect access to the state of the system at intermediate times during the anneal by performing measurements at the end of the anneal with a probe qubit. In addition, an underlying assumption was that the quantum transverse-field Ising Hamiltonian, whose ground states are already highly entangled, is an appropriate model of the device, and not some other (possibly classical) model. This begs the question of whether alternative, classical or semiclassical models would be equally effective at predicting the observed spectrum and thermal state populations. To check this, we consider a recently proposed classical rotor model with classical Monte Carlo updates, which has been successfully employed in describing features of earlier experiments involving the device. We also consider simulated quantum annealing with quantum Monte Carlo updates, an algorithm that samples from the instantaneous Gibbs state of the device Hamiltonian. Finally, we use the quantum adiabatic master equation, which cannot be efficiently simulated classically, and which has previously been used to successfully capture the open system quantum dynamics of the device. We find that only the master equation is able to reproduce the features of the tunneling spectroscopy experiment, while both the classical rotor model and simulated quantum annealing fail to reproduce the experimental results. We argue that this bolsters the evidence for the reported entanglement.

preprint2015arXiv

Tunneling and speedup in quantum optimization for permutation-symmetric problems

Tunneling is often claimed to be the key mechanism underlying possible speedups in quantum optimization via quantum annealing (QA), especially for problems featuring a cost function with tall and thin barriers. We present and analyze several counterexamples from the class of perturbed Hamming-weight optimization problems with qubit permutation symmetry. We first show that, for these problems, the adiabatic dynamics that make tunneling possible should be understood not in terms of the cost function but rather the semi-classical potential arising from the spin-coherent path integral formalism. We then provide an example where the shape of the barrier in the final cost function is short and wide, which might suggest no quantum advantage for QA, yet where tunneling renders QA superior to simulated annealing in the adiabatic regime. However, the adiabatic dynamics turn out not be optimal. Instead, an evolution involving a sequence of diabatic transitions through many avoided level-crossings, involving no tunneling, is optimal and outperforms adiabatic QA. We show that this phenomenon of speedup by diabatic transitions is not unique to this example, and we provide an example where it provides an exponential speedup over adiabatic QA. In yet another twist, we show that a classical algorithm, spin vector dynamics, is at least as efficient as diabatic QA. Finally, in a different example with a convex cost function, the diabatic transitions result in a speedup relative to both adiabatic QA with tunneling and classical spin vector dynamics.

preprint2015arXiv

When Diabatic Trumps Adiabatic in Quantum Optimization

We provide and analyze examples that counter the widely made claim that tunneling is needed for a quantum speedup in optimization problems. The examples belong to the class of perturbed Hamming-weight optimization problems. In one case, featuring a plateau in the cost function in Hamming weight space, we find that the adiabatic dynamics that make tunneling possible, while superior to simulated annealing, result in a slowdown compared to a diabatic cascade of avoided level-crossings. This, in turn, inspires a classical spin vector dynamics algorithm that is at least as efficient for the plateau problem as the diabatic quantum algorithm. In a second case whose cost function is convex in Hamming weight space, the diabatic cascade results in a speedup relative to both tunneling and classical spin vector dynamics.

preprint2014arXiv

Defining and detecting quantum speedup

The development of small-scale digital and analog quantum devices raises the question of how to fairly assess and compare the computational power of classical and quantum devices, and of how to detect quantum speedup. Here we show how to define and measure quantum speedup in various scenarios, and how to avoid pitfalls that might mask or fake quantum speedup. We illustrate our discussion with data from a randomized benchmark test on a D-Wave Two device with up to 503 qubits. Comparing the performance of the device on random spin glass instances with limited precision to simulated classical and quantum annealers, we find no evidence of quantum speedup when the entire data set is considered, and obtain inconclusive results when comparing subsets of instances on an instance-by-instance basis. Our results for one particular benchmark do not rule out the possibility of speedup for other classes of problems and illustrate that quantum speedup is elusive and can depend on the question posed.

preprint2014arXiv

Quantum error suppression with commuting Hamiltonians: Two-local is too local

We consider error suppression schemes in which quantum information is encoded into the ground subspace of a Hamiltonian comprising a sum of commuting terms. Since such Hamiltonians are gapped they are considered natural candidates for protection of quantum information and topological or adiabatic quantum computation. However, we prove that they cannot be used to this end in the 2-local case. By making the favorable assumption that the gap is infinite we show that single-site perturbations can generate a degeneracy splitting in the ground subspace of this type of Hamiltonians which is of the same order as the magnitude of the perturbation, and is independent of the number of interacting sites and their Hilbert space dimensions, just as in the absence of the protecting Hamiltonian. This splitting results in decoherence of the ground subspace, and we demonstrate that for natural noise models the coherence time is proportional to the inverse of the degeneracy splitting. Our proof involves a new version of the no-hiding theorem which shows that quantum information cannot be approximately hidden in the correlations between two quantum systems, and should be of independent interest. The main reason that 2-local commuting Hamiltonians cannot be used for quantum error suppression is that their ground subspaces have only short-range (two-body) entanglement.

preprint2014arXiv

Reexamining classical and quantum models for the D-Wave One processor

We revisit the evidence for quantum annealing in the D-Wave One device (DW1) based on the study of random Ising instances. Using the probability distributions of finding the ground states of such instances, previous work found agreement with both simulated quantum annealing (SQA) and a classical rotor model. Thus the DW1 ground state success probabilities are consistent with both models, and a different measure is needed to distinguish the data and the models. Here we consider measures that account for ground state degeneracy and the distributions of excited states, and present evidence that for these new measures neither SQA nor the classical rotor model correlate perfectly with the DW1 experiments. We thus provide evidence that SQA and the classical rotor model, both of which are classically efficient algorithms, do not satisfactorily explain all the DW1 data. A complete model for the DW1 remains an open problem. Using the same criteria we find that, on the other hand, SQA and the classical rotor model correlate closely with each other. To explain this we show that the rotor model can be derived as the semiclassical limit of the spin-coherent states path integral. We also find differences in which set of ground states is found by each method, though this feature is sensitive to calibration errors of the DW1 device and to simulation parameters.

preprint2013arXiv

Adiabatic quantum optimization with the wrong Hamiltonian

Analog models of quantum information processing, such as adiabatic quantum computation and analog quantum simulation, require the ability to subject a system to precisely specified Hamiltonians. Unfortunately, the hardware used to implement these Hamiltonians will be imperfect and limited in its precision. Even small perturbations and imprecisions can have profound effects on the nature of the ground state. Here we consider an imperfect implementation of adiabatic quantum optimization and show that, for a widely applicable random control noise model, quantum stabilizer encodings are able to reduce the effective noise magnitude and thus improve the likelihood of a successful computation or simulation. This reduction builds upon two design principles: summation of equivalent logical operators to increase the energy scale of the encoded optimization problem, and the inclusion of a penalty term comprising the sum of the code stabilizer elements. We illustrate our findings with an Ising ladder and show that classical repetition coding drastically increases the probability that the ground state of a perturbed model is decodable to that of the unperturbed model, while using only realistic two-body interaction. Finally, we note that the repetition encoding is a special case of quantum stabilizer encodings, and show that this in principle allows us to generalize our results to many types of analog quantum information processing, albeit at the expense of many-body interactions.

preprint2013arXiv

Coarse-Graining Can Beat the Rotating Wave Approximation in Quantum Markovian Master Equations

We present a first-principles derivation of the Markovian semi-group master equation without invoking the rotating wave approximation (RWA). Instead we use a time coarse-graining approach which leaves us with a free timescale parameter, which we can optimize. Comparing this approach to the standard RWA-based Markovian master equation, we find that significantly better agreement is possible using the coarse-graining approach, for a three-level model coupled to a bath of oscillators, whose exact dynamics we can solve for at zero temperature. The model has the important feature that the RWA has a non-trivial effect on the dynamics of the populations. We show that the two different master equations can exhibit strong qualitative differences for the population of the energy eigenstates even for such a simple model. The RWA-based master equation misses an important feature which the coarse-graining based scheme does not. By optimizing the coarse-graining timescale the latter scheme can be made to approach the exact solution much more closely than the RWA-based master equation.

preprint2013arXiv

Comment on: "Classical signature of quantum annealing"

In a recent preprint (arXiv:1305.4904) entitled "Classical signature of quantum annealing" Smolin and Smith point out that a bimodal distribution presented in (arXiv:1304.4595) for the success probability in the D-Wave device does not in itself provide sufficient evidence for quantum annealing, by presenting a classical model that also exhibits bimodality. Here we analyze their model and in addition present a similar model derived from the semi-classical limit of quantum spin dynamics, which also exhibits a bimodal distribution. We find that in both cases the correlations between the success probabilities of these classical models and the D-Wave device are weak compared to the correlations between a simulated quantum annealer and the D-Wave device. Indeed, the evidence for quantum annealing presented in arXiv:1304.4595 is not limited to the bimodality, but relies in addition on the success probability correlations between the D-Wave device and the simulated quantum annealer. The Smolin-Smith model and our semi-classical spin model both fail this correlation test.

preprint2013arXiv

Error corrected quantum annealing with hundreds of qubits

Quantum information processing offers dramatic speedups, yet is famously susceptible to decoherence, the process whereby quantum superpositions decay into mutually exclusive classical alternatives, thus robbing quantum computers of their power. This has made the development of quantum error correction an essential and inescapable aspect of both theoretical and experimental quantum computing. So far little is known about protection against decoherence in the context of quantum annealing, a computational paradigm which aims to exploit ground state quantum dynamics to solve optimization problems more rapidly than is possible classically. Here we develop error correction for quantum annealing and provide an experimental demonstration using up to 344 superconducting flux qubits in processors which have recently been shown to physically implement programmable quantum annealing. We demonstrate a substantial improvement over the performance of the processors in the absence of error correction. These results pave a path toward large scale noise-protected adiabatic quantum optimization devices.

preprint2013arXiv

Evolution prediction from tomography

Quantum process tomography provides a means of measuring the evolution operator for a system at a fixed measurement time $t$. The problem of using that tomographic snapshot to predict the evolution operator at other times is generally ill-posed since there are, in general, infinitely many distinct and compatible solutions. We describe the prediction, in some ``maximal ignorance'' sense, of the evolution of a quantum system based on knowledge only of the evolution operator for finitely many times $0<τ_{1}<\dots<τ_{M}$ with $M\geq 1$. To resolve the ill-posedness problem, we construct this prediction as the result of an average over some unknown (and unknowable) variables. The resulting prediction provides a description of the observer's state of knowledge of the system's evolution at times away from the measurement times. Even if the original evolution is unitary, the predicted evolution is described by a non-unitary, completely positive map.

preprint2013arXiv

Fault tolerance for holonomic quantum computation

We review an approach to fault-tolerant holonomic quantum computation on stabilizer codes. We explain its workings as based on adiabatic dragging of the subsystem containing the logical information around suitable loops along which the information remains protected.

preprint2013arXiv

Fluctuation theorems for quantum processes

We present fluctuation theorems and moment generating function equalities for generalized thermodynamic observables and quantum dynamics described by completely positive trace preserving (CPTP) maps, with and without feedback control. Our results include the quantum Jarzynski equality and Crooks fluctuation theorem, and clarify the special role played by the thermodynamic work and thermal equilibrium states in previous studies. We show that for a specific class of generalized measurements, which include projective measurements, unitality replaces microreversibility as the condition for the physicality of the reverse process in our fluctuation theorems. We present an experimental application of our theory to the problem of extracting the system-bath coupling magnitude, which we do for a system of pairs of coupled superconducting flux qubits undergoing quantum annealing.

preprint2013arXiv

No-go theorem for passive single-rail linear optical quantum computing

Photonic quantum systems are among the most promising architectures for quantum computers. It is well known that for dual-rail photons effective non-linearities and near-deterministic non-trivial two-qubit gates can be achieved via the measurement process and by introducing ancillary photons. While in principle this opens a legitimate path to scalable linear optical quantum computing, the technical requirements are still very challenging and thus other optical encodings are being actively investigated. One of the alternatives is to use single-rail encoded photons, where entangled states can be deterministically generated. Here we prove that even for such systems universal optical quantum computing using only passive optical elements such as beam splitters and phase shifters is not possible. This no-go theorem proves that photon bunching cannot be passively suppressed even when extra ancilla modes and arbitrary number of photons are used. Our result provides useful guidance for the design of optical quantum computers.

preprint2013arXiv

Optimized Dynamical Decoupling via Genetic Algorithms

We utilize genetic algorithms to find optimal dynamical decoupling (DD) sequences for a single-qubit system subjected to a general decoherence model under a variety of control pulse conditions. We focus on the case of sequences with equal pulse-intervals and perform the optimization with respect to pulse type and order. In this manner we obtain robust DD sequences, first in the limit of ideal pulses, then when including pulse imperfections such as finite pulse duration and qubit rotation (flip-angle) errors. Although our optimization is numerical, we identify a deterministic structure underlies the top-performing sequences. We use this structure to devise DD sequences which outperform previously designed concatenated DD (CDD) and quadratic DD (QDD) sequences in the presence of pulse errors. We explain our findings using time-dependent perturbation theory and provide a detailed scaling analysis of the optimal sequences.

preprint2013arXiv

Quantum annealing with more than one hundred qubits

Quantum technology is maturing to the point where quantum devices, such as quantum communication systems, quantum random number generators and quantum simulators, may be built with capabilities exceeding classical computers. A quantum annealer, in particular, solves hard optimisation problems by evolving a known initial configuration at non-zero temperature towards the ground state of a Hamiltonian encoding a given problem. Here, we present results from experiments on a 108 qubit D-Wave One device based on superconducting flux qubits. The strong correlations between the device and a simulated quantum annealer, in contrast with weak correlations between the device and classical annealing or classical spin dynamics, demonstrate that the device performs quantum annealing. We find additional evidence for quantum annealing in the form of small-gap avoided level crossings characterizing the hard problems. To assess the computational power of the device we compare it to optimised classical algorithms.

preprint2013arXiv

Review of Decoherence Free Subspaces, Noiseless Subsystems, and Dynamical Decoupling

Quantum information requires protection from the adverse affects of decoherence and noise. This review provides an introduction to the theory of decoherence-free subspaces, noiseless subsystems, and dynamical decoupling. It addresses quantum information preservation as well protected computation.

preprint2012arXiv

Adiabatic quantum algorithm for search engine ranking

We propose an adiabatic quantum algorithm for generating a quantum pure state encoding of the PageRank vector, the most widely used tool in ranking the relative importance of internet pages. We present extensive numerical simulations which provide evidence that this algorithm can prepare the quantum PageRank state in a time which, on average, scales polylogarithmically in the number of webpages. We argue that the main topological feature of the underlying web graph allowing for such a scaling is the out-degree distribution. The top ranked $\log(n)$ entries of the quantum PageRank state can then be estimated with a polynomial quantum speedup. Moreover, the quantum PageRank state can be used in "q-sampling" protocols for testing properties of distributions, which require exponentially fewer measurements than all classical schemes designed for the same task. This can be used to decide whether to run a classical update of the PageRank.

preprint2012arXiv

Experimental signature of programmable quantum annealing

Quantum annealing is a general strategy for solving difficult optimization problems with the aid of quantum adiabatic evolution. Both analytical and numerical evidence suggests that under idealized, closed system conditions, quantum annealing can outperform classical thermalization-based algorithms such as simulated annealing. Do engineered quantum annealing devices effectively perform classical thermalization when coupled to a decohering thermal environment? To address this we establish, using superconducting flux qubits with programmable spin-spin couplings, an experimental signature which is consistent with quantum annealing, and at the same time inconsistent with classical thermalization, in spite of a decoherence timescale which is orders of magnitude shorter than the adiabatic evolution time. This suggests that programmable quantum devices, scalable with current superconducting technology, implement quantum annealing with a surprising robustness against noise and imperfections.

preprint2012arXiv

High Fidelity Adiabatic Quantum Computation via Dynamical Decoupling

We introduce high-order dynamical decoupling strategies for open system adiabatic quantum computation. Our numerical results demonstrate that a judicious choice of high-order dynamical decoupling method, in conjunction with an encoding which allows computation to proceed alongside decoupling, can dramatically enhance the fidelity of adiabatic quantum computation in spite of decoherence.

preprint2011arXiv

Combining dynamical decoupling with fault-tolerant quantum computation

We study how dynamical decoupling (DD) pulse sequences can improve the reliability of quantum computers. We prove upper bounds on the accuracy of DD-protected quantum gates and derive sufficient conditions for DD-protected gates to outperform unprotected gates. Under suitable conditions, fault-tolerant quantum circuits constructed from DD-protected gates can tolerate stronger noise, and have a lower overhead cost, than fault-tolerant circuits constructed from unprotected gates. Our accuracy estimates depend on the dynamics of the bath that couples to the quantum computer, and can be expressed either in terms of the operator norm of the bath's Hamiltonian or in terms of the power spectrum of bath correlations; we explain in particular how the performance of recursively generated concatenated pulse sequences can be analyzed from either viewpoint. Our results apply to Hamiltonian noise models with limited spatial correlations.

preprint2011arXiv

High fidelity quantum memory via dynamical decoupling: theory and experiment

Quantum information processing requires overcoming decoherence---the loss of "quantumness" due to the inevitable interaction between the quantum system and its environment. One approach towards a solution is quantum dynamical decoupling---a method employing strong and frequent pulses applied to the qubits. Here we report on the first experimental test of the concatenated dynamical decoupling (CDD) scheme, which invokes recursively constructed pulse sequences. Using nuclear magnetic resonance, we demonstrate a near order of magnitude improvement in the decay time of stored quantum states. In conjunction with recent results on high fidelity quantum gates using CDD, our results suggest that quantum dynamical decoupling should be used as a first layer of defense against decoherence in quantum information processing implementations, and can be a stand-alone solution in the right parameter regime.

preprint2011arXiv

Quadratic Dynamical Decoupling: Universality Proof and Error Analysis

We prove the universality of the generalized QDD_{N1,N2} (quadratic dynamical decoupling) pulse sequence for near-optimal suppression of general single-qubit decoherence. Earlier work showed numerically that this dynamical decoupling sequence, which consists of an inner Uhrig DD (UDD) and outer UDD sequence using N1 and N2 pulses respectively, can eliminate decoherence to O(T^N) using O(N^2) unequally spaced "ideal" (zero-width) pulses, where T is the total evolution time and N=N1=N2. A proof of the universality of QDD has been given for even N1. Here we give a general universality proof of QDD for arbitrary N1 and N2. As in earlier proofs, our result holds for arbitrary bounded environments. Furthermore, we explore the single-axis (polarization) error suppression abilities of the inner and outer UDD sequences. We analyze both the single-axis QDD performance and how the overall performance of QDD depends on the single-axis errors. We identify various performance effects related to the parities and relative magnitudes of N1 and N2. We prove that using QDD_{N1,N2} decoherence can always be eliminated to O(T^min[N1,N2]).

preprint2011arXiv

Quantum adiabatic machine learning

We develop an approach to machine learning and anomaly detection via quantum adiabatic evolution. In the training phase we identify an optimal set of weak classifiers, to form a single strong classifier. In the testing phase we adiabatically evolve one or more strong classifiers on a superposition of inputs in order to find certain anomalous elements in the classification space. Both the training and testing phases are executed via quantum adiabatic evolution. We apply and illustrate this approach in detail to the problem of software verification and validation.

preprint2011arXiv

Rigorous Performance Bounds for Quadratic and Nested Dynamical Decoupling

We present rigorous performance bounds for the quadratic dynamical decoupling (QDD) pulse sequence which protects a qubit from general decoherence, and for its nested generalization to an arbitrary number of qubits. Our bounds apply under the assumption of instantaneous pulses and of bounded perturbing environment and qubit-environment Hamiltonians such as those realized by baths of nuclear spins in quantum dots. We prove that if the total sequence time is fixed then the trace-norm distance between the unperturbed and protected system states can be made arbitrarily small by increasing the number of applied pulses.

preprint2010arXiv

Arbitrarily Accurate Dynamical Control in Open Quantum Systems

We show that open-loop dynamical control techniques may be used to synthesize unitary transformations in open quantum systems in such a way that decoherence is perturbatively compensated for to a desired (in principle arbitrarily high) level of accuracy, which depends only on the strength of the relevant errors and the achievable rate of control modulation. Our constructive and fully analytical solution employs concatenated dynamically corrected gates, and is applicable independently of detailed knowledge of the system-environment interactions and environment dynamics. Explicit implications for boosting quantum gate fidelities in realistic scenarios are addressed.

preprint2010arXiv

Entanglement and area law with a fractal boundary in a topologically ordered phase

Quantum systems with short range interactions are known to respect an area law for the entanglement entropy: the von Neumann entropy $S$ associated to a bipartition scales with the boundary $p$ between the two parts. Here we study the case in which the boundary is a fractal. We consider the topologically ordered phase of the toric code with a magnetic field. When the field vanishes it is possible to analytically compute the entanglement entropy for both regular and fractal bipartitions $(A,B)$ of the system, and this yields an upper bound for the entire topological phase. When the $A$-$B$ boundary is regular we have $S/p =1$ for large $p$. When the boundary is a fractal of Hausdorff dimension $D$, we show that the entanglement between the two parts scales as $S/p=γ\leq1/D$, and $γ$ depends on the fractal considered.

preprint2010arXiv

High fidelity quantum gates via dynamical decoupling

Realizing the theoretical promise of quantum computers will require overcoming decoherence. Here we demonstrate numerically that high fidelity quantum gates are possible within a framework of quantum dynamical decoupling. Orders of magnitude improvement in the fidelities of a universal set of quantum gates, relative to unprotected evolution, is achieved over a broad range of system-environment coupling strengths, using recursively constructed (concatenated) dynamical decoupling pulse sequences.

preprint2010arXiv

Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions

We elucidate the geometry of quantum adiabatic evolution. By minimizing the deviation from adiabaticity we find a Riemannian metric tensor underlying adiabatic evolution. Equipped with this tensor, we identify a unified geometric description of quantum adiabatic evolution and quantum phase transitions, which generalizes previous treatments to allow for degeneracy. The same structure is relevant for applications in quantum information processing, including adiabatic and holonomic quantum computing, where geodesics over the manifold of control parameters correspond to paths which minimize errors. We illustrate this geometric structure with examples, for which we explicitly find adiabatic geodesics. By solving the geodesic equations in the vicinity of a quantum critical point, we identify universal characteristics of optimal adiabatic passage through a quantum phase transition. In particular, we show that in the vicinity of a critical point describing a second order quantum phase transition, the geodesic exhibits power-law scaling with an exponent given by twice the inverse of the product of the spatial and scaling dimensions.

preprint2010arXiv

Optimized Entanglement-Assisted Quantum Error Correction

Using convex optimization, we propose entanglement-assisted quantum error correction procedures that are optimized for given noise channels. We demonstrate through numerical examples that such an optimized error correction method achieves higher channel fidelities than existing methods. This improved performance, which leads to perfect error correction for a larger class of error channels, is interpreted in at least some cases by quantum teleportation, but for general channels this interpretation does not hold.

preprint2010arXiv

Rigorous Bounds for Optimal Dynamical Decoupling

We present rigorous performance bounds for the optimal dynamical decoupling pulse sequence protecting a quantum bit (qubit) against pure dephasing. Our bounds apply under the assumption of instantaneous pulses and of bounded perturbing environment and qubit-environment Hamiltonians. We show that if the total sequence time is fixed the optimal sequence can be used to make the distance between the protected and unperturbed qubit states arbitrarily small in the number of applied pulses. If, on the other hand, the minimum pulse interval is fixed and the total sequence time is allowed to scale with the number of pulses, then longer sequences need not always be advantageous. The rigorous bound may serve as testbed for approximate treatments of optimal decoupling in bounded models of decoherence.

preprint2009arXiv

Near-optimal dynamical decoupling of a qubit

We present a near-optimal quantum dynamical decoupling scheme that eliminates general decoherence of a qubit to order n using O(n^2) pulses, an exponential decrease in pulses over all previous decoupling methods. Numerical simulations of a qubit coupled to a spin bath demonstrate the superior performance of the new pulse sequences.

preprint2008arXiv

Channel-Optimized Quantum Error Correction

We develop a theory for finding quantum error correction (QEC) procedures which are optimized for given noise channels. Our theory accounts for uncertainties in the noise channel, against which our QEC procedures are robust. We demonstrate via numerical examples that our optimized QEC procedures always achieve a higher channel fidelity than the standard error correction method, which is agnostic about the specifics of the channel. This demonstrates the importance of channel characterization before QEC procedures are applied. Our main novel finding is that in the setting of a known noise channel the recovery ancillas are redundant for optimized quantum error correction. We show this using a general rank minimization heuristic and supporting numerical calculations. Therefore, one can further improve the fidelity by utilizing all the available ancillas in the encoding block.

preprint2006arXiv

Decoherence-induced geometric phase in a multilevel atomic system

We consider the STIRAP process in a three-level atom. Viewed as a closed system, no geometric phase is acquired. But in the presence of spontaneous emission and/or collisional relaxation we show numerically that a non-vanishing, purely real, geometric phase is acquired during STIRAP, whose magnitude grows with the decay rates. Rather than viewing this decoherence-induced geometric phase as a nuisance, it can be considered an example of "beneficial decoherence": the environment provides a mechanism for the generation of geometric phases which would otherwise require an extra experimental control knob.

preprint2006arXiv

Robust transmission of non-Gaussian entanglement over optical fibers

We show how the entanglement in a wide range of continuous variable non-Gaussian states can be preserved against decoherence for long-range quantum communication through an optical fiber. We apply protection via decoherence-free subspaces and quantum dynamical decoupling to this end. The latter is implemented by inserting phase shifters at regular intervals $Δ$ inside the fiber, where $Δ$ is roughly the ratio of the speed of light in the fiber to the bath high-frequency cutoff. Detailed estimates of relevant parameters are provided using the boson-boson model of system-bath interaction for silica fibers, and $Δ$ is found to be on the order of a millimeter.

preprint2004arXiv

Exchange Interaction Between Three and Four Coupled Quantum Dots: Theory and Applications to Quantum Computing

Several prominent proposals have suggested that spins of localized electrons could serve as quantum computer qubits. The exchange interaction has been invoked as a means of implementing two qubit gates. In this paper, we analyze the strength and form of the exchange interaction under relevant conditions. We find that, when several spins are engaged in mutual interactions, the quantitative strengths or even qualitative forms of the interactions can change. It is shown that the changes can be dramatic within a Heitler-London model. Hund-Mulliken calculations are also presented, and support the qualititative conclusions from the Heitler-London model. The effects need to be considered in spin-based quantum computer designs, either as a source of gate error to be overcome or a new interaction to be exploited.

preprint2003arXiv

Quantum Computers and Decoherence: Exorcising the Demon from the Machine

Decoherence is the main obstacle to the realization of quantum computers. Until recently it was thought that quantum error correcting codes are the only complete solution to the decoherence problem. Here we present an alternative that is based on a combination of a decoherence-free subspace encoding and the application of strong and fast pulses: ``encoded recoupling and decoupling'' (ERD). This alternative has the advantage of lower encoding overhead (as few as two physical qubits per logical qubit suffice), and direct application to a number of promising proposals for the experimental realization of quantum computers.

preprint2002arXiv

An Implementation of the Deutsch-Jozsa Algorithm on Molecular Vibronic Coherences Through Four-Wave Mixing: a Theoretical Study

Time-Frequency Resolved Coherent Anti-Stokes Raman Scattering (TFRCARS) was recently proposed as a means to implement quantum logic using the molecular ro-vibrational manifold as a quantum register [R. Zadoyan et al., Chem. Phys. 266, 323 (2001)]. We give a concrete example of how this can be accomplished through an illustrative algorithm that solves the Deutsch-Jozsa problem. We use realistic molecular parameters to recognize that, as the problem size expands, shaped pulses must be tailored to maintain fidelity of the algorithm.

preprint2002arXiv

Combined Error Correction Techniques for Quantum Computing Architectures

Proposals for quantum computing devices are many and varied. They each have unique noise processes that make none of them fully reliable at this time. There are several error correction/avoidance techniques which are valuable for reducing or eliminating errors, but not one, alone, will serve as a panacea. One must therefore take advantage of the strength of each of these techniques so that we may extend the coherence times of the quantum systems and create more reliable computing devices. To this end we give a general strategy for using dynamical decoupling operations on encoded subspaces. These encodings may be of any form; of particular importance are decoherence-free subspaces and quantum error correction codes. We then give means for empirically determining an appropriate set of dynamical decoupling operations for a given experiment. Using these techniques, we then propose a comprehensive encoding solution to many of the problems of quantum computing proposals which use exchange-type interactions. This uses a decoherence-free subspace and an efficient set of dynamical decoupling operations. It also addresses the problems of controllability in solid state quantum dot devices.

preprint2002arXiv

Quantum Codes for Simplifying Design and Suppressing Decoherence in Superconducting Phase-Qubits

We introduce simple qubit-encodings and logic gates which eliminate the need for certain difficult single-qubit operations in superconducting phase-qubits, while preserving universality. The simplest encoding uses two physical qubits per logical qubit. Two architectures for its implementation are proposed: one employing N physical qubits out of which N/2 are ancillas fixed in the |1> state, the other employing N/2+1 physical qubits, one of which is a bus qubit connected to all others. Details of a minimal set of universal encoded logic operations are given, together with recoupling schemes, that require nanosecond pulses. A generalization to codes with higher ratio of number of logical qubits per physical qubits is presented. Compatible decoherence and noise suppression strategies are also discussed.

preprint2002arXiv

Universal Fault-Tolerant Quantum Computation in the Presence of Spontaneous Emission and Collective Dephasing

A universal and fault tolerant scheme for quantum computation is proposed which utilizes a class of error correcting codes that is based on the detection of spontaneous emission (of, e.g., photons, phonons, and ripplons). The scheme is compatible with a number of promising solid-state and quantum-optical proposals for quantum computer implementations, such as quantum dots in cavities, electrons on helium, and trapped ions.

preprint2001arXiv

From Completely Positive Maps to the Quantum Markovian Semigroup Master Equation

A central problem in the theory of the dynamics of open quantum systems is the derivation of a rigorous and computationally tractable master equation for the reduced system density matrix. Most generally, the evolution of an open quantum system is described by a completely positive linear map. We show how to derive a completely positive Markovian master equation (the Lindblad equation) from such a map by a coarse graining procedure. We provide a novel and explicit recipe for calculating the coefficients of the master equation, using perturbation theory in the weak-coupling limit. The only parameter external to our theory is the coarse-graining time-scale. We illustrate the method by explicitly deriving the master equation for the spin-boson model. The results are evaluated for the exactly solvable case of pure dephasing, and an excellent agreement is found within the timescale where the Markovian approximation is expected to be valid. The method can be extended in principle to include non-Markovian effects.

preprint2000arXiv

Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations

The recursion equation analysis of Grover's quantum search algorithm presented by Biham et al. [PRA 60, 2742 (1999)] is generalized. It is applied to the large class of Grover's type algorithms in which the Hadamard transform is replaced by any other unitary transformation and the phase inversion is replaced by a rotation by an arbitrary angle. The time evolution of the amplitudes of the marked and unmarked states, for any initial complex amplitude distribution is expressed using first order linear difference equations. These equations are solved exactly. The solution provides the number of iterations T after which the probability of finding a marked state upon measurement is the highest, as well as the value of this probability, P_max. Both T and P_max are found to depend on the averages and variances of the initial amplitude distributions of the marked and unmarked states, but not on higher moments.

preprint2000arXiv

Decoherence-Free Subspaces for Multiple-Qubit Errors: (I) Characterization

Coherence in an open quantum system is degraded through its interaction with a bath. This decoherence can be avoided by restricting the dynamics of the system to special decoherence-free subspaces. These subspaces are usually constructed under the assumption of spatially symmetric system-bath coupling. Here we show that decoherence-free subspaces may appear without spatial symmetry. Instead, we consider a model of system-bath interactions in which to first order only multiple-qubit coupling to the bath is present, with single-qubit system-bath coupling absent. We derive necessary and sufficient conditions for the appearance of decoherence-free states in this model, and give a number of examples. In a sequel paper we show how to perform universal and fault tolerant quantum computation on the decoherence-free subspaces considered in this paper.

preprint2000arXiv

Decoherence-Free Subspaces for Multiple-Qubit Errors: (II) Universal, Fault-Tolerant Quantum Computation

Decoherence-free subspaces (DFSs) shield quantum information from errors induced by the interaction with an uncontrollable environment. Here we study a model of correlated errors forming an Abelian subgroup (stabilizer) of the Pauli group (the group of tensor products of Pauli matrices). Unlike previous studies of DFSs, this type of errors does not involve any spatial symmetry assumptions on the system-environment interaction. We solve the problem of universal, fault-tolerant quantum computation on the associated class of DFSs.

preprint2000arXiv

Universal Fault-Tolerant Computation on Decoherence-Free Subspaces

A general scheme to perform universal quantum computation within decoherence-free subspaces (DFSs) of a system's Hilbert space is presented. This scheme leads to the first fault-tolerant realization of universal quantum computation on DFSs with the properties that (i) only one- and two-qubit interactions are required, and (ii) the system remains within the DFS throughout the entire implementation of a quantum gate. We show explicitly how to perform universal computation on clusters of the four-qubit DFS encoding one logical qubit each under "collective decoherence" (qubit-permutation-invariant system-bath coupling). Our results have immediate relevance to a number of solid-state quantum computer implementations, in particular those in which quantum logic is implemented through exchange interactions, such as the recently proposed spin-spin coupled GaAs quantum dot arrays and the Si:$^{31}$P nuclear spin arrays.

preprint1999arXiv

Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution

Grover's algorithm for quantum searching is generalized to deal with arbitrary initial complex amplitude distributions. First order linear difference equations are found for the time evolution of the amplitudes of the marked and unmarked states. These equations are solved exactly. New expressions are derived for the optimal time of measurement and the maximal probability of success. They are found to depend on the averages and variances of the initial amplitude distributions of the marked and unmarked states, but not on higher moments. Our results imply that Grover's algorithm is robust against modest noise in the amplitude initialization procedure.

preprint1999arXiv

How to Teleport Superpositions of Chiral Amplitudes

Chiral molecules may exist in superpositions of left- and right-handed states. We show how the amplitudes of such superpositions may be teleported to the polarization degrees of freedom of a photon and thus measured. Two experimental schemes are proposed, one leading to perfect, the other to state-dependent teleportation. Both methods yield complete information about the amplitudes.

preprint1999arXiv

Inversion of Randomly Corrugated Surfaces Structure from Atom Scattering Data

The Sudden Approximation is applied to invert structural data on randomly corrugated surfaces from inert atom scattering intensities. Several expressions relating experimental observables to surface statistical features are derived. The results suggest that atom (and in particular He) scattering can be used profitably to study hitherto unexplored forms of complex surface disorder.

preprint1999arXiv

Protecting Quantum Information Encoded in Decoherence Free States Against Exchange Errors

The exchange interaction between identical qubits in a quantum information processor gives rise to unitary two-qubit errors. It is shown here that decoherence free subspaces (DFSs) for collective decoherence undergo Pauli errors under exchange, which however do not take the decoherence free states outside of the DFS. In order to protect DFSs against these errors it is sufficient to employ a recently proposed concatenated DFS-quantum error correcting code scheme [D.A. Lidar, D. Bacon and K.B. Whaley, Phys. Rev. Lett. {\bf 82}, 4556 (1999)].

preprint1998arXiv

Atom Scattering from Disordered Surfaces in the Sudden Approximation: Double Collisions Effects and Quantum Liquids

The Sudden Approximation (SA) for scattering of atoms from surfaces is generalized to allow for double collision events and scattering from time-dependent quantum liquid surfaces. The resulting new schemes retain the simplicity of the original SA, while requiring little extra computational effort. The results suggest that inert atom (and in particular He) scattering can be used profitably to study hitherto unexplored forms of complex surface disorder.

preprint1998arXiv

Generalized Grover Search Algorithm for Arbitrary Initial Amplitude Distribution

Grover's algorithm for quantum searching of a database is generalized to deal with arbitrary initial amplitude distributions. First order linear difference equations are found for the time evolution of the amplitudes of the r marked and N-r unmarked states. These equations are solved exactly. An expression for the optimal measurement time T \sim O(\sqrt{N/r}) is derived which is shown to depend only on the initial average amplitudes of the marked and unmarked states. A bound on the probability of measuring a marked state is derived, which depends only on the standard deviation of the initial amplitude distributions of the marked or unmarked states.

preprint1998arXiv

Scaling Range and Cutoffs in Empirical Fractals

Fractal structures appear in a vast range of physical systems. A literature survey including all experimental papers on fractals which appeared in the six Physical Review journals (A-E and Letters) during the 1990's shows that experimental reports of fractal behavior are typically based on a scaling range $Δ$ which spans only 0.5 - 2 decades. This range is limited by upper and lower cutoffs either because further data is not accessible or due to crossover bends. Focusing on spatial fractals, a classification is proposed into (a) aggregation; (b) porous media; (c) surfaces and fronts; (d) fracture and (e) critical phenomena. Most of these systems, [except for class (e)] involve processes far from thermal equilibrium. The fact that for self similar fractals [in contrast to the self affine fractals of class (c)] there are hardly any exceptions to the finding of $Δ\le 2$ decades, raises the possibility that the cutoffs are due to intrinsic properties of the measured systems rather than the specific experimental conditions and apparatus. To examine the origin of the limited range we focus on a class of aggregation systems. In these systems a molecular beam is deposited on a surface, giving rise to nucleation and growth of diffusion-limited-aggregation-like clusters. Scaling arguments are used to show that the required duration of the deposition experiment increases exponentially with $Δ$. Furthermore, using realistic parameters for surfaces such as Al(111) it is shown that these considerations limit the range of fractal behavior to less than two decades in agreement with the experimental findings. It is conjectured that related kinetic mechanisms that limit the scaling range are common in other nonequilibrium processes which generate spatial fractals.

preprint1998arXiv

The Limited Scaling Range of Empirical Fractals

The notion of the abundance of fractals is critically re-examined in light of surprising data regarding the scaling range in empirical reports on fractality.

preprint1997arXiv

Limited Range Fractality of Randomly Adsorbed Rods

Multiple resolution analysis of two dimensional structures composed of randomly adsorbed penetrable rods, for densities below the percolation threshold, has been carried out using box-counting functions. It is found that at relevant resolutions, for box-sizes, $r$, between cutoffs given by the average rod length $<\ell>$ and the average inter-rod distance $r_1$, these systems exhibit apparent fractal behavior. It is shown that unlike the case of randomly distributed isotropic objects, the upper cutoff $r_1$ is not only a function of the coverage but also depends on the excluded volume, averaged over the orientational distribution. Moreover, the apparent fractal dimension also depends on the orientational distributions of the rods and decreases as it becomes more anisotropic. For box sizes smaller than $<\ell>$ the box counting function is determined by the internal structure of the rods, whether simple or itself fractal. Two examples are considered - one of regular rods of one dimensional structure and rods which are trimmed into a Cantor set structure which are fractals themselves. The models examined are relevant to adsorption of linear molecules and fibers, liquid crystals, stress induced fractures and edge imperfections in metal catalysts. We thus obtain a distinction between two ranges of length scales: $r < <\ell>$ where the internal structure of the adsorbed objects is probed, and $<\ell> < r < r_1$ where their distribution is probed, both of which may exhibit fractal behavior. This distinction is relevant to the large class of systems which exhibit aggregation of a finite density of fractal-like clusters, which includes surface growth in molecular beam epitaxy and diffusion-limited-cluster-cluster-aggregation models.

Daniel A. Lidar

What is connected

Connect this record

See the researcher in context

Building this map preview

81 published item(s)

3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers

Breakdown of the weak coupling limit in quantum annealing

Customized quantum annealing schedules

HOQST: Hamiltonian Open Quantum System Toolkit

Standard quantum annealing outperforms adiabatic reverse annealing with decoherence

Anneal-path correction in flux qubits

Demonstration of long-range correlations via susceptibility measurements in a one-dimensional superconducting Josephson spin chain

Improved Boltzmann machines with error corrected quantum annealing

Lecture Notes on the Theory of Open Quantum Systems

Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond

Why and when is pausing beneficial in quantum annealing?

Reverse quantum annealing of the $p$-spin model with relaxation

Adiabaticity in open quantum systems

Eigenstate Tracking in Open Quantum Systems

Mean Field Analysis of Quantum Annealing Correction

Optimally Stopped Optimization

Simulated Quantum Annealing with Two All-to-All Connectivity Schemes

A general framework for complete positivity

Beyond Complete Positivity

Consistency Tests of Classical and Quantum Models for a Quantum Annealer

Decoherence in adiabatic quantum computation

Nested Quantum Annealing Correction

Quantum Adiabatic Markovian Master Equations

Quantum annealing correction for random Ising problems

Quantum Annealing Correction with Minor Embedding

Quantum speed limits for leakage and decoherence

Reexamination of the evidence for entanglement in the D-Wave processor

Tunneling and speedup in quantum optimization for permutation-symmetric problems

When Diabatic Trumps Adiabatic in Quantum Optimization

Defining and detecting quantum speedup

Quantum error suppression with commuting Hamiltonians: Two-local is too local

Reexamining classical and quantum models for the D-Wave One processor

Adiabatic quantum optimization with the wrong Hamiltonian

Coarse-Graining Can Beat the Rotating Wave Approximation in Quantum Markovian Master Equations

Comment on: "Classical signature of quantum annealing"

Error corrected quantum annealing with hundreds of qubits

Evolution prediction from tomography

Fault tolerance for holonomic quantum computation

Fluctuation theorems for quantum processes

No-go theorem for passive single-rail linear optical quantum computing

Optimized Dynamical Decoupling via Genetic Algorithms

Quantum annealing with more than one hundred qubits

Review of Decoherence Free Subspaces, Noiseless Subsystems, and Dynamical Decoupling

Adiabatic quantum algorithm for search engine ranking

Experimental signature of programmable quantum annealing

High Fidelity Adiabatic Quantum Computation via Dynamical Decoupling

Combining dynamical decoupling with fault-tolerant quantum computation

High fidelity quantum memory via dynamical decoupling: theory and experiment

Quadratic Dynamical Decoupling: Universality Proof and Error Analysis

Quantum adiabatic machine learning

Rigorous Performance Bounds for Quadratic and Nested Dynamical Decoupling

Arbitrarily Accurate Dynamical Control in Open Quantum Systems

Entanglement and area law with a fractal boundary in a topologically ordered phase

High fidelity quantum gates via dynamical decoupling

Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions

Optimized Entanglement-Assisted Quantum Error Correction

Rigorous Bounds for Optimal Dynamical Decoupling

Near-optimal dynamical decoupling of a qubit

Channel-Optimized Quantum Error Correction

Decoherence-induced geometric phase in a multilevel atomic system

Robust transmission of non-Gaussian entanglement over optical fibers

Exchange Interaction Between Three and Four Coupled Quantum Dots: Theory and Applications to Quantum Computing

Quantum Computers and Decoherence: Exorcising the Demon from the Machine

An Implementation of the Deutsch-Jozsa Algorithm on Molecular Vibronic Coherences Through Four-Wave Mixing: a Theoretical Study

Combined Error Correction Techniques for Quantum Computing Architectures

Quantum Codes for Simplifying Design and Suppressing Decoherence in Superconducting Phase-Qubits

Universal Fault-Tolerant Quantum Computation in the Presence of Spontaneous Emission and Collective Dephasing

From Completely Positive Maps to the Quantum Markovian Semigroup Master Equation

Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations

Decoherence-Free Subspaces for Multiple-Qubit Errors: (I) Characterization

Decoherence-Free Subspaces for Multiple-Qubit Errors: (II) Universal, Fault-Tolerant Quantum Computation

Universal Fault-Tolerant Computation on Decoherence-Free Subspaces

Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution

How to Teleport Superpositions of Chiral Amplitudes