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\&$\#$39;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\&$\#$39; calculus with Weingarten functions for integration over the Clifford group, and combine this with proof techniques from compressed sensing.

}, doi = {https://doi.org/10.1103/PhysRevLett.121.170502}, url = {https://arxiv.org/abs/1803.00572}, author = {Ingo Roth and Richard Kueng and Shelby Kimmel and Yi-Kai Liu and David Gross and Jens Eisert and Martin Kliesch} } @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 {1812, title = {Hamiltonian Simulation with Optimal Sample Complexity}, journal = {npj Quantum Information}, volume = {13}, year = {2017}, month = {2017/03/31}, abstract = {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.

\

},
doi = {10.1038/s41534-017-0013-7},
url = {https://www.nature.com/articles/s41534-017-0013-7},
author = {Shelby Kimmel and Cedric Yen-Yu Lin and Guang Hao Low and Maris Ozols and Theodore J. Yoder}
}
@conference {2140,
title = {Phase retrieval using unitary 2-designs},
booktitle = {SampTA 2017},
year = {2017},
month = {2017/07},
abstract = {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.

}, doi = {10.1109/SAMPTA.2017.8024414}, url = {http://ieeexplore.ieee.org/document/8024414/}, author = {Shelby Kimmel and Yi-Kai Liu} } @article {1989, title = {Quantum Algorithms for Graph Connectivity and Formula Evaluation}, year = {2017}, month = {2017/04/03}, abstract = {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.

}, url = {https://arxiv.org/abs/1704.00765}, author = {Stacey Jeffery and Shelby Kimmel} } @article {1733, title = {A Quantum Version of Sch{\"o}ning{\textquoteright}s Algorithm Applied to Quantum 2-SAT}, journal = {Quantum Information and Computation}, volume = {16}, year = {2016}, month = {2016/03/22}, abstract = {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\&$\#$39;s probabilistic algorithm for k-SAT.

}, url = {http://arxiv.org/abs/1603.06985}, author = {Edward Farhi and Shelby Kimmel and Kristan Temme} } @article {1515, title = {Demonstration of Robust Quantum Gate Tomography via Randomized Benchmarking}, journal = {New Journal of Physics}, volume = {17}, year = {2015}, month = {2015/11/05}, pages = {113019}, abstract = { 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 {\textquoteleft}atomic{\textquoteright} 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. }, doi = {10.1088/1367-2630/17/11/113019}, url = {http://arxiv.org/abs/1505.06686}, author = {Blake R. Johnson and Marcus P. da Silva and Colm A. Ryan and Shelby Kimmel and Jerry M. Chow and Thomas A. Ohki} } @article {1512, title = {Oracles with Costs}, journal = {10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)}, volume = {44}, year = {2015}, month = {2015/02/07}, pages = {1-26}, abstract = { 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{\textquoteright}s algorithm, that our algorithm is exactly optimal. }, isbn = {978-3-939897-96-5}, issn = {1868-8969}, doi = {10.4230/LIPIcs.TQC.2015.1}, url = {http://arxiv.org/abs/1502.02174}, author = {Shelby Kimmel and Cedric Yen-Yu Lin and Han-Hsuan Lin} } @article {1596, title = {Quantum Compressed Sensing Using 2-Designs}, year = {2015}, month = {2015/10/29}, abstract = {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.}, url = {http://arxiv.org/abs/1510.08887}, author = {Shelby Kimmel and Yi-Kai Liu} } @article {1592, title = {Quantum vs Classical Proofs and Subset Verification}, year = {2015}, month = {2015/10/22}, abstract = {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 {\textquoteleft}{\textquoteleft}in-place{\textquoteright}{\textquoteright} 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.}, url = {http://arxiv.org/abs/1510.06750}, author = {Bill Fefferman and Shelby Kimmel} } @article {1513, title = {Robust Single-Qubit Process Calibration via Robust Phase Estimation}, journal = {Physical Review A}, volume = {92}, year = {2015}, month = {2015/12/08}, pages = {062315}, abstract = { 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)]. }, doi = {10.1103/PhysRevA.92.062315}, url = {http://arxiv.org/abs/1502.02677}, author = {Shelby Kimmel and Guang Hao Low and Theodore J. Yoder} } @article {1514, title = {Robust Extraction of Tomographic Information via Randomized Benchmarking}, journal = {Physical Review X}, volume = {4}, year = {2014}, month = {2014/3/25}, abstract = { 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{\textquoteright}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. }, doi = {10.1103/PhysRevX.4.011050}, url = {http://arxiv.org/abs/1306.2348v1}, author = {Shelby Kimmel and Marcus P. da Silva and Colm A. Ryan and Blake R. Johnson and Thomas Ohki} } @article {1508, title = {Quantum Adversary (Upper) Bound}, journal = {Chicago Journal of Theoretical Computer Science}, volume = {19}, year = {2013}, month = {2013/04/05}, pages = {1 - 14}, abstract = { 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. }, doi = {10.4086/cjtcs.2013.004}, url = {http://arxiv.org/abs/1101.0797v5}, author = {Shelby Kimmel} } @article {1222, title = {The quantum query complexity of read-many formulas}, journal = {Lecture Notes in Computer Science}, volume = {7501}, year = {2012}, month = {2012/09/10}, pages = {337-348}, abstract = { 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. }, doi = {10.1007/978-3-642-33090-2_30}, url = {http://arxiv.org/abs/1112.0548v1}, author = {Andrew M. Childs and Shelby Kimmel and Robin Kothari} } @article {1510, title = {Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure}, journal = {ITCS {\textquoteright}12 Proceedings of the 3rd Innovations in Theoretical Computer Science Conference}, year = {2012}, month = {2012/01/08}, pages = {249-265}, abstract = { 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. }, isbn = {978-1-4503-1115-1}, doi = {10.1145/2090236.2090258}, url = {http://arxiv.org/abs/1101.0796v3}, author = {Bohua Zhan and Shelby Kimmel and Avinatan Hassidim} } @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} }