GENERALIZED STABILIZERS Ted Yoder Quantum/Classical Boundary • How do we study the power of quantum computers compared to classical ones? • Compelling problems • Shor’s factoring • Grover’s search • Oracle separations • Quantum resources • Entanglement • Discord • Classical simulation Schrödinger C ~ What is the probability of measuring the first qubit to be 0? Heisenberg C ~ What set of operators do we choose? ~ Require Examples ~ By analogy to the first, we can write any stabilizer as ~ And the state it stabilizes as Destabilizer, Tableaus, Stabilizer Bases ~ We have ~ Collect all . What is in a group, ~ A tableau defines a stabilizer basis, ? Generalized Stabilizer ~ Take any quantum state and write it in a stabilizer basis, ~ Then all the information about ~ Any state can be represented ~ Any operation can be simulated - Unitary gates - Measurements - Channels can be written as the pair C1 C2 The Interaction Picture for complex numbers φi j and Pauli operat ors B i 2 Gn . We also deﬁne ⇤( complexity. Not e t hat any quant um operat ion can be expressed uniquely (up a Pauli channel. Update Efficiencies T heor em 13. Suppose we have a generalized stabilizer on n-qubits ⌧= (χ, ~ For update efficiencies updates can be done with the following efficiency: ministic for quantum operations, • Cli ↵ ord gates: O(n) time • Pauli measurements: O ⇤(χ) n + n 2 time ⇣ ⌘ p • Pauli channels E: O ⇤(χ) ⇤(E) n + ⇤(E)n 2 time Note that ⇤( ⌧) = 11997 if and only if we have a stabilizer state. I n that case, the ~ Gottesman-Knill ment is recovered. On stabilizer states, we have the update efficiencies Proof. We prove each part in t urn. - Clifford gates: • Say we have Cli↵ord circuit C. T hen, - Pauli measurements: 0 X C ⌧C = C @ χ i j † ~ Note the correspondence when . X 1 i⇢ S j A C† ij † † Conclusion • New (universal) state representation • Combination of stabilizer and density matrix representation • Features dynamic basis that allows efficient simulation of Clifford gates • The interaction picture for quantum circuit simulation • Leads to a sufficient condition on states easily simulatable through any stabilizer circuit R efer ences References        P. W . Shor, SIA M J. Comput ., 26(5), 1484 (1994). R. Josza and N. Linden, Proc. R. Soc. London A 459, 2011 (2003). M . Nielson and I. Chuang, Quantum Computation and Quantum I nfor mation, Cambridge University Press, 2000. G. Passant e, et. al., Phys. Rev. A 84, 044302 (2011). A . M ari, J. Eisert , Phys. Rev. Let t . 109, 230503 (2012). D. Got t esman, CalTech Ph.D. t hesis, arXiv:quant -ph/ 9705052 (1997). D. Got t esman, Proceedings of t he X X I I Int ernat ional Colloquium on Group T heoret ical M et hods in Physics, edit ed by S.P. Corney et al. (Int ernat ional Press, Cambridge, M A , 1999), p. 32.  M . Van den Nest , Quant . Inf. Comp. 10, 0258 (2010).  S. A aronson and D. Got t esman, Phys. Rev. A 70, 052328 (2004).  S. A nders and H. Briegel, P, Phys. Rev. A 73, 022334 (2006). Stabilizer Circuits ~ Recall that stabilizer circuits are those made from and a final measurement of the operator . ~ What set of states can be efficiently simulated by a classical computer through any stabilizer circuit? ~ Clifford gates can be simulated in time Measurements ~ We’ll measure the complexity of ~ The complexity of a state ~ Simulating measurement of by can be defined as takes time ~ What set of states can be efficiently simulated by a classical computer through any stabilizer circuit? is sufficient. Channels ~ Define a Pauli channel as, for Pauli operators ~ Define as a measure of its complexity.