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.

1 aRoth, Ingo1 aKueng, Richard1 aKimmel, Shelby1 aLiu, Yi-Kai1 aGross, David1 aEisert, Jens1 aKliesch, Martin uhttps://arxiv.org/abs/1803.0057201121nas a2200169 4500008004100000245007000041210006900111260001500180300001100195490000800206520058700214100002200801700001900823700001900842700001700861856007300878 2017 eng d00aExperimental demonstration of cheap and accurate phase estimation0 aExperimental demonstration of cheap and accurate phase estimatio c2017/05/12 a1905020 v1183 aWe 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.

1 aRudinger, Kenneth1 aKimmel, Shelby1 aLobser, Daniel1 aMaunz, Peter uhttps://journals.aps.org/prl/abstract/10.1103/PhysRevLett.118.19050201826nas a2200169 4500008004100000245005800041210005800099260001500157490000700172520131900179100001901498700002401517700002001541700001701561700002401578856005401602 2017 eng d00aHamiltonian Simulation with Optimal Sample Complexity0 aHamiltonian Simulation with Optimal Sample Complexity c2017/03/310 v133 aWe 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.

1 aKimmel, Shelby1 aLiu, Yi-Kai uhttp://ieeexplore.ieee.org/document/8024414/01240nas a2200121 4500008004100000245006900041210006900110260001500179520084800194100002001042700001901062856003701081 2017 eng d00aQuantum Algorithms for Graph Connectivity and Formula Evaluation0 aQuantum Algorithms for Graph Connectivity and Formula Evaluation c2017/04/033 aWe 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.

1 aJeffery, Stacey1 aKimmel, Shelby uhttps://arxiv.org/abs/1704.0076501010nas a2200145 4500008004100000245007200041210006800113260001500181490000700196520056900203100001800772700001900790700001900809856003600828 2016 eng d00aA Quantum Version of SchÃ¶ning's Algorithm Applied to Quantum 2-SAT0 aQuantum Version of SchÃ¶nings Algorithm Applied to Quantum 2SAT c2016/03/220 v163 aWe 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.

1 aFarhi, Edward1 aKimmel, Shelby1 aTemme, Kristan uhttp://arxiv.org/abs/1603.0698501589nas a2200193 4500008004100000245008100041210006900122260001500191300001100206490000700217520100800224100002301232700002501255700001901280700001901299700002001318700002101338856003601359 2015 eng d00aDemonstration of Robust Quantum Gate Tomography via Randomized Benchmarking0 aDemonstration of Robust Quantum Gate Tomography via Randomized B c2015/11/05 a1130190 v173 a 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. 1 aJohnson, Blake, R.1 ada Silva, Marcus, P.1 aRyan, Colm, A.1 aKimmel, Shelby1 aChow, Jerry, M.1 aOhki, Thomas, A. uhttp://arxiv.org/abs/1505.0668601035nas a2200181 4500008004100000020002200041022001400063245002300077210002300100260001500123300000900138490000700147520060100154100001900755700002400774700001900798856003600817 2015 eng d a978-3-939897-96-5 a1868-896900aOracles with Costs0 aOracles with Costs c2015/02/07 a1-260 v443 a 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. 1 aKimmel, Shelby1 aLin, Cedric, Yen-Yu1 aLin, Han-Hsuan uhttp://arxiv.org/abs/1502.0217401216nas a2200121 4500008004100000245004700041210004600088260001500134520087400149100001901023700001601042856003601058 2015 eng d00aQuantum Compressed Sensing Using 2-Designs0 aQuantum Compressed Sensing Using 2Designs c2015/10/293 aWe 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.1 aKimmel, Shelby1 aLiu, Yi-Kai uhttp://arxiv.org/abs/1510.0888701003nas a2200121 4500008004100000245005600041210005600097260001500153520063800168100002000806700001900826856003600845 2015 eng d00aQuantum vs Classical Proofs and Subset Verification0 aQuantum vs Classical Proofs and Subset Verification c2015/10/223 aWe 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.1 aFefferman, Bill1 aKimmel, Shelby uhttp://arxiv.org/abs/1510.0675001534nas a2200157 4500008004100000245007200041210006900113260001500182300001100197490000700208520106200215100001901277700002001296700002401316856003601340 2015 eng d00aRobust Single-Qubit Process Calibration via Robust Phase Estimation0 aRobust SingleQubit Process Calibration via Robust Phase Estimati c2015/12/08 a0623150 v923 a 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)]. 1 aKimmel, Shelby1 aLow, Guang, Hao1 aYoder, Theodore, J. uhttp://arxiv.org/abs/1502.0267701337nas a2200169 4500008004100000245007700041210006900118260001400187490000600201520082000207100001901027700002501046700001901071700002301090700001701113856003701130 2014 eng d00aRobust Extraction of Tomographic Information via Randomized Benchmarking0 aRobust Extraction of Tomographic Information via Randomized Benc c2014/3/250 v43 a 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. 1 aKimmel, Shelby1 ada Silva, Marcus, P.1 aRyan, Colm, A.1 aJohnson, Blake, R.1 aOhki, Thomas uhttp://arxiv.org/abs/1306.2348v100905nas a2200133 4500008004100000245003600041210003400077260001500111300001100126490000700137520057100144100001900715856003700734 2013 eng d00aQuantum Adversary (Upper) Bound0 aQuantum Adversary Upper Bound c2013/04/05 a1 - 140 v193 a 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. 1 aKimmel, Shelby uhttp://arxiv.org/abs/1101.0797v501823nas a2200157 4500008004100000245005500041210005000096260001500146300001200161490000900173520138500182100002301567700001901590700001901609856003701628 2012 eng d00aThe quantum query complexity of read-many formulas0 aquantum query complexity of readmany formulas c2012/09/10 a337-3480 v75013 a 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. 1 aChilds, Andrew, M.1 aKimmel, Shelby1 aKothari, Robin uhttp://arxiv.org/abs/1112.0548v101009nas a2200157 4500008004100000020002200041245009100063210006900154260001500223300001200238520050600250100001600756700001900772700002300791856003700814 2012 eng d a978-1-4503-1115-100aSuper-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure0 aSuperPolynomial Quantum Speedups for Boolean Evaluation Trees wi c2012/01/08 a249-2653 a 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. 1 aZhan, Bohua1 aKimmel, Shelby1 aHassidim, Avinatan uhttp://arxiv.org/abs/1101.0796v301370nas a2200157 4500008004100000245004700041210004700088260001400135490000700149520092300156100003001079700002101109700001901130700002601149856003701175 2009 eng d00aEntanglement Cost of Nonlocal Measurements0 aEntanglement Cost of Nonlocal Measurements c2009/7/150 v803 a 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. 1 aBandyopadhyay, Somshubhro1 aBrassard, Gilles1 aKimmel, Shelby1 aWootters, William, K. uhttp://arxiv.org/abs/0809.2264v4