Scott Aaronson David Chen

Documents

kiele
of 6
Description
Generating Random Stabilizer States in Matrix Multiplication Time: A Theorem in Search of an Application. Scott Aaronson David Chen. Stabilizer States. n-qubit quantum states that can be produced from |0…0  by applying CNOT, Hadamard, and gates only. - PowerPoint PPT Presentation
Text
  • Generating Random Stabilizer States in Matrix Multiplication Time: A Theorem in Search of an Application Scott Aaronson David Chen
  • Stabilizer States n-qubit quantum states that can be produced from |0…0 by applying CNOT, Hadamard, and gates only By the celebrated Gottesman-Knill Theorem, such states are classically describable using 2n2+n bits: The X and Z matrices must satisfy: (1) XZT is symmetric (2) (XZ) (considered as an n2n matrix) has rank n
  • How Would You Generate A classical description of a Uniformly-Random Stabilizer State? Our original motivation: Generating random stabilizer measurements, in order to learn an unknown stabilizer state Obvious approach: Build up the stabilizer group, by repeatedly adding a random generator independent of all the previous generators Takes O(n4) time—or rather, O(n+1), where 2.376 is the exponent of matrix multiplication More clever approach: O(n3) time
  • Our algorithm is a consequence of a new “Atomic Structure Theorem” for stabilizer states… Theorem: Every stabilizer state can be transformed, using CNOT and Pauli gates only, into a tensor product of the following four “stabilizer atoms”: (And even the fourth “atom”—which arises because of a peculiarity of GF(2)—can be decomposed into the first three atoms, using the second or third atoms as a catalyst)
  • With the Atomic Structure Theorem in hand, we can easily generate a random stabilizer state as follows: Generate a random tensor product | of stabilizer atoms (and we’ve explicitly calculated the probabilities for each of the poly(n) possible tensor products) Generate a random circuit C of CNOT gates, by repeatedly choosing an nn matrix over GF(2) until you find one that’s invertible Apply the circuit C to | (using [A|B][AC|BC-T]) Choose a random sign (+ or -) for each stabilizer The running time is dominated by steps 2 and 3, both of which take O(n) time
  • Open Problems Find the killer app for fast generation of random stabilizer states! Find another application for our Atomic Structure Theorem! Is it possible to generate a random invertible matrix over GF(2) (i.e., a random CNOT circuit) in less than n time? * * * * * *
Comments
Top