Efficient classical simulation of slightly entangled quantum computations

Efficient classical simulation of slightly entangled quantum computations

February 1, 2008 | Guifré Vidal
The paper presents a scheme for efficiently simulating the dynamics of multipartite quantum systems using a classical computer, particularly focusing on systems with restricted entanglement. The authors show that the evolution of a pure state of \( n \) qubits can be simulated with computational resources that grow linearly in \( n \) and exponentially in the entanglement. They establish that a pure-state quantum computation can only achieve an exponential speed-up over classical computations if the entanglement increases with the size \( n \) of the computation. The key to their simulation protocol is a local decomposition of the state into tensors and vectors, which allows for efficient updates of the state under single-qubit and two-qubit gates. The results provide a clear connection between the amount of entanglement and the computational cost of simulating quantum systems, suggesting a new approach to studying multipartite entanglement based on the complexity of describing and simulating quantum systems. The authors also propose a measure of entanglement, \( E_{\chi} \), which quantifies the difficulty of expressing a state in terms of local states and provides an upper bound on the computational speed-up achievable by quantum computations.The paper presents a scheme for efficiently simulating the dynamics of multipartite quantum systems using a classical computer, particularly focusing on systems with restricted entanglement. The authors show that the evolution of a pure state of \( n \) qubits can be simulated with computational resources that grow linearly in \( n \) and exponentially in the entanglement. They establish that a pure-state quantum computation can only achieve an exponential speed-up over classical computations if the entanglement increases with the size \( n \) of the computation. The key to their simulation protocol is a local decomposition of the state into tensors and vectors, which allows for efficient updates of the state under single-qubit and two-qubit gates. The results provide a clear connection between the amount of entanglement and the computational cost of simulating quantum systems, suggesting a new approach to studying multipartite entanglement based on the complexity of describing and simulating quantum systems. The authors also propose a measure of entanglement, \( E_{\chi} \), which quantifies the difficulty of expressing a state in terms of local states and provides an upper bound on the computational speed-up achievable by quantum computations.
Reach us at info@study.space
[slides] Efficient classical simulation of slightly entangled quantum computations. | StudySpace