



02367nas a2200181   4500008004100000022001400041245004800055210004800103260001400151300000900165490000600174520189200180100001802072700001802090700001802108700002002126856003902146       2024                        eng d  a2521-327X00aFast simulation of planar Clifford circuits0 aFast simulation of planar Clifford circuits  c2/12/2024  a12510 v83 a<p>A general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally exponential in the treewidth of the underlying graph. Separately, Gottesman and Knill showed that if all gates are restricted to be Clifford, then there is a polynomial time simulation. We combine these two ideas and show that treewidth and planarity can be exploited to improve Clifford circuit simulation. Our main result is a classical algorithm with runtime scaling asymptotically as nω/2&lt;n1.19 which samples from the output distribution obtained by measuring all n qubits of a planar graph state in given Pauli bases. Here ω is the matrix multiplication exponent. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. Our work improves known classical algorithms with cubic runtime. A key ingredient is a mapping which, given a tree decomposition of some graph G, produces a Clifford circuit with a structure that mirrors the tree decomposition and which emulates measurement of the corresponding graph state. We provide a classical simulation of this circuit with the runtime stated above for planar graphs and otherwise ntω&minus;1 where t is the width of the tree decomposition. Our algorithm incorporates two subroutines which may be of independent interest. The first is a matrix-multiplication-time version of the Gottesman-Knill simulation of multi-qubit measurement on stabilizer states. The second is a new classical algorithm for solving symmetric linear systems over F2 in a planar geometry, extending previous works which only applied to non-singular linear systems in the analogous setting.</p>1 aGosset, David1 aGrier, Daniel1 aKerzner, Alex1 aSchaeffer, Luke  uhttps://arxiv.org/abs/2009.03218v301949nas a2200193   4500008004100000245005300041210005200094260001500146520133800161653004301499653002701542653003101569653002901600653003101629100001801660700002001678700002001698856003701718       2022                        eng d00aSample-optimal classical shadows for pure states0 aSampleoptimal classical shadows for pure states  c11/21/20223 a<p>We consider the classical shadows task for pure states in the setting of both joint and independent measurements. The task is to measure few copies of an unknown pure state ρ in order to learn a classical description which suffices to later estimate expectation values of observables. Specifically, the goal is to approximate Tr(Oρ) for any Hermitian observable O to within additive error ϵ provided Tr(O2)&le;B and ∥O∥=1. Our main result applies to the joint measurement setting, where we show Θ~(B&minus;&minus;&radic;ϵ&minus;1+ϵ&minus;2) samples of ρ are necessary and sufficient to succeed with high probability. The upper bound is a quadratic improvement on the previous best sample complexity known for this problem. For the lower bound, we see that the bottleneck is not how fast we can learn the state but rather how much any classical description of ρ can be compressed for observable estimation. In the independent measurement setting, we show that O(Bd&minus;&minus;&minus;&radic;ϵ&minus;1+ϵ&minus;2) samples suffice. Notably, this implies that the random Clifford measurements algorithm of Huang, Kueng, and Preskill, which is sample-optimal for mixed states, is not optimal for pure states. Interestingly, our result also uses the same random Clifford measurements but employs a different estimator.</p>10aFOS: Computer and information sciences10aFOS: Physical sciences10aInformation Theory (cs.IT)10aMachine Learning (cs.LG)10aQuantum Physics (quant-ph)1 aGrier, Daniel1 aPashayan, Hakop1 aSchaeffer, Luke  uhttps://arxiv.org/abs/2211.11810