Quantum Simulation 9 December 2008 Scott Crawford Justin Bonnar Quantum Simulation Studies the efficient classical simulation of quantum circuits Understanding what is and is not efficiently simulable has implications to the usefulness of quantum circuits Known to be closely related to entanglement In general simulation is exponential but some classes of circuits may be done efficiently Three Results in Quantum Simulation Any poly sized and generally poly depth circuit on n qubits can be efficiently simulated provided the maximum number of gates touching or spanning any wire is bounded by O log n Jozsa 2006 The evolution of a quantum state can be simulated with resources linear in the size of the state and exponential in the the entanglement If the maximum Schmidt rank of the system is poly in the size of the state then the simulation is efficient Vidal 2003 Multi scale Entanglement Renormalization Ansatz MERA is a way of describing a quantum circuit as a lattice with special properties that make it classically simulable Vidal 2006 Quantum Circuit Reduction Reduce quantum circuits to having only 1 and 2 qubit gates Formulate as parallel wires and reduce it by merging all 1qubit gates into neighboring gates and merging all consecutive 2 qubit gates that can be performed sequentially without an interposing gate Contracting Linear Networks For each wire let Di be the number of 2 qubit gates that touch or cross it Then D maxi Di Contracting Linear Networks efficient computation We measure with the projector matrix The output is prob k can be easily computed from the full transformation This sum takes time O 2 D so doing so for all wires takes time O n 2 D which is polynomial in n if D O log n Schmidt Decomposition As a consequence from linear algebra related to SVD we can decompose any quantum state into two subspaces where The number of non zero Schmidt coefficients is the Schmidt rank of the decomposition The state is separable iff it has a Schmidt rank of one If more than one coefficient is non zero the state is entangled If they are all non zero it is maximally entangled Thus the maximum Schmidt rank makes a good measure of the state s entanglement Slightly entangled states We say a pure state quantum evolution is slightly entangled if at all times t the state of the system is slightly entangled that is if is small A sequence of evolutions with an increasingly large number of n qubits is slightly entangled if is upper bounded by poly n Vidal 2003 By restricting ourselves to circuits with limited entanglement we can prove them to be efficiently simulable Conversely we can place a lower bound on the entanglement in useful quantum circuits Local state decomposition In general representing requires exponential state If it is only slightly entangled we can inductively use Schmidt decomposition to get Which is specified in terms of parameters This representation requires we pick an ordering of qubits but once we ve done so we can keep updates local That is to apply a gate to qubits l and l 1 we need only update Mind the gap Problem Our decomposed representation allows for efficient local update but gates can span multiple wires Solution decompose a gate spanning r wires into O r gates spanning two adjacent wires Efficient updates Single qubit gates only transform and can be computed in O time Proof sketch consider that a unitary operation U doesn t affect the Schmidt decomposition above or below l By a similar but more involved argument it is possible to show that applying a gate to l and l 1 can be done in O time and O space Thus provided is constrained to grow slowly the circuit can be efficiently simulated Note global entanglement appears key to computational speed up Multi scale Entanglement Renormalization Ansatz MERA A MERA efficiently encodes a lattice of quantum states of spatial dimension D The MERA for is a tensor network M that corresponds to quantum circuit C The dimension of the q states in is X MERAs Causal Cone C s includes the gates and wires that influence p s Ctheta s the number of wires in a time slice of C s is bounded by 3 D 1 4 MERAs Computing p s and p s1s2 The density matrix for each slice of Ctheta s and Ctheta s1s2 can be computed from the density matrix for the previous slice in time polynomial to X Since there are logN slices p s and p s1s2 generally p s1 sn can be computed in time O X logN Conclusions Quantum simulation is necessarily hard Understanding what can be efficiently simulated places lower bounds on worthwhile quantum circuits Entanglement appears to be the limiting factor in simulation Better models constraining entanglement enable efficient algorithms the mathematical models can be thought of as efficient data structures Questions