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.

%B Phys. Rev. Lett. %V 121 %P 170502 %8 2018/03/01 %G eng %U https://arxiv.org/abs/1803.00572 %R https://doi.org/10.1103/PhysRevLett.121.170502 %0 Journal Article %J Physical Review Letters %D 2017 %T Experimental demonstration of cheap and accurate phase estimation %A Kenneth Rudinger %A Shelby Kimmel %A Daniel Lobser %A Peter Maunz %XWe 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.

%B Physical Review Letters %V 118 %P 190502 %8 2017/05/12 %G eng %U https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.118.190502 %N 19 %R doi.org/10.1103/PhysRevLett.118.190502 %0 Journal Article %J npj Quantum Information %D 2017 %T Hamiltonian Simulation with Optimal Sample Complexity %A Shelby Kimmel %A Cedric Yen-Yu Lin %A Guang Hao Low %A Maris Ozols %A Theodore J. Yoder %XWe 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.

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.

%B SampTA 2017 %8 2017/07 %G eng %U http://ieeexplore.ieee.org/document/8024414/ %R 10.1109/SAMPTA.2017.8024414 %0 Journal Article %D 2017 %T Quantum Algorithms for Graph Connectivity and Formula Evaluation %A Stacey Jeffery %A Shelby Kimmel %XWe 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.

%8 2017/04/03 %G eng %U https://arxiv.org/abs/1704.00765 %0 Journal Article %J Quantum Information and Computation %D 2016 %T A Quantum Version of SchÃ¶ning's Algorithm Applied to Quantum 2-SAT %A Edward Farhi %A Shelby Kimmel %A Kristan Temme %XWe 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.

%B Quantum Information and Computation %V 16 %8 2016/03/22 %G eng %U http://arxiv.org/abs/1603.06985 %N 13-14 %0 Journal Article %J New Journal of Physics %D 2015 %T Demonstration of Robust Quantum Gate Tomography via Randomized Benchmarking %A Blake R. Johnson %A Marcus P. da Silva %A Colm A. Ryan %A Shelby Kimmel %A Jerry M. Chow %A Thomas A. Ohki %X 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. %B New Journal of Physics %V 17 %P 113019 %8 2015/11/05 %G eng %U http://arxiv.org/abs/1505.06686 %N 11 %R 10.1088/1367-2630/17/11/113019 %0 Journal Article %J 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015) %D 2015 %T Oracles with Costs %A Shelby Kimmel %A Cedric Yen-Yu Lin %A Han-Hsuan Lin %X 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. %B 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015) %V 44 %P 1-26 %8 2015/02/07 %@ 978-3-939897-96-5 %G eng %U http://arxiv.org/abs/1502.02174 %R 10.4230/LIPIcs.TQC.2015.1 %0 Journal Article %D 2015 %T Quantum Compressed Sensing Using 2-Designs %A Shelby Kimmel %A Yi-Kai Liu %X 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. %8 2015/10/29 %G eng %U http://arxiv.org/abs/1510.08887 %0 Journal Article %D 2015 %T Quantum vs Classical Proofs and Subset Verification %A Bill Fefferman %A Shelby Kimmel %X 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. %8 2015/10/22 %G eng %U http://arxiv.org/abs/1510.06750 %0 Journal Article %J Physical Review A %D 2015 %T Robust Single-Qubit Process Calibration via Robust Phase Estimation %A Shelby Kimmel %A Guang Hao Low %A Theodore J. Yoder %X 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)]. %B Physical Review A %V 92 %P 062315 %8 2015/12/08 %G eng %U http://arxiv.org/abs/1502.02677 %N 6 %R 10.1103/PhysRevA.92.062315 %0 Journal Article %J Physical Review X %D 2014 %T Robust Extraction of Tomographic Information via Randomized Benchmarking %A Shelby Kimmel %A Marcus P. da Silva %A Colm A. Ryan %A Blake R. Johnson %A Thomas Ohki %X 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. %B Physical Review X %V 4 %8 2014/3/25 %G eng %U http://arxiv.org/abs/1306.2348v1 %N 1 %! Phys. Rev. X %R 10.1103/PhysRevX.4.011050 %0 Journal Article %J Chicago Journal of Theoretical Computer Science %D 2013 %T Quantum Adversary (Upper) Bound %A Shelby Kimmel %X 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. %B Chicago Journal of Theoretical Computer Science %V 19 %P 1 - 14 %8 2013/04/05 %G eng %U http://arxiv.org/abs/1101.0797v5 %N 1 %! Chicago J. of Theoretical Comp. Sci. %R 10.4086/cjtcs.2013.004 %0 Journal Article %J Lecture Notes in Computer Science %D 2012 %T The quantum query complexity of read-many formulas %A Andrew M. Childs %A Shelby Kimmel %A Robin Kothari %X 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. %B Lecture Notes in Computer Science %V 7501 %P 337-348 %8 2012/09/10 %G eng %U http://arxiv.org/abs/1112.0548v1 %! Lecture Notes in Computer Science 7501 %R 10.1007/978-3-642-33090-2_30 %0 Journal Article %J ITCS '12 Proceedings of the 3rd Innovations in Theoretical Computer Science Conference %D 2012 %T Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure %A Bohua Zhan %A Shelby Kimmel %A Avinatan Hassidim %X 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. %B ITCS '12 Proceedings of the 3rd Innovations in Theoretical Computer Science Conference %P 249-265 %8 2012/01/08 %@ 978-1-4503-1115-1 %G eng %U http://arxiv.org/abs/1101.0796v3 %! ITCS 2012 Proceedings of the 3rd Innovations in Theoretical Computer Science %R 10.1145/2090236.2090258 %0 Journal Article %J Physical Review A %D 2009 %T Entanglement Cost of Nonlocal Measurements %A Somshubhro Bandyopadhyay %A Gilles Brassard %A Shelby Kimmel %A William K. Wootters %X 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. %B Physical Review A %V 80 %8 2009/7/15 %G eng %U http://arxiv.org/abs/0809.2264v4 %N 1 %! Phys. Rev. A %R 10.1103/PhysRevA.80.012313