TY - JOUR T1 - Quantum Computer Systems for Scientific Discovery Y1 - 2019 A1 - Yuri Alexeev A1 - Dave Bacon A1 - Kenneth R. Brown A1 - Robert Calderbank A1 - Lincoln D. Carr A1 - Frederic T. Chong A1 - Brian DeMarco A1 - Dirk Englund A1 - Edward Farhi A1 - Bill Fefferman A1 - Alexey V. Gorshkov A1 - Andrew Houck A1 - Jungsang Kim A1 - Shelby Kimmel A1 - Michael Lange A1 - Seth Lloyd A1 - Mikhail D. Lukin A1 - Dmitri Maslov A1 - Peter Maunz A1 - Christopher Monroe A1 - John Preskill A1 - Martin Roetteler A1 - Martin Savage A1 - Jeff Thompson A1 - Umesh Vazirani AB -

The great promise of quantum computers comes with the dual challenges of building them and finding their useful applications. We argue that these two challenges should be considered together, by co-designing full stack quantum computer systems along with their applications in order to hasten their development and potential for scientific discovery. In this context, we identify scientific and community needs, opportunities, and significant challenges for the development of quantum computers for science over the next 2-10 years. This document is written by a community of university, national laboratory, and industrial researchers in the field of Quantum Information Science and Technology, and is based on a summary from a U.S. National Science Foundation workshop on Quantum Computing held on October 21-22, 2019 in Alexandria, VA.

UR - https://arxiv.org/abs/1912.07577 ER - TY - JOUR T1 - Recovering quantum gates from few average gate fidelities JF - Phys. Rev. Lett. Y1 - 2018 A1 - Ingo Roth A1 - Richard Kueng A1 - Shelby Kimmel A1 - Yi-Kai Liu A1 - David Gross A1 - Jens Eisert A1 - Martin Kliesch AB -

Characterising quantum processes is a key task in and constitutes a challenge for the development of quantum technologies, especially at the noisy intermediate scale of today's devices. One method for characterising processes is randomised benchmarking, which is robust against state preparation and measurement (SPAM) errors, and can be used to benchmark Clifford gates. A complementing approach asks for full tomographic knowledge. Compressed sensing techniques achieve full tomography of quantum channels essentially at optimal resource efficiency. So far, guarantees for compressed sensing protocols rely on unstructured random measurements and can not be applied to the data acquired from randomised benchmarking experiments. It has been an open question whether or not the favourable features of both worlds can be combined. In this work, we give a positive answer to this question. For the important case of characterising multi-qubit unitary gates, we provide a rigorously guaranteed and practical reconstruction method that works with an essentially optimal number of average gate fidelities measured respect to random Clifford unitaries. Moreover, for general unital quantum channels we provide an explicit expansion into a unitary 2-design, allowing for a practical and guaranteed reconstruction also in that case. As a side result, we obtain a new statistical interpretation of the unitarity -- a figure of merit that characterises the coherence of a process. In our proofs we exploit recent representation theoretic insights on the Clifford group, develop a version of Collins' calculus with Weingarten functions for integration over the Clifford group, and combine this with proof techniques from compressed sensing.

VL - 121 U4 - 170502 UR - https://arxiv.org/abs/1803.00572 U5 - https://doi.org/10.1103/PhysRevLett.121.170502 ER - TY - JOUR T1 - Experimental demonstration of cheap and accurate phase estimation JF - Physical Review Letters Y1 - 2017 A1 - Kenneth Rudinger A1 - Shelby Kimmel A1 - Daniel Lobser A1 - Peter Maunz AB -

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.

VL - 118 U4 - 190502 UR - https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.118.190502 CP - 19 U5 - doi.org/10.1103/PhysRevLett.118.190502 ER - TY - JOUR T1 - Hamiltonian Simulation with Optimal Sample Complexity JF - npj Quantum Information Y1 - 2017 A1 - Shelby Kimmel A1 - Cedric Yen-Yu Lin A1 - Guang Hao Low A1 - Maris Ozols A1 - Theodore J. Yoder AB -
We investigate the sample complexity of Hamiltonian simulation: how many copies of an unknown quantum state are required to simulate a Hamiltonian encoded by the density matrix of that state? We show that the procedure proposed by Lloyd, Mohseni, and Rebentrost [Nat. Phys., 10(9):631--633, 2014] is optimal for this task. We further extend their method to the case of multiple input states, showing how to simulate any Hermitian polynomial of the states provided. As applications, we derive optimal algorithms for commutator simulation and orthogonality testing, and we give a protocol for creating a coherent superposition of pure states, when given sample access to those states. We also show that this sample-based Hamiltonian simulation can be used as the basis of a universal model of quantum computation that requires only partial swap operations and simple single-qubit states.
 
 
VL - 13 UR - https://www.nature.com/articles/s41534-017-0013-7 CP - 3 U5 - 10.1038/s41534-017-0013-7 ER - TY - CONF T1 - Phase retrieval using unitary 2-designs T2 - SampTA 2017 Y1 - 2017 A1 - Shelby Kimmel A1 - Yi-Kai Liu AB -

