Classical simulation of slightly entangled quantum systems and quantum computations

Guifré Vidal

Published Jan 15, 2003• 0 citations

Abstract

We present a scheme to efficiently simulate, with a classical computer, the dynamics of multipartite quantum systems on which the amount of entanglement (or of correlations in the case of mixed-state dynamics) is conveniently restricted. This result implies that, in order for a quantum computation to achieve a significant speed-up with respect to classical computations, the amount of entanglement (correlations) in a quantum computer cannot be upper bounded, but must scale with the size of the computation. On a practical side, the proposed scheme may be used to simulate the dynamics of certain systems of interest in quantum physics, such as one-dimensional spin models.

Related papers

Efficient Classical Simulation of Slightly Entangled Quantum Computations

Guifré Vidal

We present a classical protocol to efficiently simulate any pure-state quantum computation that involves only a restricted amount of entanglement. More generally, we show how to classically simulate pure-state quantum computations on n qubits by using computational resources that grow linearly in n and exponentially in the amount of entanglement in the quantum computer. Our results imply that a necessary condition for an exponential computational speedup (with respect to classical computations) is that the amount of entanglement increases with the size n of the computation, and provide an explicit lower bound on the required growth.

arXiv:quant-ph/0301063Physical Review LettersOct 1, 20032,368 citations

Embedding Quantum Simulators for Quantum Computation of Entanglement

Roberto Di Candia, Bernabé Mejía, Hernán Castillo +3 more

We introduce the concept of embedding quantum simulators, a paradigm allowing the efficient quantum computation of a class of bipartite and multipartite entanglement monotones. It consists in the suitable encoding of a simulated quantum dynamics in the enlarged Hilbert space of an embedding quantum simulator. In this manner, entanglement monotones are conveniently mapped onto physical observables, overcoming the necessity of full tomography and reducing drastically the experimental requirements. Furthermore, this method is directly applicable to pure states and, assisted by classical algorithms, to the mixed-state case. Finally, we expect that the proposed embedding framework paves the way for a general theory of enhanced one-to-one quantum simulators.

arXiv:1306.0510Physical Review LettersDec 9, 201326 citations

Role of entanglement and correlations in mixed-state quantum computation

Animesh Datta, Guifré Vidal

In a quantum computation with pure states, the generation of large amounts of entanglement is known to be necessary for a speedup with respect to classical computations. However, examples of quantum computations with mixed states are known, such as the deterministic computation with one quantum qubit (DQC1) model [Knill and Laflamme, Phys. Rev. Lett. 81, 5672 (1998)], in which entanglement is at most marginally present, and yet a computational speedup is believed to occur. Correlations, and not entanglement, have been identified as a necessary ingredient for mixed-state quantum computation speedups. Here we show that correlations, as measured through the operator Schmidt rank, are indeed present in large amounts in the DQC1 circuit. This provides evidence for the preclusion of efficient classical simulation of DQC1 by means of a whole class of classical simulation algorithms, thereby reinforcing the conjecture that DQC1 leads to a genuine quantum computational speedup.

arXiv:quant-ph/0611157Physical Review AApr 11, 2007259 citations

Generalised state spaces and non-locality in the classical simulation of noisy quantum computers.

N. Ratanje, S. Virmani, John M. Anderson

We develop connections between generalised notions of entanglement and quantum computational devices where the measurements available are restricted, either because they are noisy and/or because by design they are only along Pauli directions. By considering restricted measurements one can (by considering the dual positive operators) construct single particle state spaces that are different to the usual quantum state space. This leads to a modified notion of entanglement that can be very different to the quantum version (for example, Bell states can become separable). We use this approach to develop alternative methods of classical simulation that have strong connections to the study of non-local correlations: we construct noisy quantum computers that admit operations outside the Clifford set and can generate some forms of multiparty quantum entanglement, but are otherwise classical in that they can be efficiently simulated classically and cannot generate non-local statistics. Although the approach provides new regimes of noisy quantum evolution that can be efficiently simulated classically, it does not appear to lead to significant reductions of existing upper bounds to fault tolerance thresholds for common noise models.

Jul 20, 20100 citations

On the role of entanglement in quantum-computational speed-up

Richard Jozsa, Noah Linden

For any quantum algorithm operating on pure states, we prove that the presence of multi‐partite entanglement, with a number of parties that increases unboundedly with input size, is necessary if the quantum algorithm is to offer an exponential speed‐up over classical computation. Furthermore, we prove that the algorithm can be efficiently simulated classically to within a prescribed tolerance η even if a suitably small amount of global entanglement is present. We explicitly identify the occurrence of increasing multi‐partite entanglement in Shor's algorithm. Our results do not apply to quantum algorithms operating on mixed states in general and we discuss the suggestion that an exponential computational speed‐up might be possible with mixed states in the total absence of entanglement. Finally, despite the essential role of entanglement for pure‐state algorithms, we argue that it is nevertheless misleading to view entanglement as a key resource for quantum‐computational power.

arXiv:quant-ph/0201143Proceedings of the Royal Society A Mathematical Physical and Engineering SciencesAug 8, 2003839 citations

Classical Simulation of Quantum Systems

Maarten Van den Nest, Frank Verstraete

The study of quantum computations that can be simulated efficiently classically is of interest for numerous reasons. On a fundamental level, such an investigation sheds light on the intrinsic computational power that is harnessed in quantum mechanics as compared to classical physics. More practically, understanding which quantum computations do not offer any speed-ups over classical computation provides insights in where (not) to look for novel quantum algorithmic primitives. On the other hand, classical simulation of many-body systems is a challenging task, as the dimension of the Hilbert space scales with the number of particles. Therefore, to understand the properties of the systems, suitable approximation methods need to be employed. The lectures will be divided into two parts. In the first part we discuss classical simulation of quantum computation from several perspectives. We review a number of well-known examples of classically simulatable quantum computations, such as the Gottesman-Knill theorem, matchgate simulation and tensor contraction methods. We further discuss simulation methods that are centred on classical sampling methods (‘weak simulation’), and illustrate how these techniques outperform methods that rely on the exact computation of measurement probabilities (‘strong simulation’). The second part focuses on "Entanglement and variational wavefunctions in quantum many body physics". We review the idea of entanglement in quantum many-body systems and how it helps us to understand the success of numerical renormalization group methods. In particular we will discuss a few variational wave-function based methods for simulating strongly correlated quantum systems, which include (1) matrix product states (2) multiscale entanglement renormalization ansatz (3) projected entangled pair states and (4) continuous matrix product states for quantum field theories.

Jan 1, 20160 citations