@article {3489, title = {Efficient and practical Hamiltonian simulation from time-dependent product formulas}, year = {2024}, month = {3/13/2024}, abstract = {

In this work we propose an approach for implementing time-evolution of a quantum system using product formulas. The quantum algorithms we develop have provably better scaling (in terms of gate complexity and circuit depth) than a naive application of well-known Trotter formulas, for systems where the evolution is determined by a Hamiltonian with different energy scales (i.e., one part is \"large\" and another part is \"small\"). Our algorithms generate a decomposition of the evolution operator into a product of simple unitaries that are directly implementable on a quantum computer. Although the theoretical scaling is suboptimal compared with state-of-the-art algorithms (e.g., quantum signal processing), the performance of the algorithms we propose is highly competitive in practice. We illustrate this via extensive numerical simulations for several models. For instance, in the strong-field regime of the 1D transverse-field Ising model, our algorithms achieve an improvement of one order of magnitude in both the system size and evolution time that can be simulated with a fixed budget of 1000 arbitrary 2-qubit gates, compared with standard Trotter formulas.

}, url = {https://arxiv.org/abs/2403.08729}, author = {Jan Lukas Bosse and Andrew M. Childs and Charles Derby and Filippo Maria Gambetta and Ashley Montanaro and Raul A. Santos} } @article {3490, title = {Efficiently verifiable quantum advantage on near-term analog quantum simulators}, year = {2024}, month = {3/13/2024}, abstract = {

Existing schemes for demonstrating quantum computational advantage are subject to various practical restrictions, including the hardness of verification and challenges in experimental implementation. Meanwhile, analog quantum simulators have been realized in many experiments to study novel physics. In this work, we propose a quantum advantage protocol based on single-step Feynman-Kitaev verification of an analog quantum simulation, in which the verifier need only run an O(λ2)-time classical computation, and the prover need only prepare O(1) samples of a history state and perform O(λ2) single-qubit measurements, for a security parameter λ. We also propose a near-term feasible strategy for honest provers and discuss potential experimental realizations.

}, url = {https://arxiv.org/abs/2403.08195}, author = {Zhenning Liu and Dhruv Devulapalli and Dominik Hangleiter and Yi-Kai Liu and Alicia J. Koll{\'a}r and Alexey V. Gorshkov and Andrew M. Childs} } @article {3499, title = {Encoding Majorana codes}, year = {2024}, month = {2/12/2024}, abstract = {

To implement a quantum error correction protocol, we first need a scheme to prepare our state in the correct subspace of the code, and this can be done using a unitary encoding circuit. Majorana codes are special since any gates that transform such codes must preserve fermionic parity. In this paper, we present an algorithm that uses the stabilizer matrix to compute unitary encoding circuits for Majorana codes. We present two approaches, both of which use a version of Gaussian elimination with row operations replaced with elementary fermionic Clifford operations. One approach uses an additional ancilla mode and works for all Majorana stabilizer codes, while the second approach does not use ancilla but does not work if the total parity is inside the stabilizer group.

}, url = {https://arxiv.org/abs/2402.07829}, author = {Maryam Mudassar and Riley W. Chien and Daniel Gottesman} } @article {3494, title = {Error Correction in Dynamical Codes}, year = {2024}, month = {3/7/2024}, abstract = {

We ask what is the general framework for a quantum error correcting code that is defined by a sequence of measurements. Recently, there has been much interest in Floquet codes and space-time codes. In this work, we define and study the distance of a dynamical code. This is a subtle concept and difficult to determine: At any given time, the system will be in a subspace which forms a quantum error-correcting code with a given distance, but the full error correction capability of that code may not be available due to the schedule of measurements associated with the code. We address this challenge by developing an algorithm that tracks information we have learned about the error syndromes through the protocol and put that together to determine the distance of a dynamical code, in a non-fault-tolerant context. We use the tools developed for the algorithm to analyze the initialization and masking properties of a generic Floquet code. Further, we look at properties of dynamical codes under the constraint of geometric locality with a view to understand whether the fundamental limitations on logical gates and code parameters imposed by geometric locality for traditional codes can be surpassed in the dynamical paradigm. We find that codes with a limited number of long range connectivity will not allow non-Clifford gates to be implemented with finite depth circuits in the 2D setting.

}, url = {https://arxiv.org/abs/2403.04163}, author = {Xiaozhen Fu and Daniel Gottesman} } @article {3462, title = {Estimation of Hamiltonian parameters from thermal states}, year = {2024}, month = {1/18/2024}, abstract = {

We upper- and lower-bound the optimal precision with which one can estimate an unknown Hamiltonian parameter via measurements of Gibbs thermal states with a known temperature. The bounds depend on the uncertainty in the Hamiltonian term that contains the parameter and on the term\&$\#$39;s degree of noncommutativity with the full Hamiltonian: higher uncertainty and commuting operators lead to better precision. We apply the bounds to show that there exist entangled thermal states such that the parameter can be estimated with an error that decreases faster than 1/n\−\−\√, beating the standard quantum limit. This result governs Hamiltonians where an unknown scalar parameter (e.g. a component of a magnetic field) is coupled locally and identically to n qubit sensors. In the high-temperature regime, our bounds allow for pinpointing the optimal estimation error, up to a constant prefactor. Our bounds generalize to joint estimations of multiple parameters. In this setting, we recover the high-temperature sample scaling derived previously via techniques based on quantum state discrimination and coding theory. In an application, we show that noncommuting conserved quantities hinder the estimation of chemical potentials.

}, url = {https://arxiv.org/abs/2401.10343}, author = {Luis Pedro Garc{\'\i}a-Pintos and Kishor Bharti and Jacob Bringewatt and Hossein Dehghani and Adam Ehrenberg and Nicole Yunger Halpern and Alexey V. Gorshkov} } @article {3498, title = {Experimental roadmap for optimal state transfer and entanglement generation in power-law systems}, year = {2024}, month = {2/12/2024}, abstract = {

Experimental systems with power-law interactions have recently garnered interest as promising platforms for quantum information processing. Such systems are capable of spreading entanglement superballistically and achieving an asymptotic speed-up over locally interacting systems. Recently, protocols developed by Eldredge et al. [Phys. Rev. Lett. 119, 170503 (2017)] and Tran et al. [Phys. Rev. X 11, 031016 (2021)] for the task of transferring a quantum state between distant particles quickly were shown to be optimal and saturate theoretical bounds. However, the implementation of these protocols in physical systems with long-range interactions remains to be fully realized. In this work, we provide an experimental roadmap towards realizing fast state-transfer protocols in three classes of atomic and molecular systems with dipolar interactions: polar molecules composed of alkali-metal dimers, neutral atoms in excited Rydberg states, and atoms with strong magnetic moments (e.g. dysprosium). As a guide to near-term experimental implementation, we numerically evaluate the tradeoffs between the two protocols for small system sizes and develop methods to address potential crosstalk errors that may arise during the execution of the protocols.

}, url = {https://arxiv.org/abs/2402.07974}, author = {Andrew Y. Guo and Jeremy T. Young and Ron Belyansky and Przemyslaw Bienias and Alexey V. Gorshkov} } @article {3307, title = {Effect of non-unital noise on random circuit sampling}, year = {2023}, month = {6/28/2023}, abstract = {

In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical non-unital noise sources with constant noise rates. We show that even in the presence of unital sources like the depolarizing channel, the distribution, under the combined noise channel, never resembles a maximally entropic distribution at any depth. To show this, we prove that the output distribution of such circuits never anticoncentrates \— meaning it is never too \"flat\" \— regardless of the depth of the circuit. This is in stark contrast to the behavior of noiseless random quantum circuits or those with only unital noise, both of which anticoncentrate at sufficiently large depths. As consequences, our results have interesting algorithmic implications on both the hardness and easiness of noisy random circuit sampling, since anticoncentration is a critical property exploited by both state-of-the-art classical hardness and easiness results.

}, url = {https://arxiv.org/abs/2306.16659}, author = {Bill Fefferman and Soumik Ghosh and Michael Gullans and Kohdai Kuroiwa and Kunal Sharma} } @article {3265, title = {Efficient learning of ground \& thermal states within phases of matter}, year = {2023}, month = {1/30/2023}, abstract = {

We consider two related tasks: (a) estimating a parameterisation of a given Gibbs state and expectation values of Lipschitz observables on this state; and (b) learning the expectation values of local observables within a thermal or quantum phase of matter. In both cases, we wish to minimise the number of samples we use to learn these properties to a given precision.
For the first task, we develop new techniques to learn parameterisations of classes of systems, including quantum Gibbs states of non-commuting Hamiltonians with exponential decay of correlations and the approximate Markov property. We show it is possible to infer the expectation values of all extensive properties of the state from a number of copies that not only scales polylogarithmically with the system size, but polynomially in the observable\&$\#$39;s locality -- an exponential improvement. This set of properties includes expected values of quasi-local observables and entropies.\ \ For the second task, we develop efficient algorithms for learning observables in a phase of matter of a quantum system. By exploiting the locality of the Hamiltonian, we show that M local observables can be learned with probability 1\−δ to precision ϵ with using only N=O(log(Mδ)epolylog(ϵ\−1)) samples -- an exponential improvement on the precision over previous bounds. Our results apply to both families of ground states of Hamiltonians displaying local topological quantum order, and thermal phases of matter with exponential decay of correlations. In addition, our sample complexity applies to the worse case setting whereas previous results only applied on average.
Furthermore, we develop tools of independent interest, such as robust shadow tomography algorithms, Gibbs approximations to ground states, and generalisations of transportation cost inequalities for Gibbs states.

}, url = {https://arxiv.org/abs/2301.12946}, author = {Emilio Onorati and Cambyse Rouz{\'e} and Daniel Stilck Fran{\c c}a and James D. Watson} } @article {3256, title = {Error Mitigation Thresholds in Noisy Quantum Circuits}, year = {2023}, month = {2/8/2023}, abstract = {

Extracting useful information from noisy near-term quantum simulations requires error mitigation strategies. A broad class of these strategies rely on precise characterization of the noise source. We study the performance of such strategies when the noise is imperfectly characterized. We adapt an Imry-Ma argument to predict the existence of an error mitigation threshold for random spatially local circuits in spatial dimensions D\≥2: characterization disorder below the threshold rate allows for error mitigation up to times that scale with the number of qubits. For one-dimensional circuits, by contrast, mitigation fails at an O(1) time for any imperfection in the characterization of disorder. We discuss implications for tests of quantum computational advantage, fault-tolerant probes of measurement-induced phase transitions, and quantum algorithms in near-term devices.

}, url = {https://arxiv.org/abs/2302.04278}, author = {Pradeep Niroula and Sarang Gopalakrishnan and Michael Gullans} } @article {3394, title = {Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model}, year = {2023}, month = {12/17/2023}, abstract = {

In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have been well-studied and are widely believed to be secure. However, SelfTargetMSIS is novel and, though classically as hard as MSIS, its quantum hardness is unclear. In this paper, we provide the first proof of the hardness of SelfTargetMSIS via a reduction from MLWE in the Quantum Random Oracle Model (QROM). Our proof uses recently developed techniques in quantum reprogramming and rewinding. A central part of our approach is a proof that a certain hash function, derived from the MSIS problem, is collapsing. From this approach, we deduce a new security proof for Dilithium under appropriate parameter settings. Compared to the only other rigorous security proof for a variant of Dilithium, Dilithium-QROM, our proof has the advantage of being applicable under the condition q = 1 mod 2n, where q denotes the modulus and n the dimension of the underlying algebraic ring. This condition is part of the original Dilithium proposal and is crucial for the efficient implementation of the scheme. We provide new secure parameter sets for Dilithium under the condition q = 1 mod 2n, finding that our public key sizes and signature sizes are about 2.5 to 2.8 times larger than those of Dilithium-QROM for the same security levels.

}, url = {https://arxiv.org/abs/2312.16619}, author = {Kelsey A. Jackson and Carl Miller and Daochen Wang} } @article {3261, title = {Ever more optimized simulations of fermionic systems on a quantum computer}, year = {2023}, month = {3/6/2023}, abstract = {

Despite using a novel model of computation, quantum computers break down programs into elementary gates. Among such gates, entangling gates are the most expensive. In the context of fermionic simulations, we develop a suite of compilation and optimization techniques that massively reduce the entangling-gate counts. We exploit the well-studied non-quantum optimization algorithms to achieve up to 24\% savings over the state of the art for several small-molecule simulations, with no loss of accuracy or hidden costs. Our methodologies straightforwardly generalize to wider classes of near-term simulations of the ground state of a fermionic system or real-time simulations probing dynamical properties of a fermionic system.\ 

}, url = {https://arxiv.org/abs/2303.03460}, author = {Qingfeng Wang and Ze-Pei Cian and Ming Li and Igor L. Markov and Yunseong Nam} } @article {3316, title = {Experimental Observation of Thermalization with Noncommuting Charges}, journal = {PRX Quantum}, volume = {4}, year = {2023}, month = {4/28/2023}, abstract = {

Quantum simulators have recently enabled experimental observations of quantum many-body systems\&$\#$39; internal thermalization. Often, the global energy and particle number are conserved, and the system is prepared with a well-defined particle number - in a microcanonical subspace. However, quantum evolution can also conserve quantities, or charges, that fail to commute with each other. Noncommuting charges have recently emerged as a subfield at the intersection of quantum thermodynamics and quantum information. Until now, this subfield has remained theoretical. We initiate the experimental testing of its predictions, with a trapped-ion simulator. We prepare 6-21 spins in an approximate microcanonical subspace, a generalization of the microcanonical subspace for accommodating noncommuting charges, which cannot necessarily have well-defined nontrivial values simultaneously. We simulate a Heisenberg evolution using laser-induced entangling interactions and collective spin rotations. The noncommuting charges are the three spin components. We find that small subsystems equilibrate to near a recently predicted non-Abelian thermal state. This work bridges quantum many-body simulators to the quantum thermodynamics of noncommuting charges, whose predictions can now be tested.

}, doi = {10.1103/prxquantum.4.020318}, url = {https://arxiv.org/abs/2202.04652}, author = {Florian Kranzl and Aleksander Lasek and Manoj K. Joshi and Amir Kalev and Rainer Blatt and Christian F. Roos and Nicole Yunger Halpern} } @article {3205, title = {Efficient and practical quantum compiler towards multi-qubit systems with deep reinforcement learning}, year = {2022}, month = {4/14/2022}, abstract = {

Efficient quantum compiling tactics greatly enhance the capability of quantum computers to execute complicated quantum algorithms. Due to its fundamental importance, a plethora of quantum compilers has been designed in past years. However, there are several caveats to current protocols, which are low optimality, high inference time, limited scalability, and lack of universality. To compensate for these defects, here we devise an efficient and practical quantum compiler assisted by advanced deep reinforcement learning (RL) techniques, i.e., data generation, deep Q-learning, and AQ* search. In this way, our protocol is compatible with various quantum machines and can be used to compile multi-qubit operators. We systematically evaluate the performance of our proposal in compiling quantum operators with both inverse-closed and inverse-free universal basis sets. In the task of single-qubit operator compiling, our proposal outperforms other RL-based quantum compilers in the measure of compiling sequence length and inference time. Meanwhile, the output solution is near-optimal, guaranteed by the Solovay-Kitaev theorem. Notably, for the inverse-free universal basis set, the achieved sequence length complexity is comparable with the inverse-based setting and dramatically advances previous methods. These empirical results contribute to improving the inverse-free Solovay-Kitaev theorem. In addition, for the first time, we demonstrate how to leverage RL-based quantum compilers to accomplish two-qubit operator compiling. The achieved results open an avenue for integrating RL with quantum compiling to unify efficiency and practicality and thus facilitate the exploration of quantum advantages.

}, keywords = {FOS: Computer and information sciences, FOS: Physical sciences, Machine Learning (cs.LG), Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2204.06904}, url = {https://arxiv.org/abs/2204.06904}, author = {Chen, Qiuhao and Du, Yuxuan and Zhao, Qi and Jiao, Yuling and Lu, Xiliang and Wu, Xingyao} } @article {2910, title = {Efficient Product Formulas for Commutators and Applications to Quantum Simulation}, journal = {Physical Review Research}, volume = {4}, year = {2022}, month = {03/10/2022}, chapter = {013191}, abstract = {

We construct product formulas for exponentials of commutators and explore their applications. First, we directly construct a third-order product formula with six exponentials by solving polynomial equations obtained using the operator differential method. We then derive higher-order product formulas recursively from the third-order formula. We improve over previous recursive constructions, reducing the number of gates required to achieve the same accuracy. In addition, we demonstrate that the constituent linear terms in the commutator can be included at no extra cost. As an application, we show how to use the product formulas in a digital protocol for counterdiabatic driving, which increases the fidelity for quantum state preparation. We also discuss applications to quantum simulation of one-dimensional fermion chains with nearest- and next-nearest-neighbor hopping terms, and two-dimensional fractional quantum Hall phases.

}, doi = {https://doi.org/10.1103/PhysRevResearch.4.013191}, url = {https://arxiv.org/abs/2111.12177}, author = {Yu-An Chen and Andrew M. Childs and Mohammad Hafezi and Zhang Jiang and Hwanmun Kim and Yijia Xu} } @article {3064, title = {Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation}, year = {2022}, month = {5/2/2022}, abstract = {

Nonlinear differential equations exhibit rich phenomena in many fields but are notoriously challenging to solve. Recently, Liu et al. [1] demonstrated the first efficient quantum algorithm for dissipative quadratic differential equations under the condition R\<1, where R measures the ratio of nonlinearity to dissipation using the l2 norm. Here we develop an efficient quantum algorithm based on [1] for reaction-diffusion equations, a class of nonlinear partial differential equations (PDEs). To achieve this, we improve upon the Carleman linearization approach introduced in [1] to obtain a faster convergence rate under the condition RD\<1, where RD measures the ratio of nonlinearity to dissipation using the l\∞ norm. Since RD is independent of the number of spatial grid points n while R increases with n, the criterion RD\<1 is significantly milder than R\<1 for high-dimensional systems and can stay convergent under grid refinement for approximating PDEs. As applications of our quantum algorithm we consider the Fisher-KPP and Allen-Cahn equations, which have interpretations in classical physics. In particular, we show how to estimate the mean square kinetic energy in the solution by postprocessing the quantum state that encodes it to extract derivative information.

}, url = {https://arxiv.org/abs/2205.01141}, author = {Dong An and Di Fang and Stephen Jordan and Jin-Peng Liu and Guang Hao Low and Jiasu Wang} } @article {3153, title = {Error-correcting codes for fermionic quantum simulation}, year = {2022}, month = {10/16/2022}, abstract = {

We provide ways to simulate fermions by qubits on 2d lattices using Z2 gauge theories (stabilizer codes). By studying the symplectic automorphisms of the Pauli module over the Laurent polynomial ring, we develop a systematic way to increase the code distances of stabilizer codes. We identify a family of stabilizer codes that can be used to simulate fermions with code distances of d=2,3,4,5,6,7 such that any \⌊d\−12\⌋-qubit error can be corrected. In particular, we demonstrate three stabilizer codes with code distances of d=3, d=4, and d=5, respectively, with all stabilizers and logical operators shown explicitly. The syndromes for all Pauli errors are provided. Finally, we introduce a syndrome-matching method to compute code distances numerically.

}, keywords = {FOS: Mathematics, FOS: Physical sciences, Mathematical Physics (math-ph), Quantum Algebra (math.QA), Quantum Physics (quant-ph), Strongly Correlated Electrons (cond-mat.str-el)}, doi = {10.48550/ARXIV.2210.08411}, url = {https://arxiv.org/abs/2210.08411}, author = {Chen, Yu-An and Alexey V. Gorshkov and Xu, Yijia} } @article {3081, title = {Estimating gate complexities for the site-by-site preparation of fermionic vacua}, year = {2022}, month = {07/04/2022}, abstract = {

An important aspect of quantum simulation is the preparation of physically interesting states on a quantum computer, and this task can often be costly or challenging to implement. A digital, {\textquoteleft}{\textquoteleft}site-by-site\&$\#$39;\&$\#$39; scheme of state preparation was introduced in arXiv:1911.03505 as a way to prepare the vacuum state of certain fermionic field theory Hamiltonians with a mass gap. More generally, this algorithm may be used to prepare ground states of Hamiltonians by adding one site at a time as long as successive intermediate ground states share a non-zero overlap and the Hamiltonian has a non-vanishing spectral gap at finite lattice size. In this paper, we study the ground state overlap as a function of the number of sites for a range of quadratic fermionic Hamiltonians. Using analytical formulas known for free fermions, we are able to explore the large-N behavior and draw conclusions about the state overlap. For all models studied, we find that the overlap remains large (e.g. \>0.1) up to large lattice sizes (N=64,72) except near quantum phase transitions or in the presence of gapless edge modes. For one-dimensional systems, we further find that two N/2-site ground states also share a large overlap with the N-site ground state everywhere except a region near the phase boundary. Based on these numerical results, we additionally propose a recursive alternative to the site-by-site state preparation algorithm.

}, url = {https://arxiv.org/abs/2207.01692}, author = {Troy Sewell and Aniruddha Bapat and Stephen Jordan} } @article {3016, title = {Euler-obstructed Cooper pairing: Nodal superconductivity and hinge Majorana zero modes}, journal = {Physical Review B}, volume = {105}, year = {2022}, month = {3/29/2022}, abstract = {

Since the proposal of monopole Cooper pairing in [Phys. Rev. Lett. 120, 067003 (2018)], considerable research efforts have been dedicated to the study of Cooper pairing order parameters constrained (or obstructed) by the nontrivial normal-state band topology at Fermi surfaces in 3D systems. In the current work, we generalize the topologically obstructed pairings between Chern states (like the monopole Cooper pairing) by proposing Euler obstructed Cooper pairing in 3D systems. The Euler obstructed Cooper pairing widely exists between two Fermi surfaces with nontrivial band topology characterized by nonzero Euler numbers; such Fermi surfaces can exist in 3D PT-protected spinless-Dirac/nodal-line semimetals with negligible spin-orbit coupling, where PT is the space-time inversion symmetry. An Euler obstructed pairing channel must have pairing nodes on the pairing-relevant Fermi surfaces, and the total winding number of the pairing nodes is determined by the sum or difference of the Euler numbers on the Fermi surfaces. In particular, we find that when the normal state is time-reversal invariant and the pairing is weak, a sufficiently-dominant Euler obstructed pairing channel with zero total momentum leads to nodal superconductivity. If the Fermi surface splitting is small, the resultant nodal superconductor hosts hinge Majorana zero modes. The possible dominance of the Euler obstructed pairing channel near the superconducting transition and the robustness of the hinge Majorana zero modes against disorder are explicitly demonstrated using effective or tight-binding models. Our work presents the first class of higher-order nodal superconductivity originating from the topologically obstructed Cooper pairing.

}, doi = {https://doi.org/10.1103\%2Fphysrevb.105.104515}, url = {https://arxiv.org/abs/2109.02685}, author = {Jiabin Yu and Yu-An Chen and Sankar Das Sarma} } @article {3139, title = {Experimental Implementation of an Efficient Test of Quantumness}, year = {2022}, month = {9/28/2022}, abstract = {

A test of quantumness is a protocol where a classical user issues challenges to a quantum device to determine if it exhibits non-classical behavior, under certain cryptographic assumptions. Recent attempts to implement such tests on current quantum computers rely on either interactive challenges with efficient verification, or non-interactive challenges with inefficient (exponential time) verification. In this paper, we execute an efficient non-interactive test of quantumness on an ion-trap quantum computer. Our results significantly exceed the bound for a classical device\&$\#$39;s success.

}, keywords = {FOS: Physical sciences, Other Condensed Matter (cond-mat.other), Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2209.14316}, url = {https://arxiv.org/abs/2209.14316}, author = {Lewis, Laura and Zhu, Daiwei and Gheorghiu, Alexandru and Noel, Crystal and Katz, Or and Harraz, Bahaa and Wang, Qingfeng and Risinger, Andrew and Feng, Lei and Biswas, Debopriyo and Egan, Laird and Vidick, Thomas and Cetina, Marko and Monroe, Christopher} } @article {3002, title = {Experimental observation of thermalisation with noncommuting charges}, year = {2022}, month = {2/9/2022}, abstract = {

Quantum simulators have recently enabled experimental observations of quantum many-body systems\&$\#$39; internal thermalisation. Often, the global energy and particle number are conserved, and the system is prepared with a well-defined particle number - in a microcanonical subspace. However, quantum evolution can also conserve quantities, or charges, that fail to commute with each other. Noncommuting charges have recently emerged as a subfield at the intersection of quantum thermodynamics and quantum information. Until now, this subfield has remained theoretical. We initiate the experimental testing of its predictions, with a trapped-ion simulator. We prepare 6-15 spins in an approximate microcanonical subspace, a generalisation of the microcanonical subspace for accommodating noncommuting charges, which cannot necessarily have well-defined nontrivial values simultaneously. We simulate a Heisenberg evolution using laser-induced entangling interactions and collective spin rotations. The noncommuting charges are the three spin components. We find that small subsystems equilibrate to near a recently predicted non-Abelian thermal state. This work bridges quantum many-body simulators to the quantum thermodynamics of noncommuting charges, whose predictions can now be tested.

}, keywords = {FOS: Physical sciences, Quantum Physics (quant-ph), Statistical Mechanics (cond-mat.stat-mech)}, doi = {10.48550/ARXIV.2202.04652}, url = {https://arxiv.org/abs/2202.04652}, author = {Kranzl, Florian and Lasek, Aleksander and Joshi, Manoj K. and Kalev, Amir and Blatt, Rainer and Roos, Christian F. and Nicole Yunger Halpern} } @article {3077, title = {Experimentally Measuring Rolling and Sliding in Three-Dimensional Dense Granular Packings}, journal = {Phys. Rev. Lett.}, volume = {129}, year = {2022}, month = {06/18/2022}, pages = {048001}, abstract = {

We experimentally measure a three-dimensional (3D) granular system\’s reversibility under cyclic compression. We image the grains using a refractive-index-matched fluid, then analyze the images using the artificial intelligence of variational autoencoders. These techniques allow us to track all the grains\’ translations and 3D rotations with accuracy sufficient to infer sliding and rolling displacements. Our observations reveal unique roles played by 3D rotational motions in granular flows. We find that rotations and contact-point motion dominate the dynamics in the bulk, far from the perturbation\’s source. Furthermore, we determine that 3D rotations are irreversible under cyclic compression. Consequently, contact-point sliding, which is dissipative, accumulates throughout the cycle. Using numerical simulations whose accuracy our experiment supports, we discover that much of the dissipation occurs in the bulk, where grains rotate more than they translate. Our observations suggest that the analysis of 3D rotations is needed for understanding granular materials\’ unique and powerful ability to absorb and dissipate energy.

}, doi = {https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.129.048001}, url = {https://arxiv.org/abs/2108.11975}, author = {Zackery A. Benson and Anton Peshkov and Nicole Yunger Halpern and Derek C. Richardson and Wolfgang Losert} } @article {3122, title = {Extracting Wilson loop operators and fractional statistics from a single bulk ground state}, year = {2022}, month = {9/28/2022}, abstract = {

An essential aspect of topological phases of matter is the existence of Wilson loop operators that keep the ground state subspace invariant. Here we present and implement an unbiased numerical optimization scheme to systematically find the Wilson loop operators given a single ground state wave function of a gapped Hamiltonian on a disk. We then show how these Wilson loop operators can be cut and glued through further optimization to give operators that can create, move, and annihilate anyon excitations. We subsequently use these operators to determine the braiding statistics and topological twists of the anyons, yielding a way to fully extract topological order from a single wave function. We apply our method to the ground state of the perturbed toric code and doubled semion models with a magnetic field that is up to a half of the critical value. From a contemporary perspective, this can be thought of as a machine learning approach to discover emergent 1-form symmetries of a ground state wave function. From an application perspective, our approach can be relevant to find Wilson loop operators in current quantum simulators.

}, keywords = {FOS: Physical sciences, Quantum Physics (quant-ph), Strongly Correlated Electrons (cond-mat.str-el)}, doi = {10.48550/ARXIV.2209.14302}, url = {https://arxiv.org/abs/2209.14302}, author = {Cian, Ze-Pei and Hafezi, Mohammad and Barkeshli, Maissam} } @article {2881, title = {EasyPQC: Verifying Post-Quantum Cryptography}, journal = {ACM CCS 2021}, year = {2021}, month = {9/20/2021}, abstract = {

EasyCrypt is a formal verification tool used extensively for formalizing concrete security proofs of cryptographic constructions. However, the EasyCrypt formal logics consider only classical attackers, which means that post-quantum security proofs cannot be formalized and machine-checked with this tool. In this paper we prove that a natural extension of the EasyCrypt core logics permits capturing a wide class of post-quantum cryptography proofs, settling a question raised by (Unruh, POPL 2019). Leveraging our positive result, we implement EasyPQC, an extension of EasyCrypt for post-quantum security proofs, and use EasyPQC to verify post-quantum security of three classic constructions: PRF-based MAC, Full Domain Hash and GPV08 identity-based encryption.

}, doi = {https://dx.doi.org/10.1145/3460120.3484567}, author = {Manuel Barbosa and Gilles Barthe and Xiong Fan and Benjamin Gr{\'e}goire and Shih-Han Hung and Jonathan Katz and Pierre-Yves Strub and Xiaodi Wu and Li Zhou} } @article {2700, title = {Efficient quantum algorithm for dissipative nonlinear differential equations}, journal = {Proceedings of the National Academy of Sciences}, volume = {118}, year = {2021}, month = {3/1/2021}, chapter = {e2026805118}, abstract = {

While there has been extensive previous work on efficient quantum algorithms for linear differential equations, analogous progress for nonlinear differential equations has been severely limited due to the linearity of quantum mechanics. Despite this obstacle, we develop a quantum algorithm for initial value problems described by dissipative quadratic n-dimensional ordinary differential equations. Assuming R\<1, where R is a parameter characterizing the ratio of the nonlinearity to the linear dissipation, this algorithm has complexity T2poly(logT,logn)/ϵ, where T is the evolution time and ϵ is the allowed error in the output quantum state. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. We achieve this improvement using the method of Carleman linearization, for which we give an improved convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for R\≥2\–\√. Finally, we discuss potential applications of this approach to problems arising in biology as well as in fluid and plasma dynamics.

}, doi = {https://doi.org/10.1073/pnas.2026805118}, url = {https://arxiv.org/abs/2011.03185}, author = {Jin-Peng Liu and Herman {\O}ie Kolden and Hari K. Krovi and Nuno F. Loureiro and Konstantina Trivisa and Andrew M. Childs} } @article {2426, title = {Efficient quantum measurement of Pauli operators}, journal = {Quantum}, volume = {5}, year = {2021}, month = {01/19/2021}, chapter = {385}, abstract = {

Estimating the expectation value of an observable is a fundamental task in quantum computation. Unfortunately, it is often impossible to obtain such estimates directly, as the computer is restricted to measuring in a fixed computational basis. One common solution splits the observable into a weighted sum of Pauli operators and measures each separately, at the cost of many measurements. An improved version first groups mutually commuting Pauli operators together and then measures all operators within each group simultaneously. The effectiveness of this depends on two factors. First, to enable simultaneous measurement, circuits are required to rotate each group to the computational basis. In our work, we present two efficient circuit constructions that suitably rotate any group of k commuting n-qubit Pauli operators using at most kn\−k(k+1)/2 and O(kn/logk) two-qubit gates respectively. Second, metrics that justifiably measure the effectiveness of a grouping are required. In our work, we propose two natural metrics that operate under the assumption that measurements are distributed optimally among groups. Motivated by our new metrics, we introduce SORTED INSERTION, a grouping strategy that is explicitly aware of the weighting of each Pauli operator in the observable. Our methods are numerically illustrated in the context of the Variational Quantum Eigensolver, where the observables in question are molecular Hamiltonians. As measured by our metrics, SORTED INSERTION outperforms four conventional greedy colouring algorithms that seek the minimum number of groups.

}, doi = {https://doi.org/10.22331/q-2021-01-20-385}, url = {https://arxiv.org/abs/1908.06942}, author = {Ophelia Crawford and Barnaby van Straaten and Daochen Wang and Thomas Parks and Earl Campbell and Stephen Brierley} } @article {2821, title = {Efficient quantum programming using EASE gates on a trapped-ion quantum computer}, year = {2021}, month = {7/15/2021}, abstract = {

Parallel operations in conventional computing have proven to be an essential tool for efficient and practical computation, and the story is not different for quantum computing. Indeed, there exists a large body of works that study advantages of parallel implementations of quantum gates for efficient quantum circuit implementations. Here, we focus on the recently invented efficient, arbitrary, simultaneously entangling (EASE) gates, available on a trapped-ion quantum computer. Leveraging its flexibility in selecting arbitrary pairs of qubits to be coupled with any degrees of entanglement, all in parallel, we show a n-qubit Clifford circuit can be implemented using 6log(n) EASE gates, a n-qubit multiply-controlled NOT gate can be implemented using 3n/2 EASE gates, and a n-qubit permutation can be implemented using six EASE gates. We discuss their implications to near-term quantum chemistry simulations and the state of the art pattern matching algorithm. Given Clifford + multiply-controlled NOT gates form a universal gate set for quantum computing, our results imply efficient quantum computation by EASE gates, in general.

}, url = {https://arxiv.org/abs/2107.07591}, author = {Nikodem Grzesiak and Andrii Maksymov and Pradeep Niroula and Yunseong Nam} } @article {2725, title = {Energy storage and coherence in closed and open quantum batteries}, journal = {Quantum}, volume = {5}, year = {2021}, month = {7/15/2021}, pages = {505}, abstract = {

We study the role of coherence in closed and open quantum batteries. We obtain upper bounds to the work performed or energy exchanged by both closed and open quantum batteries in terms of coherence. Specifically, we show that the energy storage can be bounded by the Hilbert-Schmidt coherence of the density matrix in the spectral basis of the unitary operator that encodes the evolution of the battery. We also show that an analogous bound can be obtained in terms of the battery\&$\#$39;s Hamiltonian coherence in the basis of the unitary operator by evaluating their commutator. We apply these bounds to a 4-state quantum system and the anisotropic XY Ising model in the closed system case, and the Spin-Boson model in the open case.\ 

}, doi = {https://doi.org/10.22331/q-2021-07-15-505}, url = {https://arxiv.org/abs/2012.15026}, author = {Francesco Caravelli and Bin Yan and Luis Pedro Garc{\'\i}a-Pintos and Alioscia Hamma} } @article {2932, title = {Entangled quantum cellular automata, physical complexity, and Goldilocks rules}, journal = {Quantum Science and Technology}, volume = {6}, year = {2021}, month = {9/29/2021}, pages = {045017}, abstract = {

Cellular automata are interacting classical bits that display diverse emergent behaviors, from fractals to random-number generators to Turing-complete computation. We discover that quantum cellular automata (QCA) can exhibit complexity in the sense of the complexity science that describes biology, sociology, and economics. QCA exhibit complexity when evolving under \"Goldilocks rules\" that we define by balancing activity and stasis. Our Goldilocks rules generate robust dynamical features (entangled breathers), network structure and dynamics consistent with complexity, and persistent entropy fluctuations. Present-day experimental platforms -- Rydberg arrays, trapped ions, and superconducting qubits -- can implement our Goldilocks protocols, making testable the link between complexity science and quantum computation exposed by our QCA.

}, issn = {2058-9565}, doi = {10.1088/2058-9565/ac1c41}, url = {http://dx.doi.org/10.1088/2058-9565/ac1c41}, author = {Hillberry, Logan E and Jones, Matthew T and Vargas, David L and Rall, Patrick and Nicole Yunger Halpern and Bao, Ning and Notarnicola, Simone and Montangero, Simone and Carr, Lincoln D} } @article {2724, title = {Entanglement and purification transitions in non-Hermitian quantum mechanics}, journal = {Phys. Rev. Lett., in press}, year = {2021}, month = {12/2/2020}, abstract = {

A quantum system subject to continuous measurement and post-selection evolves according to a non-Hermitian Hamiltonian. We show that, as one increases the rate of post-selection, this non-Hermitian Hamiltonian undergoes a spectral phase transition. On one side of this phase transition (for weak post-selection) an initially mixed density matrix remains mixed at all times, and an initially unentangled state develops volume-law entanglement; on the other side, an arbitrary initial state approaches a unique pure state with low entanglement. We identify this transition with an exceptional point in the spectrum of the non-Hermitian Hamiltonian, at which PT symmetry is spontaneously broken. We characterize the transition as well as the nontrivial steady state that emerges at late times in the mixed phase using exact diagonalization and an approximate, analytically tractable mean-field theory; these methods yield consistent conclusions.

}, url = {https://arxiv.org/abs/2012.01435}, author = {Sarang Gopalakrishnan and Michael Gullans} } @article {2776, title = {Entanglement Phase Transitions in Measurement-Only Dynamics}, journal = {Physical Review X}, volume = {11}, year = {2021}, month = {1/2/2021}, abstract = {

Unitary circuits subject to repeated projective measurements can undergo an entanglement phase transition (EPT) as a function of the measurement rate. This transition is generally understood in terms of a competition between the scrambling effects of unitary dynamics and the disentangling effects of measurements. We find that, surprisingly, EPTs are possible even in the absence of scrambling unitary dynamics, where they are best understood as arising from measurements alone. This motivates us to introduce \emph{measurement-only models}, in which the \"scrambling\" and \"un-scrambling\" effects driving the EPT are fundamentally intertwined and cannot be attributed to physically distinct processes. This represents a novel form of an EPT, conceptually distinct from that in hybrid unitary-projective circuits. We explore the entanglement phase diagrams, critical points, and quantum code properties of some of these measurement-only models. We find that the principle driving the EPTs in these models is \emph{frustration}, or mutual incompatibility, of the measurements. Suprisingly, an entangling (volume-law) phase is the generic outcome when measuring sufficiently long but still local (≳3-body) operators. We identify a class of exceptions to this behavior (\"bipartite ensembles\") which cannot sustain an entangling phase, but display dual area-law phases, possibly with different kinds of quantum order, separated by self-dual critical points. Finally, we introduce a measure of information spreading in dynamics with measurements and use it to demonstrate the emergence of a statistical light-cone, despite the non-locality inherent to quantum measurements.

}, doi = {10.1103/PhysRevX.11.011030}, url = {https://arxiv.org/abs/2004.09560}, author = {Ippoliti, Matteo and Michael Gullans and Gopalakrishnan, Sarang and Huse, David A. and Khemani, Vedika} } @article {2872, title = {Estimating distinguishability measures on quantum computers}, year = {2021}, month = {8/18/2021}, abstract = {

The performance of a quantum information processing protocol is ultimately judged by distinguishability measures that quantify how distinguishable the actual result of the protocol is from the ideal case. The most prominent distinguishability measures are those based on the fidelity and trace distance, due to their physical interpretations. In this paper, we propose and review several algorithms for estimating distinguishability measures based on trace distance and fidelity, and we evaluate their performance using simulators of quantum computers. The algorithms can be used for distinguishing quantum states, channels, and strategies (the last also known in the literature as \"quantum combs\"). The fidelity-based algorithms offer novel physical interpretations of these distinguishability measures in terms of the maximum probability with which a single prover (or competing provers) can convince a verifier to accept the outcome of an associated computation. We simulate these algorithms by using a variational approach with parameterized quantum circuits and find that they converge well for the examples that we consider.\ 

}, url = {https://arxiv.org/abs/2108.08406}, author = {Rochisha Agarwal and Soorya Rethinasamy and Kunal Sharma and Mark M. Wilde} } @article {2928, title = {Exactly Solvable Lattice Hamiltonians and Gravitational Anomalies}, year = {2021}, month = {10/27/2021}, abstract = {

We construct infinitely many new exactly solvable local commuting projector lattice Hamiltonian models for general bosonic beyond group cohomology invertible topological phases of order two and four in any spacetime dimensions, whose boundaries are characterized by gravitational anomalies. Examples include the beyond group cohomology invertible phase without symmetry in (4+1)D that has an anomalous boundary Z2 topological order with fermionic particle and fermionic loop excitations that have mutual π statistics. We argue that this construction gives a new non-trivial quantum cellular automaton (QCA) in (4+1)D of order two. We also present an explicit construction of gapped symmetric boundary state for the bosonic beyond group cohomology invertible phase with unitary Z2 symmetry in (4+1)D. We discuss new quantum phase transitions protected by different invertible phases across the transitions.

}, url = {https://arxiv.org/abs/2110.14644}, author = {Yu-An Chen and Po-Shen Hsin} } @conference {2941, title = {Expanding the VOQC Toolkit}, booktitle = {The Second International Workshop on Programming Languages for Quantum Computing (PLanQC 2021)}, year = {2021}, month = {06/2021}, abstract = {

voqc [Hietala et al. 2021b] (pronounced \“vox\”) is a compiler for quantum circuits, in the style of
tools like Qiskit [Aleksandrowicz et al. 2019], tket [Cambridge Quantum Computing Ltd 2019],
Quilc [Rigetti Computing 2019], and Cirq [Developers 2021]. What makes voqc different from these
tools is that it has been formally verified in the Coq proof assistant [Coq Development Team 2019].
voqc source programs are expressed in sqir, a simple quantum intermediate representation, which
has a precise mathematical semantics. We use Gallina, Coq\’s programming language, to implement
voqc transformations over sqir programs, and use Coq to prove the source program\’s semantics
are preserved. We then extract these Gallina definitions to OCaml, and compile the OCaml code to
a library that can operate on standard-formatted circuits.
voqc, and sqir, were built to be general-purpose. For example, while we originally designed sqir
for use in verified optimizations, we subsequently found sqir could also be suitable for writing, and
proving correct, source programs [Hietala et al. 2021a]. We have continued to develop the voqc
codebase to expand its reach and utility.
In this abstract, we present new extensions to voqc as an illustration of its flexibility. These
include support for calling voqc transformations from Python, added support for new gate sets
and optimizations, and the extension of our notion of correctness to include mapping-preservation,
which allows us to apply optimizations after mapping, reducing the cost introduced by making a
program conform to hardware constraints.

}, url = {http://rand.cs.uchicago.edu/files/planqc_2021c.pdf}, author = {Kesha Hietala and Liyi Li and Akshaj Gaur and Aaron Green and Robert Rand and Xiaodi Wu and Michael Hicks} } @article {2877, title = {An explicit vector algorithm for high-girth MaxCut}, year = {2021}, month = {8/27/2021}, abstract = {

We give an approximation algorithm for MaxCut and provide guarantees on the average fraction of edges cut on d-regular graphs of girth \≥2k. For every d\≥3 and k\≥4, our approximation guarantees are better than those of all other classical and quantum algorithms known to the authors. Our algorithm constructs an explicit vector solution to the standard semidefinite relaxation of MaxCut and applies hyperplane rounding. It may be viewed as a simplification of the previously best known technique, which approximates Gaussian wave processes on the infinite d-regular tree.

}, url = {https://arxiv.org/abs/2108.12477}, author = {Jessica K. Thompson and Ojas Parekh and Kunal Marwaha} } @article {2756, title = {Exploiting anticommutation in Hamiltonian simulation}, year = {2021}, month = {3/14/2021}, abstract = {

Quantum computing can efficiently simulate Hamiltonian dynamics of many-body quantum physics, a task that is generally intractable with classical computers. The hardness lies at the ubiquitous anti-commutative relations of quantum operators, in corresponding with the notorious negative sign problem in classical simulation. Intuitively, Hamiltonians with more commutative terms are also easier to simulate on a quantum computer, and anti-commutative relations generally cause more errors, such as in the product formula method. Here, we theoretically explore the role of anti-commutative relation in Hamiltonian simulation. We find that, contrary to our intuition, anti-commutative relations could also reduce the hardness of Hamiltonian simulation. Specifically, Hamiltonians with mutually anti-commutative terms are easy to simulate, as what happens with ones consisting of mutually commutative terms. Such a property is further utilized to reduce the algorithmic error or the gate complexity in the truncated Taylor series quantum algorithm for general problems. Moreover, we propose two modified linear combinations of unitaries methods tailored for Hamiltonians with different degrees of anti-commutation. We numerically verify that the proposed methods exploiting anti-commutative relations could significantly improve the simulation accuracy of electronic Hamiltonians. Our work sheds light on the roles of commutative and anti-commutative relations in simulating quantum systems.

}, url = {https://arxiv.org/abs/2103.07988}, author = {Qi Zhao and Xiao Yuan} } @article {2860, title = {Exponentially Many Local Minima in Quantum Neural Networks}, journal = {Proceedings of the 38th International Conference on Machine Learning, PMLR}, volume = {139}, year = {2021}, month = {10/5/2021}, pages = {12144-12155}, abstract = {

Quantum Neural Networks (QNNs), or the so-called variational quantum circuits, are important quantum applications both because of their similar promises as classical neural networks and because of the feasibility of their implementation on near-term intermediate-size noisy quantum machines (NISQ). However, the training task of QNNs is challenging and much less understood. We conduct a quantitative investigation on the landscape of loss functions of QNNs and identify a class of simple yet extremely hard QNN instances for training. Specifically, we show for typical under-parameterized QNNs, there exists a dataset that induces a loss function with the number of spurious local minima depending exponentially on the number of parameters. Moreover, we show the optimality of our construction by providing an almost matching upper bound on such dependence. While local minima in classical neural networks are due to non-linear activations, in quantum neural networks local minima appear as a result of the quantum interference phenomenon. Finally, we empirically confirm that our constructions can indeed be hard instances in practice with typical gradient-based optimizers, which demonstrates the practical value of our findings.\ 

}, url = {https://arxiv.org/pdf/2110.02479.pdf}, author = {Xuchen You and Xiaodi Wu} } @article {2584, title = {Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians}, year = {2020}, month = {4/21/2020}, abstract = {

All known examples confirming the possibility of an exponential separation between classical simulation algorithms and stoquastic adiabatic quantum computing (AQC) exploit symmetries that constrain adiabatic dynamics to effective, symmetric subspaces. The symmetries produce large effective eigenvalue gaps, which in turn make adiabatic computation efficient. We present a classical algorithm to efficiently sample from the effective subspace of a k-local stoquastic Hamiltonian H, without a priori knowledge of its symmetries (or near-symmetries). Our algorithm maps any k-local Hamiltonian to a graph G=(V,E) with |V|=O(poly(n)) where n is the number of qubits. Given the well-known result of Babai, we exploit graph isomorphism to study the automorphisms of G and arrive at an algorithm quasi-polynomial in |V| for producing samples from the effective subspace eigenstates of H. Our results rule out exponential separations between stoquastic AQC and classical computation that arise from hidden symmetries in k-local Hamiltonians. Furthermore, our graph representation of H is not limited to stoquastic Hamiltonians and may rule out corresponding obstructions in non-stoquastic cases, or be useful in studying additional properties of k-local Hamiltonians.

}, url = {https://arxiv.org/abs/2004.08681}, author = {Jacob Bringewatt and Michael Jarret} } @article {2540, title = {Efficient randomness certification by quantum probability estimation}, journal = {Phys. Rev. Research }, volume = {2}, year = {2020}, month = {1/7/2020}, abstract = {

For practical applications of quantum randomness generation, it is important to certify and further produce a fixed block of fresh random bits with as few trials as possible. Consequently, protocols with high finite-data efficiency are preferred. To yield such protocols with respect to quantum side information, we develop quantum probability estimation. Our approach is applicable to device-independent as well as device-dependent scenarios, and it generalizes techniques from previous works [Miller and Shi, SIAM J. Comput. 46, 1304 (2017); Arnon-Friedman et al., Nat. Commun. 9, 459 (2018)]. Quantum probability estimation can adapt to changing experimental conditions, allows stopping the experiment as soon as the prespecified randomness goal is achieved, and can tolerate imperfect knowledge of the input distribution. Moreover, the randomness rate achieved at constant error is asymptotically optimal. For the device-independent scenario, our approach certifies the amount of randomness available in experimental results without first searching for relations between randomness and violations of fixed Bell inequalities. We implement quantum probability estimation for device-independent randomness generation in the CHSH Bell-test configuration, and we show significant improvements in finite-data efficiency, particularly at small Bell violations which are typical in current photonic loophole-free Bell tests.

}, doi = {https://doi.org/10.1103/PhysRevResearch.2.013016}, author = {Yanbao Zhang and Honghao Fu and Emanuel Knill} } @article {2627, title = {Efficient Simulation of Random States and Random Unitaries}, journal = {In: Canteaut A., Ishai Y. (eds) Advances in Cryptology {\textendash} EUROCRYPT 2020. Lecture Notes in Computer Science, Springer, Cham}, volume = {12107}, year = {2020}, month = {5/1/2020}, pages = {759-787}, type = {inproceedings}, abstract = {

We consider the problem of efficiently simulating random quantum states and random unitary operators, in a manner which is convincing to unbounded adversaries with black-box oracle access.

This problem has previously only been considered for restricted adversaries. Against adversaries with an a priori bound on the number of queries, it is well-known that t-designs suffice. Against polynomial-time adversaries, one can use pseudorandom states (PRS) and pseudorandom unitaries (PRU), as defined in a recent work of Ji, Liu, and Song; unfortunately, no provably secure construction is known for PRUs.

In our setting, we are concerned with unbounded adversaries. Nonetheless, we are able to give stateful quantum algorithms which simulate the ideal object in both settings of interest. In the case of Haar-random states, our simulator is polynomial-time, has negligible error, and can also simulate verification and reflection through the simulated state. This yields an immediate application to quantum money: a money scheme which is information-theoretically unforgeable and untraceable. In the case of Haar-random unitaries, our simulator takes polynomial space, but simulates both forward and inverse access with zero error.

These results can be seen as the first significant steps in developing a theory of lazy sampling for random quantum objects.

}, doi = {https://doi.org/10.1007/978-3-030-45727-3_26}, author = {Gorjan Alagic and Christian Majenz and Alexander Russell} } @article {2331, title = {Efficiently computable bounds for magic state distillation}, journal = {Phys. Rev. Lett. }, volume = {124}, year = {2020}, month = {3/6/2020}, abstract = {

Magic state manipulation is a crucial component in the leading approaches to realizing scalable, fault-tolerant, and universal quantum computation. Related to magic state manipulation is the resource theory of magic states, for which one of the goals is to characterize and quantify quantum \"magic.\" In this paper, we introduce the family of thauma measures to quantify the amount of magic in a quantum state, and we exploit this family of measures to address several open questions in the resource theory of magic states. As a first application, we use the min-thauma to bound the regularized relative entropy of magic. As a consequence of this bound, we find that two classes of states with maximal mana, a previously established magic measure, cannot be interconverted in the asymptotic regime at a rate equal to one. This result resolves a basic question in the resource theory of magic states and reveals a fundamental difference between the resource theory of magic states and other resource theories such as entanglement and coherence. As a second application, we establish the hypothesis testing thauma as an efficiently computable benchmark for the one-shot distillable magic, which in turn leads to a variety of bounds on the rate at which magic can be distilled, as well as on the overhead of magic state distillation. Finally, we prove that the max-thauma can outperform mana in benchmarking the efficiency of magic state distillation.\ 

}, doi = {https://doi.org/10.1103/PhysRevLett.124.090505}, url = {https://arxiv.org/abs/1812.10145}, author = {Xin Wang and Mark M. Wilde and Yuan Su} } @article {2457, title = {Entanglement Bounds on the Performance of Quantum Computing Architectures}, journal = {Phys. Rev. Research}, volume = {2}, year = {2020}, month = {9/22/2020}, abstract = {

There are many possible architectures for future quantum computers that designers will need to choose between. However, the process of evaluating a particular connectivity graph\&$\#$39;s performance as a quantum architecture can be difficult. In this paper, we establish a connection between a quantity known as the isoperimetric number and a lower bound on the time required to create highly entangled states. The metric we propose counts resources based on the use of two-qubit unitary operations, while allowing for arbitrarily fast measurements and classical feedback. We describe how these results can be applied to the evaluation of the hierarchical architecture proposed in Phys. Rev. A 98, 062328 (2018). We also show that the time-complexity bound we place on the creation of highly-entangled states can be saturated up to a multiplicative factor logarithmic in the number of qubits.

}, doi = {https://doi.org/10.1103/PhysRevResearch.2.033316}, url = {https://arxiv.org/abs/1908.04802}, author = {Zachary Eldredge and Leo Zhou and Aniruddha Bapat and James R. Garrison and Abhinav Deshpande and Frederic T. Chong and Alexey V. Gorshkov} } @article {2677, title = {Entanglement entropy scaling transition under competing monitoring protocols}, year = {2020}, month = {08/19/2020}, abstract = {

Dissipation generally leads to the decoherence of a quantum state. In contrast, numerous recent proposals have illustrated that dissipation can also be tailored to stabilize many-body entangled quantum states. While the focus of these works has been primarily on engineering the non-equilibrium steady state, we investigate the build-up of entanglement in the quantum trajectories. Specifically, we analyze the competition between two different dissipation channels arising from two incompatible continuous monitoring protocols. The first protocol locks the phase of neighboring sites upon registering a quantum jump, thereby generating a long-range entanglement through the system, while the second one destroys the coherence via dephasing mechanism. By studying the unraveling of stochastic quantum trajectories associated with the continuous monitoring protocols, we present a transition for the scaling of the averaged trajectory entanglement entropies, from critical scaling to area-law behavior. Our work provides novel insights into the occurrence of a measurement-induced phase transition within a continuous monitoring protocol.

}, url = {https://arxiv.org/abs/2008.08619}, author = {Mathias Van Regemortel and Ze-Pei Cian and Alireza Seif and Hossein Dehghani and Mohammad Hafezi} } @article {2567, title = {Exotic photonic molecules via Lennard-Jones-like potentials}, journal = {Phys. Rev. Lett.}, volume = {125}, year = {2020}, month = {9/19/2020}, abstract = {

Ultracold systems offer an unprecedented level of control of interactions between atoms. An important challenge is to achieve a similar level of control of the interactions between photons. Towards this goal, we propose a realization of a novel Lennard-Jones-like potential between photons coupled to the Rydberg states via electromagnetically induced transparency (EIT). This potential is achieved by tuning Rydberg states to a F{{\"o}}rster resonance with other Rydberg states. We consider few-body problems in 1D and 2D geometries and show the existence of self-bound clusters (\"molecules\") of photons. We demonstrate that for a few-body problem, the multi-body interactions have a significant impact on the geometry of the molecular ground state. This leads to phenomena without counterparts in conventional systems: For example, three photons in 2D preferentially arrange themselves in a line-configuration rather than in an equilateral-triangle configuration. Our result opens a new avenue for studies of many-body phenomena with strongly interacting photons.

}, doi = {https://doi.org/10.1103/PhysRevLett.125.093601}, url = {https://arxiv.org/abs/2003.07864}, author = {Przemyslaw Bienias and Michael Gullans and Marcin Kalinowski and Alexander N. Craddock and Dalia P. Ornelas-Huerta and Steven L. Rolston and J. V. Porto and Alexey V. Gorshkov} } @article {2329, title = {Experimental Low-Latency Device-Independent Quantum Randomness}, journal = {Phys. Rev. Lett. }, volume = {124}, year = {2020}, month = {12/24/2019}, abstract = {

Applications of randomness such as private key generation and public randomness beacons require small blocks of certified random bits on demand. Device-independent quantum random number generators can produce such random bits, but existing quantum-proof protocols and loophole-free implementations suffer from high latency, requiring many hours to produce any random bits. We demonstrate device-independent quantum randomness generation from a loophole-free Bell test with a more efficient quantum-proof protocol, obtaining multiple blocks of 512 bits with an average experiment time of less than 5 min per block and with certified error bounded by 2\−64\≈5.42\×10\−20.

}, doi = {https://doi.org/10.1103/PhysRevLett.124.010505}, url = {https://arxiv.org/abs/1812.07786}, author = {Yanbao Zhang and Lynden K. Shalm and Joshua C. Bienfang and Martin J. Stevens and Michael D. Mazurek and Sae Woo Nam and Carlos Abell{\'a}n and Waldimar Amaya and Morgan W. Mitchell and Honghao Fu and Carl Miller and Alan Mink and Emanuel Knill} } @article {2640, title = {An exponential ramp in the quadratic Sachdev-Ye-Kitaev model}, year = {2020}, month = {6/26/2020}, abstract = {

A long period of linear growth in the spectral form factor provides a universal diagnostic of quantum chaos at intermediate times. By contrast, the behavior of the spectral form factor in disordered integrable many-body models is not well understood. Here we study the two-body Sachdev-Ye-Kitaev model and show that the spectral form factor features an exponential ramp, in sharp contrast to the linear ramp in chaotic models. We find a novel mechanism for this exponential ramp in terms of a high-dimensional manifold of saddle points in the path integral formulation of the spectral form factor. This manifold arises because the theory enjoys a large symmetry group. With finite nonintegrable interaction strength, these delicate symmetries reduce to a relative time translation, causing the exponential ramp to give way to a linear ramp.

}, url = {https://arxiv.org/abs/2006.15152}, author = {Michael Winer and Shao-Kai Jian and Brian Swingle} } @article {2405, title = {Equilibration to the non-Abelian thermal state in quantum many-body physics}, year = {2019}, month = {6/21/2019}, abstract = {

In statistical mechanics, a small system exchanges conserved charges---heat, particles, electric charge, etc.---with a bath. The small system thermalizes to the canonical ensemble, or the grand canonical ensemble, etc., depending on the charges. The charges are usually represented by operators assumed to commute with each other. This assumption was removed within quantum-information-theoretic (QI-theoretic) thermodynamics recently. The small system\&$\#$39;s long-time state was dubbed \"the non-Abelian thermal state (NATS).\" We propose an experimental protocol for observing a system thermalize to the NATS. We illustrate with a chain of spins, a subset of which form the system of interest. The conserved charges manifest as spin components. Heisenberg interactions push the charges between the system and the effective bath, the rest of the chain. We predict long-time expectation values, extending the NATS theory from abstract idealization to finite systems that thermalize with finite couplings for finite times. Numerical simulations support the analytics: The system thermalizes to the NATS, rather than to the canonical prediction. Our proposal can be implemented with ultracold atoms, nitrogen-vacancy centers, trapped ions, quantum dots, and perhaps nuclear magnetic resonance. This work introduces noncommuting charges from QI-theoretic thermodynamics into quantum many-body physics: atomic, molecular, and optical physics and condensed matter.\ 

}, url = {https://arxiv.org/abs/1906.09227}, author = {Nicole Yunger Halpern and Michael E. Beverland and Amir Kalev} } @article {1998, title = {Electro-mechano-optical NMR detection}, journal = {Optica}, volume = {5}, year = {2018}, month = {2018/02/01}, pages = {152-158}, abstract = {

Signal reception of nuclear magnetic resonance (NMR) usually relies on electrical amplification of the electromotive force caused by nuclear induction. Here, we report up-conversion of a radio-frequency NMR signal to an optical regime using a high-stress silicon nitride membrane that interfaces the electrical detection circuit and an optical cavity through the electro-mechanical and the opto-mechanical couplings. This enables optical NMR detection without sacrificing the versatility of the traditional nuclear induction approach. While the signal-to-noise ratio is currently limited by the Brownian motion of the membrane as well as additional technical noise, we find it can exceed that of the conventional electrical schemes by increasing the electro-mechanical coupling strength. The electro-mechano-optical NMR detection presented here can even be combined with the laser cooling technique applied to nuclear spins.

}, doi = {10.1364/OPTICA.5.000152}, url = {https://www.osapublishing.org/optica/abstract.cfm?uri=optica-5-2-152}, author = {Kazuyuki Takeda and Kentaro Nagasaka and Atsushi Noguchi and Rekishu Yamazaki and Yasunobu Nakamura and Eiji Iwase and J. M. Taylor and Koji Usami} } @article {2104, title = {Electro-optomechanical equivalent circuits for quantum transduction}, year = {2018}, month = {2018/10/15}, abstract = {

Using the techniques of optomechanics, a high-Q mechanical oscillator may serve as a link between electromagnetic modes of vastly different frequencies. This approach has successfully been exploited for the frequency conversion of classical signals and has the potential of performing quantum state transfer between superconducting circuitry and a traveling optical signal. Such transducers are often operated in a linear regime, where the hybrid system can be described using linear response theory based on the Heisenberg-Langevin equations. While mathematically straightforward to solve, this approach yields little intuition about the dynamics of the hybrid system to aid the optimization of the transducer. As an analysis and design tool for such electro-optomechanical transducers, we introduce an equivalent circuit formalism, where the entire transducer is represented by an electrical circuit. Thereby we integrate the transduction functionality of optomechanical (OM) systems into the toolbox of electrical engineering allowing the use of its well-established design techniques. This unifying impedance description can be applied both for static (DC) and harmonically varying (AC) drive fields, accommodates arbitrary linear circuits, and is not restricted to the resolved-sideband regime. Furthermore, by establishing the quantized input/output formalism for the equivalent circuit, we obtain the scattering matrix for linear transducers using circuit analysis, and thereby have a complete quantum mechanical characterization of the transducer. Hence, this mapping of the entire transducer to the language of electrical engineering both sheds light on how the transducer performs and can at the same time be used to optimize its performance by aiding the design of a suitable electrical circuit.

}, doi = {https://doi.org/10.1103/PhysRevApplied.10.044036}, url = {https://arxiv.org/abs/1710.10136}, author = {Emil Zeuthen and Albert Schliesser and J. M. Taylor and Anders S. S{\o}rensen} } @article {2315, title = {Energy-level statistics in strongly disordered systems with power-law hopping}, journal = {Phys. Rev. }, volume = {B}, year = {2018}, month = {2018/07/16}, pages = {014201}, abstract = {

Motivated by neutral excitations in disordered electronic materials and systems of trapped ultracold particles with long-range interactions, we study energy-level statistics of quasiparticles with the power-law hopping Hamiltonian \∝1/rα in a strong random potential. In solid-state systems such quasiparticles, which are exemplified by neutral dipolar excitations, lead to long-range correlations of local observables and may dominate energy transport. Focussing on the excitations in disordered electronic systems, we compute the energy-level correlation function R2(ω) in a finite system in the limit of sufficiently strong disorder. At small energy differences the correlations exhibit Wigner-Dyson statistics. In particular, in the limit of very strong disorder the energy-level correlation function is given by R2(ω,V)=A3ωωV for small frequencies ω<<ωV and R2(ω,V)=1\−(α\−d)A1(ωVω)dα\−A2(ωVω)2 for large frequencies ω>>ωV, where ωV\∝V\−αd is the characteristic matrix element of excitation hopping in a system of volume V, and A1, A2 and A3 are coefficient of order unity which depend on the shape of the system. The energy-level correlation function, which we study, allows for a direct experimental observation, for example, by measuring the correlations of the ac conductance of the system at different frequencies.

}, doi = {https://doi.org/10.1103/PhysRevB.98.014201}, url = {https://arxiv.org/abs/1803.11178}, author = {Paraj Titum and Victor L. Quito and Sergey V. Syzranov} } @article {2054, title = {Entanglement of purification: from spin chains to holography}, journal = {Journal of High Energy Physics}, year = {2018}, month = {2018/01/22}, pages = {98}, abstract = {

Purification is a powerful technique in quantum physics whereby a mixed quantum state is extended to a pure state on a larger system. This process is not unique, and in systems composed of many degrees of freedom, one natural purification is the one with minimal entanglement. Here we study the entropy of the minimally entangled purification, called the entanglement of purification, in three model systems: an Ising spin chain, conformal field theories holographically dual to Einstein gravity, and random stabilizer tensor networks. We conjecture values for the entanglement of purification in all these models, and we support our conjectures with a variety of numerical and analytical results. We find that such minimally entangled purifications have a number of applications, from enhancing entanglement-based tensor network methods for describing mixed states to elucidating novel aspects of the emergence of geometry from entanglement in the AdS/CFT correspondence.

}, doi = {10.1007/JHEP01(2018)098}, url = {https://link.springer.com/article/10.1007\%2FJHEP01\%282018\%29098$\#$citeas}, author = {Phuc Nguyen and Trithep Devakul and Matthew G. Halbasch and Michael P. Zaletel and Brian Swingle} } @article {2318, title = {Exact entanglement cost of quantum states and channels under PPT-preserving operations}, year = {2018}, abstract = {

This paper establishes single-letter formulas for the exact entanglement cost of generating bipartite quantum states and simulating quantum channels under free quantum operations that completely preserve positivity of the partial transpose (PPT). First, we establish that the exact entanglement cost of any bipartite quantum state under PPT-preserving operations is given by a single-letter formula, here called the\ κ-entanglement of a quantum state. This formula is calculable by a semidefinite program, thus allowing for an efficiently computable solution for general quantum states. Notably, this is the first time that an entanglement measure for general bipartite states has been proven not only to possess a direct operational meaning but also to be efficiently computable, thus solving a question that has remained open since the inception of entanglement theory over two decades ago. Next, we introduce and solve the exact entanglement cost for simulating quantum channels in both the parallel and sequential settings, along with the assistance of free PPT-preserving operations. The entanglement cost in both cases is given by the same single-letter formula and is equal to the largest\ κ-entanglement that can be shared by the sender and receiver of the channel. It is also efficiently computable by a semidefinite program.\ 

}, url = {https://arxiv.org/abs/1809.09592}, author = {Xin Wang and Mark M. Wilde} } @article {2282, title = {Experimentally Generated Randomness Certified by the Impossibility of Superluminal Signals}, journal = {Nature}, volume = {556}, year = {2018}, month = {2018/04/11}, pages = {223-226}, abstract = {

From dice to modern complex circuits, there have been many attempts to build increasingly better devices to generate random numbers. Today, randomness is fundamental to security and cryptographic systems, as well as safeguarding privacy. A key challenge with random number generators is that it is hard to ensure that their outputs are unpredictable. For a random number generator based on a physical process, such as a noisy classical system or an elementary quantum measurement, a detailed model describing the underlying physics is required to assert unpredictability. Such a model must make a number of assumptions that may not be valid, thereby compromising the integrity of the device. However, it is possible to exploit the phenomenon of quantum nonlocality with a loophole-free Bell test to build a random number generator that can produce output that is unpredictable to any adversary limited only by general physical principles. With recent technological developments, it is now possible to carry out such a loophole-free Bell test. Here we present certified randomness obtained from a photonic Bell experiment and extract 1024 random bits uniform to within 10\−12. These random bits could not have been predicted within any physical theory that prohibits superluminal signaling and allows one to make independent measurement choices. To certify and quantify the randomness, we describe a new protocol that is optimized for apparatuses characterized by a low per-trial violation of Bell inequalities. We thus enlisted an experimental result that fundamentally challenges the notion of determinism to build a system that can increase trust in random sources. In the future, random number generators based on loophole-free Bell tests may play a role in increasing the security and trust of our cryptographic systems and infrastructure.

}, doi = {https://doi.org/10.1038/s41586-018-0019-0}, url = {https://arxiv.org/abs/1803.06219}, author = {Peter Bierhorst and Emanuel Knill and Scott Glancy and Yanbao Zhang and Alan Mink and Stephen Jordan and Andrea Rommal and Yi-Kai Liu and Bradley Christensen and Sae Woo Nam and Martin J. Stevens and Lynden K. Shalm} } @article {2001, title = {{E}ntanglement area laws for long-range interacting systems}, journal = {Physical Review Letters}, volume = {119}, year = {2017}, month = {2017/07/31}, pages = {050501}, abstract = {

We prove that the entanglement entropy of any state evolved under an arbitrary 1/rα long-range-interacting D-dimensional lattice spin Hamiltonian cannot change faster than a rate proportional to the boundary area for any α \> D + 1. We also prove that for any α \> 2D + 2, the ground state of such a Hamiltonian satisfies the entanglement area law if it can be transformed along a gapped adiabatic path into a ground state known to satisfy the area law. These results significantly generalize their existing counterparts for short-range interacting systems, and are useful for identifying dynamical phase transitions and quantum phase transitions in the presence of long-range interactions.

}, doi = {10.1103/PhysRevLett.119.050501}, url = {https://arxiv.org/abs/1702.05368}, author = {Zhe-Xuan Gong and Michael Foss-Feig and Fernando G. S. L. Brand{\~a}o and Alexey V. Gorshkov} } @article {2021, title = {Efficient quantum algorithms for analyzing large sparse electrical networks}, journal = {Quantum Information \& Computation}, volume = {17}, year = {2017}, month = {2017/07/21}, pages = {987-1026}, abstract = {

Analyzing large sparse electrical networks is a fundamental task in physics, electrical engineering and computer science. We propose two classes of quantum algorithms for this task. The first class is based on solving linear systems, and the second class is based on using quantum walks. These algorithms compute various electrical quantities, including voltages, currents, dissipated powers and effective resistances, in time poly(d, c,log(N),1/λ,1/ε), where N is the number of vertices in the network, d is the maximum unweighted degree of the vertices, c is the ratio of largest to smallest edge resistance, λ is the spectral gap of the normalized Laplacian of the network, and ε is the accuracy. Furthermore, we show that the polynomial dependence on 1/λ is necessary. This implies that our algorithms are optimal up to polynomial factors and cannot be signficantly improved.

}, url = {https://arxiv.org/abs/1311.1851}, author = {Guoming Wang} } @article {1902, title = {Efficient simulation of sparse Markovian quantum dynamics}, journal = {Quantum Information and Computation}, volume = {17}, year = {2017}, month = {2017/09/01}, pages = {901-947}, abstract = {

Quantum algorithms for simulating Hamiltonian dynamics have been extensively developed, but there has been much less work on quantum algorithms for simulating the dynamics of open quantum systems. We give the first efficient quantum algorithms for simulating Markovian quantum dynamics generated by Lindbladians that are not necessarily local. We introduce two approaches to simulating sparse Lindbladians. First, we show how to simulate Lindbladians that act within small invariant subspaces using a quantum algorithm to implement sparse Stinespring isometries. Second, we develop a method for simulating sparse Lindblad operators by concatenating a sequence of short-time evolutions. We also show limitations on Lindbladian simulation by proving a no-fast-forwarding theorem for simulating sparse Lindbladians in a black-box model.

}, doi = {10.26421/QIC17.11-12}, url = {https://arxiv.org/abs/1611.05543}, author = {Andrew M. Childs and Tongyang Li} } @article {2059, title = {Efimov States of Strongly Interacting Photons}, journal = {Physical Review Letters}, volume = {119}, year = {2017}, month = {2017/12/04}, pages = {233601}, abstract = {

We demonstrate the emergence of universal Efimov physics for interacting photons in cold gases of Rydberg atoms. We consider the behavior of three photons injected into the gas in their propagating frame, where a paraxial approximation allows us to consider them as massive particles. In contrast to atoms and nuclei, the photons have a large anisotropy between their longitudinal mass, arising from dispersion, and their transverse mass, arising from diffraction. Nevertheless, we show that in suitably rescaled coordinates the effective interactions become dominated by s-wave scattering near threshold and, as a result, give rise to an Efimov effect near unitarity, but with spatially anisotropic wavefunctions in the original coordinates. We show that the three-body loss of these Efimov trimers can be strongly suppressed and determine conditions under which these states are observable in current experiments. These effects can be naturally extended to probe few-body universality beyond three bodies, as well as the role of Efimov physics in the non-equilbrium, many-body regime.

}, doi = {10.1103/PhysRevLett.119.233601}, url = {https://arxiv.org/abs/1709.01955}, author = {Michael Gullans and S. Diehl and S. T. Rittenhouse and B. P. Ruzic and J. P. D{\textquoteright}Incao and P. Julienne and Alexey V. Gorshkov and J. M. Taylor} } @article {2051, title = {An Elementary Proof of Private Random Number Generation from Bell Inequalities}, year = {2017}, month = {2017/07/20}, abstract = {

The field of device-independent quantum cryptography has seen enormous success in the past several years, including security proofs for key distribution and random number generation that account for arbitrary imperfections in the devices used. Full security proofs in the field so far are long and technically deep. In this paper we show that the concept of the mirror adversary can be used to simplify device-independent proofs. We give a short proof that any bipartite Bell violation can be used to generate private random numbers. The proof is based on elementary techniques and is self-contained.

}, url = {https://arxiv.org/abs/1707.06597}, author = {Carl Miller} } @article {1906, title = {Emergent equilibrium in many-body optical bistability}, journal = {Physical Review A}, volume = {95}, year = {2017}, month = {2017/04/17}, pages = {043826}, abstract = {

Many-body systems constructed of quantum-optical building blocks can now be realized in experimental platforms ranging from exciton-polariton fluids to ultracold gases of Rydberg atoms, establishing a fascinating interface between traditional many-body physics and the driven-dissipative, non-equilibrium setting of cavity-QED. At this interface, the standard techniques and intuitions of both fields are called into question, obscuring issues as fundamental as the role of fluctuations, dimensionality, and symmetry on the nature of collective behavior and phase transitions. Here, we study the driven-dissipative Bose-Hubbard model, a minimal description of numerous atomic, optical, and solid-state systems in which particle loss is countered by coherent driving. Despite being a lattice version of optical bistability---a foundational and patently non-equilibrium model of cavity-QED---the steady state possesses an emergent equilibrium description in terms of a classical Ising model. We establish this picture by identifying a limit in which the quantum dynamics is asymptotically equivalent to non-equilibrium Langevin equations, which support a phase transition described by model A of the Hohenberg-Halperin classification. Numerical simulations of the Langevin equations corroborate this picture, producing results consistent with the behavior of a finite-temperature Ising model.

}, doi = {doi.org/10.1103/PhysRevA.95.043826}, url = {https://journals.aps.org/pra/abstract/10.1103/PhysRevA.95.043826}, author = {Michael Foss-Feig and Pradeep Niroula and Jeremy T. Young and Mohammad Hafezi and Alexey V. Gorshkov and Ryan M. Wilson and Mohammad F. Maghrebi} } @article {2301, title = {Entanglement Wedge Reconstruction via Universal Recovery Channels}, year = {2017}, abstract = {

We apply and extend the theory of universal recovery channels from quantum information theory to address the problem of entanglement wedge reconstruction in AdS/CFT. It has recently been proposed that any low-energy local bulk operators in a CFT boundary region\&$\#$39;s entanglement wedge can be reconstructed on that boundary region itself. Existing work arguing for this proposal relies on algebraic consequences of the exact equivalence between bulk and boundary relative entropies, namely the theory of operator algebra quantum error correction. However, bulk and boundary relative entropies are only approximately equal in bulk effective field theory, and in similar situations it is known that predictions from exact entropic equalities can be qualitatively incorrect. The framework of universal recovery channels provides a robust demonstration of the entanglement wedge reconstruction conjecture in addition to new physical insights. Most notably, we find that a bulk operator acting in a given boundary region\&$\#$39;s entanglement wedge can be expressed as the response of the boundary region\&$\#$39;s modular Hamiltonian to a perturbation of the bulk state in the direction of the bulk operator. This formula can be interpreted as a noncommutative version of Bayes\&$\#$39; rule that attempts to undo the noise induced by restricting to only a portion of the boundary, and has an integral representation in terms of modular flows. To reach these conclusions, we extend the theory of universal recovery channels to finite-dimensional operator algebras and demonstrate that recovery channels approximately preserve the multiplicative structure of the operator algebra

}, url = {https://arxiv.org/abs/1704.05839}, author = {Jordan Cotler and Patrick Hayden and Geoffrey Penington and Grant Salton and Brian Swingle and Michael Walter} } @article {1921, title = {Exact sampling hardness of Ising spin models}, journal = {Physical Review A}, volume = {96}, year = {2017}, month = {2017/09/14}, pages = {032324}, abstract = {

We study the complexity of classically sampling from the output distribution of an Ising spin model, which can be implemented naturally in a variety of atomic, molecular, and optical systems. In particular, we construct a specific example of an Ising Hamiltonian that, after time evolution starting from a trivial initial state, produces a particular output configuration with probability very nearly proportional to the square of the permanent of a matrix with arbitrary integer entries. In a similar spirit to boson sampling, the ability to sample classically from the probability distribution induced by time evolution under this Hamiltonian would imply unlikely complexity theoretic consequences, suggesting that the dynamics of such a spin model cannot be efficiently simulated with a classical computer. Physical Ising spin systems capable of achieving problem-size instances (i.e., qubit numbers) large enough so that classical sampling of the output distribution is classically difficult in practice may be achievable in the near future. Unlike boson sampling, our current results only imply hardness of\ exact\ classical sampling, leaving open the important question of whether a much stronger approximate-sampling hardness result holds in this context. The latter is most likely necessary to enable a convincing experimental demonstration of quantum supremacy. As referenced in a recent paper [A. Bouland, L. Mancinska, and X. Zhang, in\ Proceedings of the 31st Conference on Computational Complexity (CCC 2016), Leibniz International Proceedings in Informatics (Schloss Dagstuhl\–Leibniz-Zentrum f{\"u}r Informatik, Dagstuhl, 2016)], our result completes the sampling hardness classification of two-qubit commuting Hamiltonians.

}, doi = {10.1103/PhysRevA.96.032324}, url = {https://arxiv.org/abs/1701.03167}, author = {Bill Fefferman and Michael Foss-Feig and Alexey V. Gorshkov} } @article {1780, title = {Exactly soluble model of boundary degeneracy}, journal = {Physical Review B}, volume = {95}, year = {2017}, month = {2017/01/25}, chapter = {045309}, abstract = {

We investigate the topological degeneracy that can be realized in Abelian fractional quantum spin Hall states with multiply connected gapped boundaries. Such a topological degeneracy (also dubbed as \"boundary degeneracy\") does not require superconducting proximity effect and can be created by simply applying a depletion gate to the quantum spin Hall material and using a generic spin-mixing term (e.g., due to backscattering) to gap out the edge modes. We construct an exactly soluble microscopic model manifesting this topological degeneracy and solve it using the recently developed technique [S. Ganeshan and M. Levin, Phys. Rev. B 93, 075118 (2016)]. The corresponding string operators spanning this degeneracy are explicitly calculated. It is argued that the proposed scheme is experimentally reasonable.

}, doi = {10.1103/PhysRevB.95.045309}, url = {http://journals.aps.org/prb/abstract/10.1103/PhysRevB.95.045309}, author = {Sriram Ganeshan and Alexey V. Gorshkov and Victor Gurarie and Victor M. Galitski} } @proceedings {1935, title = {Experimental Comparison of Two Quantum Computing Architectures}, volume = {114}, year = {2017}, month = {2017/03/21}, pages = {3305-3310}, edition = {13}, abstract = {

We run a selection of algorithms on two state-of-the-art 5-qubit quantum computers that are based on different technology platforms. One is a publicly accessible superconducting transmon device [1] with limited connectivity, and the other is a fully connected trapped-ion system [2]. Even though the two systems have different native quantum interactions, both can be programmed in a way that is blind to the underlying hardware, thus allowing the first comparison of identical quantum algorithms between different physical systems. We show that quantum algorithms and circuits that employ more connectivity clearly benefit from a better connected system of qubits. While the quantum systems here are not yet large enough to eclipse classical computers, this experiment exposes critical factors of scaling quantum computers, such as qubit connectivity and gate expressivity. In addition, the results suggest that co-designing particular quantum applications with the hardware itself will be paramount in successfully using quantum computers in the future.

}, doi = {10.1073/pnas.1618020114}, url = {http://www.pnas.org/content/114/13/3305}, author = {N.M. Linke and Dmitri Maslov and Martin Roetteler and S. Debnath and C. Figgatt and K. A. Landsman and K. Wright and Christopher Monroe} } @article {1944, title = {Experimental demonstration of cheap and accurate phase estimation}, journal = {Physical Review Letters}, volume = {118}, year = {2017}, month = {2017/05/12}, pages = {190502}, abstract = {

We demonstrate experimental implementation of robust phase estimation (RPE) to learn the phases of X and Y rotations on a trapped Yb+ ion qubit. We estimate these phases with uncertainties less than 4 \· 10\−4 radians using as few as 176 total experimental samples per phase, and our estimates exhibit Heisenberg scaling. Unlike standard phase estimation protocols, RPE neither assumes perfect state preparation and measurement, nor requires access to ancillae. We cross-validate the results of RPE with the more resource-intensive protocol of gate set tomography.

}, doi = {doi.org/10.1103/PhysRevLett.118.190502}, url = {https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.118.190502}, author = {Kenneth Rudinger and Shelby Kimmel and Daniel Lobser and Peter Maunz} } @article {2130, title = {Experimental Study of Optimal Measurements for Quantum State Tomography}, journal = {Physical Review Letters}, volume = {119}, year = {2017}, month = {2017/10/13}, pages = {150401}, abstract = {

Quantum tomography is a critically important tool to evaluate quantum hardware, making it essential to develop optimized measurement strategies that are both accurate and efficient. We compare a variety of strategies using nearly pure test states. Those that are informationally complete for all states are found to be accurate and reliable even in the presence of errors in the measurements themselves, while those designed to be complete only for pure states are far more efficient but highly sensitive to such errors. Our results highlight the unavoidable trade-offs inherent in quantum tomography.

}, doi = {10.1103/PhysRevLett.119.150401}, url = {https://link.aps.org/doi/10.1103/PhysRevLett.119.150401}, author = {Sosa-Martinez, H. and Lysne, N. K. and Baldwin, C. H. and Kalev, A. and Deutsch, I. H. and Jessen, P. S.} } @article {1945, title = {Experimentally Generated Random Numbers Certified by the Impossibility of Superluminal Signaling}, year = {2017}, month = {2017/02/16}, abstract = {

Random numbers are an important resource for applications such as numerical simulation and secure communication. However, it is difficult to certify whether a physical random number generator is truly unpredictable. Here, we exploit the phenomenon of quantum nonlocality in a loophole-free photonic Bell test experiment for the generation of randomness that cannot be predicted within any physical theory that allows one to make independent measurement choices and prohibits superluminal signaling. To certify and quantify the randomness, we describe a new protocol that performs well in an experimental regime characterized by low violation of Bell inequalities. Applying an extractor function to our data, we obtained 256 new random bits, uniform to within 0.001.

}, url = {https://arxiv.org/abs/1702.05178$\#$}, author = {Peter Bierhorst and Emanuel Knill and Scott Glancy and Alan Mink and Stephen P. Jordan and Andrea Rommal and Yi-Kai Liu and Bradley Christensen and Sae Woo Nam and Lynden K. Shalm} } @article {2201, title = {Exponential improvements for quantum-accessible reinforcement learning}, year = {2017}, abstract = {

Quantum computers can offer dramatic improvements over classical devices for data analysis tasks such as prediction and classification. However, less is known about the advantages that quantum computers may bring in the setting of reinforcement learning, where learning is achieved via interaction with a task environment. Here, we consider a special case of reinforcement learning, where the task environment allows quantum access. In addition, we impose certain \"naturalness\" conditions on the task environment, which rule out the kinds of oracle problems that are studied in quantum query complexity (and for which quantum speedups are well-known). Within this framework of quantum-accessible reinforcement learning environments, we demonstrate that quantum agents can achieve exponential improvements in learning efficiency, surpassing previous results that showed only quadratic improvements. A key step in the proof is to construct task environments that encode well-known oracle problems, such as Simon\&$\#$39;s problem and Recursive Fourier Sampling, while satisfying the above \"naturalness\" conditions for reinforcement learning. Our results suggest that quantum agents may perform well in certain game-playing scenarios, where the game has recursive structure, and the agent can learn by playing against itself

}, url = {https://arxiv.org/abs/1710.11160}, author = {Vedran Dunjko and Yi-Kai Liu and Xingyao Wu and J. M. Taylor} } @article {2106, title = {Exponential Quantum Speed-ups for Semidefinite Programming with Applications to Quantum Learning}, year = {2017}, month = {2017/10/06}, abstract = {

We give semidefinite program (SDP) quantum solvers with an exponential speed-up over classical ones. Specifically, we consider SDP instances with m constraint matrices of dimension n, each of rank at most r, and assume that the input matrices of the SDP are given as quantum states (after a suitable normalization). Then we show there is a quantum algorithm that solves the SDP feasibility problem with accuracy ǫ by using \√ m log m \· poly(log n,r, ǫ \−1 ) quantum gates. The dependence on n provides an exponential improvement over the work of Brand \˜ao and Svore [6] and the work of van Apeldoorn et al. [23], and demonstrates an exponential quantum speed-up when m and r are small. We apply the SDP solver to the problem of learning a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state ρ, we show we can find in time \√ m log m \· poly(log n,r, ǫ \−1 ) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as ρ on the m measurements up to error ǫ. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes\’ principle. As in previous work, we obtain our algorithm by \“quantizing\” classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension based on the techniques developed in quantum principal component analysis, which could be of independent interest. Our quantum SDP solver is different from previous ones in the following two aspects: (1) it follows from a zero-sum game approach of Hazan [11] of solving SDPs rather than the primal-dual approach by Arora and Kale [5]; and (2) it does not rely on any sparsity assumption of the input matrices.

}, url = {https://arxiv.org/abs/1710.02581}, author = {Fernando G. S. L. Brand{\~a}o and Amir Kalev and Tongyang Li and Cedric Yen-Yu Lin and Krysta M. Svore and Xiaodi Wu} } @article {1986, title = {Extracting entanglement geometry from quantum states}, journal = {Physical Review Letters}, volume = {119}, year = {2017}, month = {2017/10/06}, abstract = {

Tensor networks impose a notion of geometry on the entanglement of a quantum system. In some cases, this geometry is found to reproduce key properties of holographic dualities, and subsequently much work has focused on using tensor networks as tractable models for holographic dualities. Conventionally, the structure of the network - and hence the geometry - is largely fixed a priori by the choice of tensor network ansatz. Here, we evade this restriction and describe an unbiased approach that allows us to extract the appropriate geometry from a given quantum state. We develop an algorithm that iteratively finds a unitary circuit that transforms a given quantum state into an unentangled product state. We then analyze the structure of the resulting unitary circuits. In the case of non-interacting, critical systems in one dimension, we recover signatures of scale invariance in the unitary network, and we show that appropriately defined geodesic paths between physical degrees of freedom exhibit known properties of a hyperbolic geometry.

}, doi = {10.1103/PhysRevLett.119.140502}, url = {https://arxiv.org/abs/1704.01974}, author = {Katharine Hyatt and James R. Garrison and Bela Bauer} } @article {2009, title = {Extreme learning machines for regression based on V-matrix method}, journal = {Cognitive Neurodynamics}, year = {2017}, month = {2017/06/10}, abstract = {

This paper studies the joint effect of V-matrix, a recently proposed framework for statistical inferences, and extreme learning machine (ELM) on regression problems. First of all, a novel algorithm is proposed to efficiently evaluate the V-matrix. Secondly, a novel weighted ELM algorithm called V-ELM is proposed based on the explicit kernel mapping of ELM and the V-matrix method. Though V-matrix method could capture the geometrical structure of training data, it tends to assign a higher weight to instance with smaller input value. In order to avoid this bias, a novel method called VI-ELM is proposed by minimizing both the regression error and the V-matrix weighted error simultaneously. Finally, experiment results on 12 real world benchmark datasets show the effectiveness of our proposed methods.

}, issn = {1871-4099}, doi = {10.1007/s11571-017-9444-2}, url = {http://dx.doi.org/10.1007/s11571-017-9444-2}, author = {Yang, Zhiyong and Zhang, Taohong and Lu, Jingcheng and Yuan Su and Zhang, Dezheng and Duan, Yaowu} } @article {1784, title = {Effective Field Theory for Rydberg Polaritons}, journal = {Physical Review Letters}, volume = {117}, year = {2016}, month = {2016/09/09}, pages = {113601}, abstract = {

We study non-perturbative effects in N-body scattering of Rydberg polaritons using effective field theory (EFT). We develop an EFT in one dimension and show how a suitably long medium can be used to prepare shallow N-body bound states. We then derive the effective N-body interaction potential for Rydberg polaritons and the associated N-body contact force that arises in the EFT. We use the contact force to find the leading order corrections to the binding energy of the N-body bound states and determine the photon number at which the EFT description breaks down. We find good agreement throughout between the predictions of EFT and numerical simulations of the exact two and three photon wavefunction transmission.

}, doi = {http://dx.doi.org/10.1103/PhysRevLett.117.113601}, url = {http://arxiv.org/abs/1605.05651}, author = {Michael Gullans and J. D. Thompson and Y. Wang and Q. -Y. Liang and V. Vuletic and M. D. Lukin and Alexey V. Gorshkov} } @article {2004, title = {Entanglement and spin-squeezing without infinite-range interactions}, year = {2016}, month = {2016/12/22}, abstract = {

Infinite-range interactions are known to facilitate the production of highly entangled states with applications in quantum information and metrology. However, many experimental systems have interactions that decay with distance, and the achievable benefits in this context are much less clear. Combining recent exact solutions with a controlled expansion in the system size, we analyze quench dynamics in Ising models with power-law (1/r α ) interactions in D dimensions, thereby expanding the understanding of spin squeezing into a broad and experimentally relevant context. In spatially homogeneous systems, we show that for small α the scaling of squeezing with system size is identical to the infinite-range (α = 0) case. This indifference to the interaction range persists up to a critical value α = 2D/3, above which squeezing degrades continuously. Boundaryinduced inhomogeneities present in most experimental systems modify this picture, but it nevertheless remains qualitatively correct for finite-sized systems.

}, url = {https://arxiv.org/abs/1612.07805}, author = {Michael Foss-Feig and Zhe-Xuan Gong and Alexey V. Gorshkov and Charles W. Clark} } @article {1735, title = {Entangling distant resonant exchange qubits via circuit quantum electrodynamics}, journal = {Physical Review B}, volume = {94}, year = {2016}, month = {2016/11/16}, pages = {205421}, abstract = {

We investigate a hybrid quantum system consisting of spatially separated resonant exchange qubits, defined in three-electron semiconductor triple quantum dots, that are coupled via a superconducting transmission line resonator. Drawing on methods from circuit quantum electrodynamics and Hartmann-Hahn double resonance techniques, we analyze three specific approaches for implementing resonator-mediated two-qubit entangling gates in both dispersive and resonant regimes of interaction. We calculate entangling gate fidelities as well as the rate of relaxation via phonons for resonant exchange qubits in silicon triple dots and show that such an implementation is particularly well-suited to achieving the strong coupling regime. Our approach combines the favorable coherence properties of encoded spin qubits in silicon with the rapid and robust long-range entanglement provided by circuit QED systems.

}, doi = {10.1103/PhysRevB.94.205421}, url = {https://doi.org/10.1103/PhysRevB.94.205421}, author = {V. Srinivasa and J. M. Taylor and C. Tahan} } @article {1910, title = {Experimental demonstration of quantum fault tolerance}, year = {2016}, month = {2016/11/21}, abstract = {

Quantum computers will eventually reach a size at which quantum error correction (QEC) becomes imperative. In order to make quantum information robust to errors introduced by qubit imperfections and flawed control operations, QEC protocols encode a logical qubit in multiple physical qubits. This redundancy allows the extraction of error syndromes and the subsequent correction or detection of errors without destroying the logical state itself through direct measurement. While several experiments have shown a reduction of high intrinsic or artificially introduced errors in logical qubits, fault-tolerant encoding of a logical qubit has never been demonstrated. Here we show the encoding and syndrome measurement of a fault-tolerant logical qubit via an error detection protocol on four physical qubits, represented by trapped atomic ions. This demonstrates for the first time the robustness of a fault-tolerant qubit to imperfections in the very operations used to encode it. This advantage persists in the face of large added error rates and experimental calibration errors.

}, url = {https://arxiv.org/abs/1611.06946}, author = {N. M. Linke and M. Gutierrez and K. A. Landsman and C. Figgatt and S. Debnath and K. R. Brown and C. Monroe} } @conference {1903, title = {Exponential Separation of Quantum Communication and Classical Information}, booktitle = {20th Annual Conference on Quantum Information Processing (QIP)}, year = {2016}, month = {2016/11/28}, abstract = {
We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the other direction was already known from the work of Kerenidis et. al. [SICOMP 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable. As classical information complexity is an upper bound on quantum information complexity, which in turn is equal to amortized quantum communication complexity, our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold. The function we use to present such a separation is the Symmetric k-ary Pointer Jumping function introduced by Rao and Sinha [ECCC TR15-057], whose classical communication complexity is exponentially larger than its classical information complexity. In this paper, we show that the quantum communication complexity of this function is polynomially equivalent to its classical communication complexity. The high-level idea behind our proof is arguably the simplest so far for such an exponential separation between information and communication, driven by a sequence of round-elimination arguments, allowing us to simplify further the approach of Rao and Sinha.\ 
As another application of the techniques that we develop, we give a simple proof for an optimal trade-off between Alice\&$\#$39;s and Bob\&$\#$39;s communication while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/exp(O(b)) bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.
}, url = {https://arxiv.org/abs/1611.08946}, author = {Anurag Anshu and Dave Touchette and Penghui Yao and Nengkun Yu} } @article {1526, title = {Entanglement entropy of dispersive media from thermodynamic entropy in one higher dimension}, journal = {Physical Review Letters}, volume = {114}, year = {2015}, month = {2015/04/16}, pages = {151602}, abstract = { A dispersive medium becomes entangled with zero-point fluctuations in the vacuum. We consider an arbitrary array of material bodies weakly interacting with a quantum field and compute the quantum mutual information between them. It is shown that the mutual information in D dimensions can be mapped to classical thermodynamic entropy in D+1 dimensions. As a specific example, we compute the mutual information both analytically and numerically for a range of separation distances between two bodies in D=2 dimensions and find a logarithmic correction to the area law at short separations. A key advantage of our method is that it allows the strong subadditivity property---notoriously difficult to prove for quantum systems---to be easily verified. }, doi = {10.1103/PhysRevLett.114.151602}, url = {http://arxiv.org/abs/1412.5613v2}, author = {Mohammad F. Maghrebi and Homer Reid} } @article {1473, title = {Entangling two transportable neutral atoms via local spin exchange}, journal = {Nature}, volume = {527}, year = {2015}, month = {2015/11/02}, pages = {208-211}, abstract = { To advance quantum information science a constant pursuit is the search for physical systems that meet the stringent requirements for creating and preserving quantum entanglement. In atomic physics, robust two-qubit entanglement is typically achieved by strong, long-range interactions in the form of Coulomb interactions between ions or dipolar interactions between Rydberg atoms. While these interactions allow fast gates, atoms subject to these interactions must overcome the associated coupling to the environment and cross-talk among qubits. Local interactions, such as those requiring significant wavefunction overlap, can alleviate these detrimental effects yet present a new challenge: To distribute entanglement, qubits must be transported, merged for interaction, and then isolated for storage and subsequent operations. Here we show how, via a mobile optical tweezer, it is possible to prepare and locally entangle two ultracold neutral atoms, and then separate them while preserving their entanglement. While ultracold neutral atom experiments have measured dynamics consistent with spin entanglement, we are now able to demonstrate two-particle coherence via application of a local gradient and parity measurements; this new entanglement-verification protocol could be applied to arbitrary spin-entangled states of spatially-separated atoms. The local entangling operation is achieved via ultracold spin-exchange interactions, and quantum tunneling is used to combine and separate atoms. Our toolset provides a framework for dynamically entangling remote qubits via local operations within a large-scale quantum register. }, doi = {10.1038/nature16073}, url = {http://arxiv.org/abs/1507.05586}, author = {A. M. Kaufman and B. J. Lester and Michael Foss-Feig and M. L. Wall and A. M. Rey and C. A. Regal} } @article {1600, title = {"Einstein and Bohr Meet Alice and Bob{\textquoteright}, Logic and Science Facing the New Technologies}, journal = {Proceedings of the 14th Congress for Logic (Nancy), Logic, Methodology and Philosophy of Science}, year = {2014}, month = {2014/01/01}, author = {Jeffrey Bub and Peter Schroeder-Heister and Gerhard Heinzmann and Wilfrid Hodges and Pierre Edouard Bour} } @article {1264, title = {Exponential improvement in precision for simulating sparse Hamiltonians}, journal = {Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014)}, year = {2014}, month = {2014/05/31}, pages = {283-292}, abstract = { We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a $d$-sparse Hamiltonian $H$ acting on $n$ qubits can be simulated for time $t$ with precision $\epsilon$ using $O\big(\tau \frac{\log(\tau/\epsilon)}{\log\log(\tau/\epsilon)}\big)$ queries and $O\big(\tau \frac{\log^2(\tau/\epsilon)}{\log\log(\tau/\epsilon)}n\big)$ additional 2-qubit gates, where $\tau = d^2 \|{H}\|_{\max} t$. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error. }, isbn = {978-1-4503-2710-7}, doi = {10.1145/2591796.2591854}, url = {http://arxiv.org/abs/1312.1414v2}, author = {Dominic W. Berry and Andrew M. Childs and Richard Cleve and Robin Kothari and Rolando D. Somma} } @article {1791, title = {Extended order parameter and conjugate field for the dynamic phase transition in a Ginzburg-Landau mean-field model in an oscillating field}, journal = {Physical Review E}, volume = {89}, year = {2014}, month = {2014/02/12}, pages = {022114}, abstract = {We present numerical evidence for an extended order parameter and conjugate field for the dynamic phase transition in a Ginzburg-Landau mean-field model driven by an oscillating field. The order parameter, previously taken to be the time-averaged magnetization, comprises the deviations of the Fourier components of the magnetization from their values at the critical period. The conjugate field, previously taken to be the time-averaged magnetic field, comprises the even Fourier components of the field. The scaling exponents β and δ associated with the extended order parameter and conjugate field are shown numerically to be consistent with their values in the equilibrium mean-field model.}, doi = {10.1103/PhysRevE.89.022114}, url = {http://link.aps.org/doi/10.1103/PhysRevE.89.022114}, author = {Daniel T. Robb and Aaron Ostrander} } @article {1245, title = {Easy and hard functions for the Boolean hidden shift problem}, journal = {Proceedings of TQC 2013}, volume = {22}, year = {2013}, month = {2013/04/16}, pages = {50-79}, abstract = { We study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x+s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this problem depends strongly on f. We demonstrate that the easiest instances of this problem correspond to bent functions, in the sense that an exact one-query algorithm exists if and only if the function is bent. We partially characterize the hardest instances, which include delta functions. Moreover, we show that the problem is easy for random functions, since two queries suffice. Our algorithm for random functions is based on performing the pretty good measurement on several copies of a certain state; its analysis relies on the Fourier transform. We also use this approach to improve the quantum rejection sampling approach to the Boolean hidden shift problem. }, doi = {10.4230/LIPIcs.TQC.2013.50}, url = {http://arxiv.org/abs/1304.4642v1}, author = {Andrew M. Childs and Robin Kothari and Maris Ozols and Martin Roetteler} } @article {1343, title = {Electrically-protected resonant exchange qubits in triple quantum dots}, journal = {Physical Review Letters}, volume = {111}, year = {2013}, month = {2013/7/31}, abstract = {We present a modulated microwave approach for quantum computing with qubits comprising three spins in a triple quantum dot. This approach includes single- and two-qubit gates that are protected against low-frequency electrical noise, due to an operating point with a narrowband response to high frequency electric fields. Furthermore, existing double quantum dot advances, including robust preparation and measurement via spin-to-charge conversion, are immediately applicable to the new qubit. Finally, the electric dipole terms implicit in the high frequency coupling enable strong coupling with superconducting microwave resonators, leading to more robust two-qubit gates. }, doi = {10.1103/PhysRevLett.111.050502}, url = {http://arxiv.org/abs/1304.3407v2}, author = {J. M. Taylor and V. Srinivasa and J. Medford} } @article {1864, title = {Evasiveness of Graph Properties and Topological Fixed-Point Theorems}, journal = {Foundations and Trends in Theoretical Computer Science}, volume = {7}, year = {2013}, month = {2013/05/16}, pages = {337-415}, abstract = {

Many graph properties (e.g., connectedness, containing a complete subgraph) are known to be difficult to check. In a decision-tree model, the cost of an algorithm is measured by the number of edges in the graph that it queries. R. Karp conjectured in the early 1970s that all monotone graph properties are evasive -- that is, any algorithm which computes a monotone graph property must check all edges in the worst case. This conjecture is unproven, but a lot of progress has been made. Starting with the work of Kahn, Saks, and Sturtevant in 1984, topological methods have been applied to prove partial results on the Karp conjecture. This text is a tutorial on these topological methods. I give a fully self-contained account of the central proofs from the paper of Kahn, Saks, and Sturtevant, with no prior knowledge of topology assumed. I also briefly survey some of the more recent results on evasiveness.

}, issn = {1551-305X}, doi = {10.1561/0400000055}, url = {http://dx.doi.org/10.1561/0400000055}, author = {Carl Miller} } @article {1268, title = {Experimental Performance of a Quantum Simulator: Optimizing Adiabatic Evolution and Identifying Many-Body Ground States }, journal = {Physical Review A}, volume = {88}, year = {2013}, month = {2013/7/31}, abstract = { We use local adiabatic evolution to experimentally create and determine the ground state spin ordering of a fully-connected Ising model with up to 14 spins. Local adiabatic evolution -- in which the system evolution rate is a function of the instantaneous energy gap -- is found to maximize the ground state probability compared with other adiabatic methods while only requiring knowledge of the lowest $\sim N$ of the $2^N$ Hamiltonian eigenvalues. We also demonstrate that the ground state ordering can be experimentally identified as the most probable of all possible spin configurations, even when the evolution is highly non-adiabatic. }, doi = {10.1103/PhysRevA.88.012334}, url = {http://arxiv.org/abs/1305.2253v1}, author = {Philip Richerme and Crystal Senko and Jacob Smith and Aaron Lee and Simcha Korenblit and Christopher Monroe} } @article {1347, title = {The equilibrium states of open quantum systems in the strong coupling regime}, journal = {Physical Review E}, volume = {86}, year = {2012}, month = {2012/12/26}, abstract = {In this work we investigate the late-time stationary states of open quantum systems coupled to a thermal reservoir in the strong coupling regime. In general such systems do not necessarily relax to a Boltzmann distribution if the coupling to the thermal reservoir is non-vanishing or equivalently if the relaxation timescales are finite. Using a variety of non-equilibrium formalisms valid for non-Markovian processes, we show that starting from a product state of the closed system = system + environment, with the environment in its thermal state, the open system which results from coarse graining the environment will evolve towards an equilibrium state at late-times. This state can be expressed as the reduced state of the closed system thermal state at the temperature of the environment. For a linear (harmonic) system and environment, which is exactly solvable, we are able to show in a rigorous way that all multi-time correlations of the open system evolve towards those of the closed system thermal state. Multi-time correlations are especially relevant in the non-Markovian regime, since they cannot be generated by the dynamics of the single-time correlations. For more general systems, which cannot be exactly solved, we are able to provide a general proof that all single-time correlations of the open system evolve to those of the closed system thermal state, to first order in the relaxation rates. For the special case of a zero-temperature reservoir, we are able to explicitly construct the reduced closed system thermal state in terms of the environmental correlations. }, doi = {10.1103/PhysRevE.86.061132}, url = {http://arxiv.org/abs/1206.2707v1}, author = {Y. Subasi and C. H. Fleming and J. M. Taylor and B. L. Hu} } @article {1523, title = {Electromagnetic Casimir Energies of Semi-Infinite Planes}, journal = {EPL (Europhysics Letters)}, volume = {95}, year = {2011}, month = {2011/07/01}, pages = {14001}, abstract = { Using recently developed techniques based on scattering theory, we find the electromagnetic Casimir energy for geometries involving semi-infinite planes, a case that is of particular interest in the design of microelectromechanical devices. We obtain both approximate analytic formulae and exact results requiring only modest numerical computation. Using these results, we analyze the effects of edges and orientation on the Casimir energy. We also demonstrate the accuracy, simplicity, and utility of our approximation scheme, which is based on a multiple reflection expansion. }, doi = {10.1209/0295-5075/95/14001}, url = {http://arxiv.org/abs/1102.1486v1}, author = {Mohammad F. Maghrebi and Noah Graham} } @article {1457, title = {Entanglement can completely defeat quantum noise}, journal = {Physical Review Letters}, volume = {107}, year = {2011}, month = {2011/12/15}, abstract = { We describe two quantum channels that individually cannot send any information, even classical, without some chance of decoding error. But together a single use of each channel can send quantum information perfectly reliably. This proves that the zero-error classical capacity exhibits superactivation, the extreme form of the superadditivity phenomenon in which entangled inputs allow communication over zero capacity channels. But our result is stronger still, as it even allows zero-error quantum communication when the two channels are combined. Thus our result shows a new remarkable way in which entanglement across two systems can be used to resist noise, in this case perfectly. We also show a new form of superactivation by entanglement shared between sender and receiver. }, doi = {10.1103/PhysRevLett.107.250504}, url = {http://arxiv.org/abs/1109.0540v1}, author = {Jianxin Chen and Toby S. Cubitt and Aram W. Harrow and Graeme Smith} } @article {1521, title = {Entropic force of polymers on a cone tip}, journal = {EPL (Europhysics Letters)}, volume = {96}, year = {2011}, month = {2011/12/01}, pages = {66002}, abstract = { We consider polymers attached to the tip of a cone, and the resulting force due to entropy loss on approaching a plate (or another cone). At separations shorter than the polymer radius of gyration R_g, the only relevant length scale is the tip-plate (or tip-tip) separation h, and the entropic force is given by F=A kT/h. The universal amplitude A can be related to (geometry dependent) correlation exponents of long polymers. We compute A for phantom polymers, and for self-avoiding (including star) polymers by epsilon-expansion, as well as by numerical simulations in 3 dimensions. }, doi = {10.1209/0295-5075/96/66002}, url = {http://arxiv.org/abs/1109.5658v2}, author = {Mohammad F. Maghrebi and Yacov Kantor and Mehran Kardar} } @article {1431, title = {Efficient Direct Tomography for Matrix Product States}, year = {2010}, month = {2010/02/24}, abstract = { In this note, we describe a method for reconstructing matrix product states from a small number of efficiently-implementable measurements. Our method is exponentially faster than standard tomography, and it can also be used to certify that the unknown state is an MPS. The basic idea is to use local unitary operations to measure in the Schmidt basis, giving direct access to the MPS representation. This compares favorably with recently and independently proposed methods that recover the MPS tensors by performing a variational minimization, which is computationally intractable in certain cases. Our method also has the advantage of recovering any MPS, while other approaches were limited to special classes of states that exclude important examples such as GHZ and W states. }, url = {http://arxiv.org/abs/1002.4632v1}, author = {Olivier Landon-Cardinal and Yi-Kai Liu and David Poulin} } @article {1436, title = {Efficient quantum state tomography}, journal = {Nature Communications}, volume = {1}, year = {2010}, month = {2010/12/21}, pages = {149}, abstract = { Quantum state tomography, the ability to deduce the state of a quantum system from measured data, is the gold standard for verification and benchmarking of quantum devices. It has been realized in systems with few components, but for larger systems it becomes infeasible because the number of quantum measurements and the amount of computation required to process them grows exponentially in the system size. Here we show that we can do exponentially better than direct state tomography for a wide range of quantum states, in particular those that are well approximated by a matrix product state ansatz. We present two schemes for tomography in 1-D quantum systems and touch on generalizations. One scheme requires unitary operations on a constant number of subsystems, while the other requires only local measurements together with more elaborate post-processing. Both schemes rely only on a linear number of experimental operations and classical postprocessing that is polynomial in the system size. A further strength of the methods is that the accuracy of the reconstructed states can be rigorously certified without any a priori assumptions. }, doi = {10.1038/ncomms1147}, url = {http://arxiv.org/abs/1101.4366v1}, author = {Marcus Cramer and Martin B. Plenio and Steven T. Flammia and David Gross and Stephen D. Bartlett and Rolando Somma and Olivier Landon-Cardinal and Yi-Kai Liu and David Poulin} } @article {1867, title = {An Euler{\textendash}Poincar{\'e} bound for equicharacteristic {\'e}tale sheaves}, journal = {Algebra \& Number Theory}, volume = {4}, year = {2010}, month = {2010/01/14}, pages = {21 - 45}, abstract = {

The Grothendieck\–Ogg\–Shafarevich formula expresses the Euler characteristic of an {\'e}tale sheaf on a characteristic-p\ curve in terms of local data. The purpose of this paper is to prove an equicharacteristic version of this formula (a bound, rather than an equality). This follows work of R.\ Pink.

The basis for the proof of this result is the characteristic-p\ Riemann\–Hilbert correspondence, which is a functorial relationship between two different types of sheaves on a characteristic-p\ scheme. In the paper we prove a one-dimensional version of this correspondence, considering both local and global settings.

}, issn = {1937-0652}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.648.3584}, author = {Carl Miller} } @article {1386, title = {Efficient quantum circuits for arbitrary sparse unitaries}, journal = {Physical Review A}, volume = {80}, year = {2009}, month = {2009/12/1}, abstract = { Arbitrary exponentially large unitaries cannot be implemented efficiently by quantum circuits. However, we show that quantum circuits can efficiently implement any unitary provided it has at most polynomially many nonzero entries in any row or column, and these entries are efficiently computable. One can formulate a model of computation based on the composition of sparse unitaries which includes the quantum Turing machine model, the quantum circuit model, anyonic models, permutational quantum computation, and discrete time quantum walks as special cases. Thus we obtain a simple unified proof that these models are all contained in BQP. Furthermore our general method for implementing sparse unitaries simplifies several existing quantum algorithms. }, doi = {10.1103/PhysRevA.80.062301}, url = {http://arxiv.org/abs/0904.2211v2}, author = {Stephen P. Jordan and Pawel Wocjan} } @article {1400, title = {Efficient quantum processing of ideals in finite rings}, year = {2009}, month = {2009/07/31}, abstract = { Suppose we are given black-box access to a finite ring R, and a list of generators for an ideal I in R. We show how to find an additive basis representation for I in poly(log |R|) time. This generalizes a recent quantum algorithm of Arvind et al. which finds a basis representation for R itself. We then show that our algorithm is a useful primitive allowing quantum computers to rapidly solve a wide variety of problems regarding finite rings. In particular we show how to test whether two ideals are identical, find their intersection, find their quotient, prove whether a given ring element belongs to a given ideal, prove whether a given element is a unit, and if so find its inverse, find the additive and multiplicative identities, compute the order of an ideal, solve linear equations over rings, decide whether an ideal is maximal, find annihilators, and test the injectivity and surjectivity of ring homomorphisms. These problems appear to be hard classically. }, url = {http://arxiv.org/abs/0908.0022v1}, author = {Pawel M. Wocjan and Stephen P. Jordan and Hamed Ahmadi and Joseph P. Brennan} } @article {1511, title = {Entanglement Cost of Nonlocal Measurements}, journal = {Physical Review A}, volume = {80}, year = {2009}, month = {2009/7/15}, abstract = { For certain joint measurements on a pair of spatially separated particles, we ask how much entanglement is needed to carry out the measurement exactly. For a class of orthogonal measurements on two qubits with partially entangled eigenstates, we present upper and lower bounds on the entanglement cost. The upper bound is based on a recent result by D. Berry [Phys. Rev. A 75, 032349 (2007)]. The lower bound, based on the entanglement production capacity of the measurement, implies that for almost all measurements in the class we consider, the entanglement required to perform the measurement is strictly greater than the average entanglement of its eigenstates. On the other hand, we show that for any complete measurement in d x d dimensions that is invariant under all local Pauli operations, the cost of the measurement is exactly equal to the average entanglement of the states associated with the outcomes. }, doi = {10.1103/PhysRevA.80.012313}, url = {http://arxiv.org/abs/0809.2264v4}, author = {Somshubhro Bandyopadhyay and Gilles Brassard and Shelby Kimmel and William K. Wootters} } @article {1384, title = {Estimating Jones and HOMFLY polynomials with One Clean Qubit}, journal = {Quantum Information and Computation}, volume = {9}, year = {2009}, month = {2009/03/01}, pages = {264-289}, abstract = {

The Jones and HOMFLY polynomials are link invariants with close connections to quantum computing. It was recently shown that finding a certain approximation to the Jones polynomial of the trace closure of a braid at the fifth root of unity is a complete problem for the one clean qubit complexity class. This is the class of problems solvable in polynomial time on a quantum computer acting on an initial state in which one qubit is pure and the rest are maximally mixed. Here we generalize this result by showing that one clean qubit computers can efficiently approximate the Jones and single-variable HOMFLY polynomials of the trace closure of a braid at any root of unity.

}, url = {http://dl.acm.org/citation.cfm?id=2011787}, author = {Stephen P. Jordan and Pawel Wocjan} } @article {1483, title = {Efficient scheme for one-way quantum computing in thermal cavities}, journal = {International Journal of Theoretical Physics}, volume = {47}, year = {2008}, month = {2008/4/12}, pages = {2997 - 3004}, abstract = { We propose a practical scheme for one-way quantum computing based on efficient generation of 2D cluster state in thermal cavities. We achieve a controlled-phase gate that is neither sensitive to cavity decay nor to thermal field by adding a strong classical field to the two-level atoms. We show that a 2D cluster state can be generated directly by making every two atoms collide in an array of cavities, with numerically calculated parameters and appropriate operation sequence that can be easily achieved in practical Cavity QED experiments. Based on a generated cluster state in Box$^{(4)}$ configuration, we then implement Grover{\textquoteright}s search algorithm for four database elements in a very simple way as an example of one-way quantum computing. }, doi = {10.1007/s10773-008-9734-x}, url = {http://arxiv.org/abs/0704.2297v1}, author = {Wen-Xing Yang and Zhe-Xuan Gong} } @article {1382, title = {Estimating Jones polynomials is a complete problem for one clean qubit}, journal = {Quantum Information \& Computation}, volume = {8}, year = {2008}, month = {2008/09/01}, pages = {681-714}, abstract = {

It is known that evaluating a certain approximation to the Jones polynomial for the plat closure of a braid is a BQP-complete problem. That is, this problem exactly captures the power of the quantum circuit model. The one clean qubit model is a model of quantum computation in which all but one qubit starts in the maximally mixed state. One clean qubit computers are believed to be strictly weaker than standard quantum computers, but still capable of solving some classically intractable problems. Here we show that evaluating a certain approximation to the Jones polynomial at a fifth root of unity for the trace closure of a braid is a complete problem for the one clean qubit complexity class. That is, a one clean qubit computer can approximate these Jones polynomials in time polynomial in both the number of strands and number of crossings, and the problem of simulating a one clean qubit computer is reducible to approximating the Jones polynomial of the trace closure of a braid.

}, url = {http://dl.acm.org/citation.cfm?id=2017011.2017012}, author = {Peter W. Shor and Stephen P. Jordan} } @article {1453, title = {Existence of Universal Entangler}, journal = {Journal of Mathematical Physics}, volume = {49}, year = {2008}, month = {2008/01/01}, pages = {012103}, abstract = { A gate is called entangler if it transforms some (pure) product states to entangled states. A universal entangler is a gate which transforms all product states to entangled states. In practice, a universal entangler is a very powerful device for generating entanglements, and thus provides important physical resources for accomplishing many tasks in quantum computing and quantum information. This Letter demonstrates that a universal entangler always exists except for a degenerated case. Nevertheless, the problem how to find a universal entangler remains open. }, doi = {10.1063/1.2829895}, url = {http://arxiv.org/abs/0704.1473v2}, author = {Jianxin Chen and Runyao Duan and Zhengfeng Ji and Mingsheng Ying and Jun Yu} } @article {1291, title = {Effective-range description of a Bose gas under strong one- or two-dimensional confinement }, journal = {New Journal of Physics}, volume = {9}, year = {2007}, month = {2007/01/29}, pages = {19 - 19}, abstract = { We point out that theories describing s-wave collisions of bosonic atoms confined in one- or two-dimensional geometries can be extended to much tighter confinements than previously thought. This is achieved by replacing the scattering length by an energy-dependent scattering length which was already introduced for the calculation of energy levels under 3D confinement. This replacement accurately predicts the position of confinement-induced resonances in strongly confined geometries. }, doi = {10.1088/1367-2630/9/1/019}, url = {http://arxiv.org/abs/physics/0607140v2}, author = {Pascal Naidon and Eite Tiesinga and William F. Mitchell and Paul S. Julienne} } @article {1255, title = {Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer }, year = {2007}, month = {2007/03/02}, abstract = { For every NAND formula of size N, there is a bounded-error N^{1/2+o(1)}-time quantum algorithm, based on a coined quantum walk, that evaluates this formula on a black-box input. Balanced, or {\textquoteleft}{\textquoteleft}approximately balanced,{\textquoteright}{\textquoteright} NAND formulas can be evaluated in O(sqrt{N}) queries, which is optimal. It follows that the (2-o(1))-th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy. }, url = {http://arxiv.org/abs/quant-ph/0703015v3}, author = {Andrew M. Childs and Ben W. Reichardt and Robert Spalek and Shengyu Zhang} } @article {1481, title = {Effective error-suppression scheme for reversible quantum computer}, year = {2006}, month = {2006/08/20}, abstract = { We construct a new error-suppression scheme that makes use of the adjoint of reversible quantum algorithms. For decoherence induced errors such as depolarization, it is presented that provided the depolarization error probability is less than 1, our scheme can exponentially reduce the final output error rate to zero using a number of cycles, and the output state can be coherently sent to another stage of quantum computation process. Besides, experimental set-ups via optical approach have been proposed using Grover{\textquoteright}s search algorithm as an example. Some further discussion on the benefits and limitations of the scheme is given in the end. }, url = {http://arxiv.org/abs/quant-ph/0608152v4}, author = {Zhe-Xuan Gong} } @article {1405, title = {Effects of finite temperature on the Mott insulator state}, journal = {Physical Review A}, volume = {73}, year = {2006}, month = {2006/1/20}, abstract = { We investigate the effects of finite temperature on ultracold Bose atoms confined in an optical lattice plus a parabolic potential in the Mott insulator state. In particular, we analyze the temperature dependence of the density distribution of atomic pairs in the lattice, by means of exact Monte-Carlo simulations. We introduce a simple model that quantitatively accounts for the computed pair density distributions at low enough temperatures. We suggest that the temperature dependence of the atomic pair statistics may be used to estimate the system{\textquoteright}s temperature at energies of the order of the atoms{\textquoteright} interaction energy. }, doi = {10.1103/PhysRevA.73.013408}, url = {http://arxiv.org/abs/cond-mat/0407075v3}, author = {Guido Pupillo and Carl J. Williams and Nikolay V. Prokof{\textquoteright}ev} } @article {1394, title = {Error correcting codes for adiabatic quantum computation}, journal = {Physical Review A}, volume = {74}, year = {2006}, month = {2006/11/14}, abstract = { Recently, there has been growing interest in using adiabatic quantum computation as an architecture for experimentally realizable quantum computers. One of the reasons for this is the idea that the energy gap should provide some inherent resistance to noise. It is now known that universal quantum computation can be achieved adiabatically using 2-local Hamiltonians. The energy gap in these Hamiltonians scales as an inverse polynomial in the problem size. Here we present stabilizer codes which can be used to produce a constant energy gap against 1-local and 2-local noise. The corresponding fault-tolerant universal Hamiltonians are 4-local and 6-local respectively, which is the optimal result achievable within this framework. }, doi = {10.1103/PhysRevA.74.052322}, url = {http://arxiv.org/abs/quant-ph/0512170v3}, author = {Stephen P. Jordan and Edward Farhi and Peter W. Shor} } @article {1869, title = {Exponential iterated integrals and the relative solvable completion of the fundamental group of a manifold}, journal = {Topology}, volume = {44}, year = {2005}, month = {2005/03/01}, pages = {351 - 373}, abstract = {

We develop a class of integrals on a manifold\ M\ called\ exponential iterated integrals \ , an extension of K.T. Chen\&$\#$39;s iterated integrals. It is shown that the matrix entries of any upper triangular representation of\ π1(M,x)\ can be expressed via these new integrals. The ring of exponential iterated integrals contains the coordinate rings for a class of universal representations, called the\ relative solvable completions \ \ of\ π1(M,x). We consider exponential iterated integrals in the particular case of fibered knot complements, where the fundamental group always has a faithful relative solvable completion.

}, issn = {00409383}, doi = {10.1016/j.top.2004.10.005}, url = {http://www.sciencedirect.com/science/article/pii/S0040938304000795}, author = {Carl Miller} } @article {1263, title = {Exponential algorithmic speedup by quantum walk}, year = {2002}, month = {2002/09/24}, abstract = { We construct an oracular (i.e., black box) problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our oracular setting. We then show how this quantum walk can be used to solve our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve this problem with high probability in subexponential time. }, doi = {10.1145/780542.780552}, url = {http://arxiv.org/abs/quant-ph/0209131v2}, author = {Andrew M. Childs and Richard Cleve and Enrico Deotto and Edward Farhi and Sam Gutmann and Daniel A. Spielman} } @article {1248, title = {Exact sampling from non-attractive distributions using summary states}, journal = {Physical Review E}, volume = {63}, year = {2001}, month = {2001/2/22}, abstract = { Propp and Wilson{\textquoteright}s method of coupling from the past allows one to efficiently generate exact samples from attractive statistical distributions (e.g., the ferromagnetic Ising model). This method may be generalized to non-attractive distributions by the use of summary states, as first described by Huber. Using this method, we present exact samples from a frustrated antiferromagnetic triangular Ising model and the antiferromagnetic q=3 Potts model. We discuss the advantages and limitations of the method of summary states for practical sampling, paying particular attention to the slowing down of the algorithm at low temperature. In particular, we show that such a slowing down can occur in the absence of a physical phase transition. }, doi = {10.1103/PhysRevE.63.036113}, url = {http://arxiv.org/abs/cond-mat/0005132v1}, author = {Andrew M. Childs and Ryan B. Patterson and David J. C. MacKay} } @article {1208, title = {An example of the difference between quantum and classical random walks}, journal = {Quantum Information Processing}, volume = {1}, year = {2001}, month = {2002/04/01}, pages = {35 - 43}, abstract = { In this note, we discuss a general definition of quantum random walks on graphs and illustrate with a simple graph the possibility of very different behavior between a classical random walk and its quantum analogue. In this graph, propagation between a particular pair of nodes is exponentially faster in the quantum case. }, doi = {10.1023/A:1019609420309}, url = {http://arxiv.org/abs/quant-ph/0103020v1}, author = {Andrew M. Childs and Edward Farhi and Sam Gutmann} }