We consider a variant of the phase retrieval problem, where vectors are replaced by unitary matrices, i.e., the unknown signal is a unitary matrix U, and the measurements consist of squared inner products |tr(C†U)|2 with unitary matrices C that are chosen by the observer. This problem has applications to quantum process tomography, when the unknown process is a unitary operation. We show that PhaseLift, a convex programming algorithm for phase retrieval, can be adapted to this matrix setting, using measurements that are sampled from unitary 4- and 2-designs. In the case of unitary 4-design measurements, we show that PhaseLift can reconstruct all unitary matrices, using a nearoptimal number of measurements. This extends previous work on PhaseLift using spherical 4-designs. In the case of unitary 2-design measurements, we show that PhaseLift still works pretty well on average: it recovers almost all signals, up to a constant additive error, using a near-optimal number of measurements. These 2-design measurements are convenient for quantum process tomography, as they can be implemented via randomized benchmarking techniques. This is the first positive result on PhaseLift using 2-designs.

JA - SampTA 2017 UR - http://ieeexplore.ieee.org/document/8024414/ U5 - 10.1109/SAMPTA.2017.8024414 ER - TY - JOUR T1 - Quantum Algorithms for Graph Connectivity and Formula Evaluation Y1 - 2017 A1 - Stacey Jeffery A1 - Shelby Kimmel AB -

We give a new upper bound on the quantum query complexity of deciding st-connectivity on certain classes of planar graphs, and show the bound is sometimes exponentially better than previous results. We then show Boolean formula evaluation reduces to deciding connectivity on just such a class of graphs. Applying the algorithm for st-connectivity to Boolean formula evaluation problems, we match the O( √ N) bound on the quantum query complexity of evaluating formulas on N variables, give a quadratic speed-up over the classical query complexity of a certain class of promise Boolean formulas, and show this approach can yield superpolynomial quantum/classical separations. These results indicate that this st-connectivity-based approach may be the “right” way of looking at quantum algorithms for formula evaluation.

UR - https://arxiv.org/abs/1704.00765 ER - TY - JOUR T1 - A Quantum Version of Schöning's Algorithm Applied to Quantum 2-SAT JF - Quantum Information and Computation Y1 - 2016 A1 - Edward Farhi A1 - Shelby Kimmel A1 - Kristan Temme AB -

We study a quantum algorithm that consists of a simple quantum Markov process, and we analyze its behavior on restricted versions of Quantum 2-SAT. We prove that the algorithm solves this decision problem with high probability for n qubits, L clauses, and promise gap c in time O(n^2 L^2 c^{-2}). If the Hamiltonian is additionally polynomially gapped, our algorithm efficiently produces a state that has high overlap with the satisfying subspace. The Markov process we study is a quantum analogue of Sch\"oning's probabilistic algorithm for k-SAT.

