Scott Aaronson David Chen

Documents

kiele
  • 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? * * * * * *
Please download to view
6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
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