02031nas a2200121 4500008004100000245006200041210006200103260001500165520165100180100001701831700002401848856003701872 2023 eng d00aSecret extraction attacks against obfuscated IQP circuits0 aSecret extraction attacks against obfuscated IQP circuits c12/15/20233 a

Quantum computing devices can now perform sampling tasks which, according to complexity-theoretic and numerical evidence, are beyond the reach of classical computers. This raises the question of how one can efficiently verify that a quantum computer operating in this regime works as intended. In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of so-called IQP circuits, and challenges a prover to execute it on a quantum computer. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test that accepts samples from a correct quantum implementation. It was conjectured that extracting the secret from the challenge problem is NP-hard, so that the ability to pass the test constitutes strong evidence that the prover possesses a quantum device and that it works as claimed. Unfortunately, about a decade later, Kahanamoku-Meyer found an efficient classical secret extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol. Their IQP Stabilizer Scheme has been explicitly designed to circumvent the known weakness. They also suggested that the original construction can be made secure by adjusting the problem parameters. In this work, we develop a number of secret extraction attacks which are effective against both new approaches in a wide range of problem parameters. The important problem of finding an efficient and reliable verification protocol for sampling-based proofs of quantum supremacy thus remains open.

1 aGross, David1 aHangleiter, Dominik uhttps://arxiv.org/abs/2312.1015602434nas a2200205 4500008004100000245006200041210006200103260001500165300001100180490000800191520186900199100001502068700001902083700001902102700001602121700001702137700001702154700002002171856003702191 2018 eng d00aRecovering quantum gates from few average gate fidelities0 aRecovering quantum gates from few average gate fidelities c2018/03/01 a1705020 v1213 a

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.0057202431nas a2200169 4500008004100000245010800041210006900149260001500218300001100233490000700244520189900251100002402150700001702174700001602191700001702207856003702224 2012 eng d00aQuantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators 0 aQuantum Tomography via Compressed Sensing Error Bounds Sample Co c2012/09/27 a0950220 v143 a Intuitively, if a density operator has small rank, then it should be easier to estimate from experimental data, since in this case only a few eigenvectors need to be learned. We prove two complementary results that confirm this intuition. First, we show that a low-rank density matrix can be estimated using fewer copies of the state, i.e., the sample complexity of tomography decreases with the rank. Second, we show that unknown low-rank states can be reconstructed from an incomplete set of measurements, using techniques from compressed sensing and matrix completion. These techniques use simple Pauli measurements, and their output can be certified without making any assumptions about the unknown state. We give a new theoretical analysis of compressed tomography, based on the restricted isometry property (RIP) for low-rank matrices. Using these tools, we obtain near-optimal error bounds, for the realistic situation where the data contains noise due to finite statistics, and the density matrix is full-rank with decaying eigenvalues. We also obtain upper-bounds on the sample complexity of compressed tomography, and almost-matching lower bounds on the sample complexity of any procedure using adaptive sequences of Pauli measurements. Using numerical simulations, we compare the performance of two compressed sensing estimators with standard maximum-likelihood estimation (MLE). We find that, given comparable experimental resources, the compressed sensing estimators consistently produce higher-fidelity state reconstructions than MLE. In addition, the use of an incomplete set of measurements leads to faster classical processing with no loss of accuracy. Finally, we show how to certify the accuracy of a low rank estimate using direct fidelity estimation and we describe a method for compressed quantum process tomography that works for processes with small Kraus rank. 1 aFlammia, Steven, T.1 aGross, David1 aLiu, Yi-Kai1 aEisert, Jens uhttp://arxiv.org/abs/1205.2300v201526nas a2200157 4500008004100000245005100041210005000092260001500142520108300157100002201240700001901262700001701281700001601298700001701314856003701331 2011 eng d00aContinuous-variable quantum compressed sensing0 aContinuousvariable quantum compressed sensing c2011/11/033 a We significantly extend recently developed methods to faithfully reconstruct unknown quantum states that are approximately low-rank, using only a few measurement settings. Our new method is general enough to allow for measurements from a continuous family, and is also applicable to continuous-variable states. As a technical result, this work generalizes quantum compressed sensing to the situation where the measured observables are taken from a so-called tight frame (rather than an orthonormal basis) --- hence covering most realistic measurement scenarios. As an application, we discuss the reconstruction of quantum states of light from homodyne detection and other types of measurements, and we present simulations that show the advantage of the proposed compressed sensing technique over present methods. Finally, we introduce a method to construct a certificate which guarantees the success of the reconstruction with no assumption on the state, and we show how slightly more measurements give rise to "universal" state reconstruction that is highly robust to noise. 1 aOhliger, Matthias1 aNesme, Vincent1 aGross, David1 aLiu, Yi-Kai1 aEisert, Jens uhttp://arxiv.org/abs/1111.0853v301775nas a2200229 4500008004100000245003900041210003900080260001500119300000800134490000600142520116900148100001901317700002301336700002401359700001701383700002601400700001901426700002901445700001601474700001801490856003701508 2010 eng d00aEfficient quantum state tomography0 aEfficient quantum state tomography c2010/12/21 a1490 v13 a 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. 1 aCramer, Marcus1 aPlenio, Martin, B.1 aFlammia, Steven, T.1 aGross, David1 aBartlett, Stephen, D.1 aSomma, Rolando1 aLandon-Cardinal, Olivier1 aLiu, Yi-Kai1 aPoulin, David uhttp://arxiv.org/abs/1101.4366v101338nas a2200169 4500008004100000245005200041210005200093260001400145490000800159520087000167100001701037700001601054700002401070700002001094700001701114856003701131 2010 eng d00aQuantum state tomography via compressed sensing0 aQuantum state tomography via compressed sensing c2010/10/40 v1053 a We establish methods for quantum state tomography based on compressed sensing. These methods are specialized for quantum states that are fairly pure, and they offer a significant performance improvement on large quantum systems. In particular, they are able to reconstruct an unknown density matrix of dimension d and rank r using O(rd log^2 d) measurement settings, compared to standard methods that require d^2 settings. Our methods have several features that make them amenable to experimental implementation: they require only simple Pauli measurements, use fast convex optimization, are stable against noise, and can be applied to states that are only approximately low-rank. The acquired data can be used to certify that the state is indeed close to pure, so no a priori assumptions are needed. We present both theoretical bounds and numerical simulations. 1 aGross, David1 aLiu, Yi-Kai1 aFlammia, Steven, T.1 aBecker, Stephen1 aEisert, Jens uhttp://arxiv.org/abs/0909.3304v4