VL - 16 UR - http://arxiv.org/abs/1603.06985 CP - 13-14 ER - TY - JOUR T1 - Demonstration of Robust Quantum Gate Tomography via Randomized Benchmarking JF - New Journal of Physics Y1 - 2015 A1 - Blake R. Johnson A1 - Marcus P. da Silva A1 - Colm A. Ryan A1 - Shelby Kimmel A1 - Jerry M. Chow A1 - Thomas A. Ohki AB - Typical quantum gate tomography protocols struggle with a self-consistency problem: the gate operation cannot be reconstructed without knowledge of the initial state and final measurement, but such knowledge cannot be obtained without well-characterized gates. A recently proposed technique, known as randomized benchmarking tomography (RBT), sidesteps this self-consistency problem by designing experiments to be insensitive to preparation and measurement imperfections. We implement this proposal in a superconducting qubit system, using a number of experimental improvements including implementing each of the elements of the Clifford group in single `atomic' pulses and custom control hardware to enable large overhead protocols. We show a robust reconstruction of several single-qubit quantum gates, including a unitary outside the Clifford group. We demonstrate that RBT yields physical gate reconstructions that are consistent with fidelities obtained by randomized benchmarking. VL - 17 U4 - 113019 UR - http://arxiv.org/abs/1505.06686 CP - 11 U5 - 10.1088/1367-2630/17/11/113019 ER - TY - JOUR T1 - Oracles with Costs JF - 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015) Y1 - 2015 A1 - Shelby Kimmel A1 - Cedric Yen-Yu Lin A1 - Han-Hsuan Lin AB - While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal. VL - 44 U4 - 1-26 SN - 978-3-939897-96-5 UR - http://arxiv.org/abs/1502.02174 U5 - 10.4230/LIPIcs.TQC.2015.1 ER - TY - JOUR T1 - Quantum Compressed Sensing Using 2-Designs Y1 - 2015 A1 - Shelby Kimmel A1 - Yi-Kai Liu AB - We develop a method for quantum process tomography that combines the efficiency of compressed sensing with the robustness of randomized benchmarking. Our method is robust to state preparation and measurement errors, and it achieves a quadratic speedup over conventional tomography when the unknown process is a generic unitary evolution. Our method is based on PhaseLift, a convex programming technique for phase retrieval. We show that this method achieves approximate recovery of almost all signals, using measurements sampled from spherical or unitary 2-designs. This is the first positive result on PhaseLift using 2-designs. We also show that exact recovery of all signals is possible using unitary 4-designs. Previous positive results for PhaseLift required spherical 4-designs, while PhaseLift was known to fail in certain cases when using spherical 2-designs. UR - http://arxiv.org/abs/1510.08887 ER - TY - JOUR T1 - Quantum vs Classical Proofs and Subset Verification Y1 - 2015 A1 - Bill Fefferman A1 - Shelby Kimmel AB - We study the ability of efficient quantum verifiers to decide properties of exponentially large subsets given either a classical or quantum witness. We develop a general framework that can be used to prove that QCMA machines, with only classical witnesses, cannot verify certain properties of subsets given implicitly via an oracle. We use this framework to prove an oracle separation between QCMA and QMA using an ``in-place'' permutation oracle, making the first progress on this question since Aaronson and Kuperberg in 2007. We also use the framework to prove a particularly simple standard oracle separation between QCMA and AM. UR - http://arxiv.org/abs/1510.06750 ER - TY - JOUR T1 - Robust Single-Qubit Process Calibration via Robust Phase Estimation JF - Physical Review A Y1 - 2015 A1 - Shelby Kimmel A1 - Guang Hao Low A1 - Theodore J. Yoder AB - An important step in building a quantum computer is calibrating experimentally implemented quantum gates to produce operations that are close to ideal unitaries. The calibration step involves estimating the error in gates and then using controls to correct the implementation. Quantum process tomography is a standard technique for estimating these errors, but is both time consuming, (when one only wants to learn a few key parameters), and requires resources, like perfect state preparation and measurement, that might not be available. With the goal of efficiently estimating specific errors using minimal resources, we develop a parameter estimation technique, which can gauge two key parameters (amplitude and off-resonance errors) in a single-qubit gate with provable robustness and efficiency. In particular, our estimates achieve the optimal efficiency, Heisenberg scaling. Our main theorem making this possible is a robust version of the phase estimation procedure of Higgins et al. [B. L. Higgins, New J. Phys. 11, 073023 (2009)]. VL - 92 U4 - 062315 UR - http://arxiv.org/abs/1502.02677 CP - 6 U5 - 10.1103/PhysRevA.92.062315 ER - TY - JOUR T1 - Robust Extraction of Tomographic Information via Randomized Benchmarking JF - Physical Review X Y1 - 2014 A1 - Shelby Kimmel A1 - Marcus P. da Silva A1 - Colm A. Ryan A1 - Blake R. Johnson A1 - Thomas Ohki AB - We describe how randomized benchmarking can be used to reconstruct the unital part of any trace-preserving quantum map, which in turn is sufficient for the full characterization of any unitary evolution, or more generally, any unital trace-preserving evolution. This approach inherits randomized benchmarking's robustness to preparation and measurement imperfections, therefore avoiding systematic errors caused by these imperfections. We also extend these techniques to efficiently estimate the average fidelity of a quantum map to unitary maps outside of the Clifford group. The unitaries we consider include operations commonly used to achieve universal quantum computation in a fault-tolerant setting. In addition, we rigorously bound the time and sampling complexities of randomized benchmarking procedures. VL - 4 UR - http://arxiv.org/abs/1306.2348v1 CP - 1 J1 - Phys. Rev. X U5 - 10.1103/PhysRevX.4.011050 ER - TY - JOUR T1 - Quantum Adversary (Upper) Bound JF - Chicago Journal of Theoretical Computer Science Y1 - 2013 A1 - Shelby Kimmel AB - We describe a method to upper bound the quantum query complexity of Boolean formula evaluation problems, using fundamental theorems about the general adversary bound. This nonconstructive method can give an upper bound on query complexity without producing an algorithm. For example, we describe an oracle problem which we prove (non-constructively) can be solved in $O(1)$ queries, where the previous best quantum algorithm uses a polylogarithmic number of queries. We then give an explicit $O(1)$-query algorithm for this problem based on span programs. VL - 19 U4 - 1 - 14 UR - http://arxiv.org/abs/1101.0797v5 CP - 1 J1 - Chicago J. of Theoretical Comp. Sci. U5 - 10.4086/cjtcs.2013.004 ER - TY - JOUR T1 - The quantum query complexity of read-many formulas JF - Lecture Notes in Computer Science Y1 - 2012 A1 - Andrew M. Childs A1 - Shelby Kimmel A1 - Robin Kothari AB - The quantum query complexity of evaluating any read-once formula with n black-box input bits is Theta(sqrt(n)). However, the corresponding problem for read-many formulas (i.e., formulas in which the inputs have fanout) is not well understood. Although the optimal read-once formula evaluation algorithm can be applied to any formula, it can be suboptimal if the inputs have large fanout. We give an algorithm for evaluating any formula with n inputs, size S, and G gates using O(min{n, sqrt{S}, n^{1/2} G^{1/4}}) quantum queries. Furthermore, we show that this algorithm is optimal, since for any n,S,G there exists a formula with n inputs, size at most S, and at most G gates that requires Omega(min{n, sqrt{S}, n^{1/2} G^{1/4}}) queries. We also show that the algorithm remains nearly optimal for circuits of any particular depth k >= 3, and we give a linear-size circuit of depth 2 that requires Omega (n^{5/9}) queries. Applications of these results include a Omega (n^{19/18}) lower bound for Boolean matrix product verification, a nearly tight characterization of the quantum query complexity of evaluating constant-depth circuits with bounded fanout, new formula gate count lower bounds for several functions including PARITY, and a construction of an AC^0 circuit of linear size that can only be evaluated by a formula with Omega(n^{2-epsilon}) gates. VL - 7501 U4 - 337-348 UR - http://arxiv.org/abs/1112.0548v1 J1 - Lecture Notes in Computer Science 7501 U5 - 10.1007/978-3-642-33090-2_30 ER - TY - JOUR T1 - Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure JF - ITCS '12 Proceedings of the 3rd Innovations in Theoretical Computer Science Conference Y1 - 2012 A1 - Bohua Zhan A1 - Shelby Kimmel A1 - Avinatan Hassidim AB - We give a quantum algorithm for evaluating a class of boolean formulas (such as NAND trees and 3-majority trees) on a restricted set of inputs. Due to the structure of the allowed inputs, our algorithm can evaluate a depth $n$ tree using $O(n^{2+\log\omega})$ queries, where $\omega$ is independent of $n$ and depends only on the type of subformulas within the tree. We also prove a classical lower bound of $n^{\Omega(\log\log n)}$ queries, thus showing a (small) super-polynomial speed-up. U4 - 249-265 SN - 978-1-4503-1115-1 UR - http://arxiv.org/abs/1101.0796v3 J1 - ITCS 2012 Proceedings of the 3rd Innovations in Theoretical Computer Science U5 - 10.1145/2090236.2090258 ER - TY - JOUR T1 - Entanglement Cost of Nonlocal Measurements JF - Physical Review A Y1 - 2009 A1 - Somshubhro Bandyopadhyay A1 - Gilles Brassard A1 - Shelby Kimmel A1 - William K. Wootters AB - 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. VL - 80 UR - http://arxiv.org/abs/0809.2264v4 CP - 1 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.80.012313 ER -