arXiv:1201.0613

Exploiting non-quantum entanglement to widen applicability of limited-entanglement classical simulations of quantum systems

N. Ratanje, S. Virmani

Published Jan 3, 2012• 3 citations

Abstract

It is known that if the quantum gates in a proposed quantum computer are so noisy that they are incapable of generating entanglement, then the device can be efficiently simulated classically. If the measurements and single particle operations are restricted, then the same statement can be true for generalised non-quantum notions of entanglement. Here we show that this can improve the applicability of limited-entanglement simulation algorithms. In particular, we show that by using a non-quantum notion of separability a classical simulation algorithm of Harrow & Nielsen can efficiently simulate magic state quantum computers with noisy CNOTs (but otherwise ideal) for joint depolarising strengths of 272/489 ~ 56%, in comparison to noise levels of 2/3 ~ 66% required if the algorithm uses quantum notions of separability. This suggests that quantum entanglement may not be the most appropriate notion of entanglement to use when discussing the power of stabilizer based quantum computers.

DOI: 10.48550/arxiv.1201.0613

Related papers

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

Quantum Simulation of Non-Classical Correlations: A Computationally Efficient Strategy

Jincheng Zhang

Quantum simulation offers unprecedented capabilities for modeling complex quantum systems, particularly those exhibiting non-classical correlations. However, the inherent complexity of these correlations often necessitates substantial computational resources, hindering practical applications. This paper explores a novel computational strategy for quantum simulation, leveraging the unique properties of non-classical correlations to significantly enhance efficiency and accuracy. We propose a quantum-based approach that utilizes quantum entanglement to reduce computational cost and improve the fidelity of simulations. This strategy focuses on minimizing the number of necessary quantum operations while maintaining the desired level of accuracy. The core mechanism centers on employing a specific entanglement-based algorithm to manage and exploit these correlations, ultimately providing a more efficient and precise method for simulating these systems. This research aims to address the limitations of traditional quantum simulation techniques, particularly in the context of challenging non-classical correlations.

Aug 29, 20260 citations

The power of restricted quantum computational models

Mithuna Yoganathan

Restricted models of quantum computation are ones that have less power than a universal quantum computer. We studied the consequences of removing particular properties from a universal quantum computer to discover whether those resources were important.In the first part of the thesis we studied universal quantum computers which are implemented using Clifford gates, adaptive measurements, and magic states. The Gottesman–Knill theorem shows that circuits in this form which do not use magic states can be simulated by a classical computer. We extended this result to show that all circuits in this form can be partially simulated; the same computation can be implemented using a smaller quantum computer with the assistance of some polynomial time classical computation. We also identified a subclass of these computations that can be shown to not be entirely classically simulated by any method, given certain complexity theoretic assumptions are true.In the next part of the thesis we examine the role of entanglement in noisy quantum computations. Entanglement is necessary for noiseless quantum computers to have any quantum advantage, but it is not known whether the same is true for mixed state quantum computers. We show that entanglement, unexpectedly, does play a crucial role in the most well known mixed state computer: the one clean qubit model.Finally, we investigate how closely classical simulation is related to another idea of classicality.This notion captures how easily the final state of a computation can be learnt, given samples of measurements from it. We find an extra condition under which a circuit that is classically simulable is also efficiently learnable.

Jan 5, 20210 citations

Classical simulability, entanglement breaking, and quantum computation thresholds (Invited Paper)

S. Virmani, Susana F. Huelga, Martin Bodo Plenio

We investigate the amount of noise required to turn a universal quantum gate set into one that can be efficiently modelled classically. This question is useful for providing upper bounds on fault tolerant thresholds, and for understanding the nature of the quantum/classical computational transition. We refine some previously known upper bounds using two different strategies. The first one involves the introduction of bi-entangling operations, a class of classically simulatable machines that can generate at most bipartite entanglement. Using this class we show that it is possible to sharpen previously obtained upper bounds in certain cases. As an example, we show that under depolarizing noise on the controlled-not gate, the previously known upper bound of 74% can be sharpened to around 67%. Another interesting consequence is that measurement based schemes cannot work using only 2-qubit non-degenerate projections. In the second strand of the work we utilize the Gottesman-Knill theorem on the classically efficient simulation of Clifford group operations. The bounds attained using this approach for the pi/8-gate can be as low as 15% for general single gate noise, and 30% for dephasing noise.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIEMay 23, 20050 citations

Exact efficient simulation of noisy logical magic states using Clifford stabilizers

Yugo Takada, Stephen D. Bartlett, Dominic J. Williamson

The preparation of high-fidelity logical magic states is a crucial subroutine for universal fault-tolerant quantum computation (FTQC). Predicting the performance of FTQC and developing improved protocols rely on numerical methods to classically simulate logical magic state preparation in the presence of noise. Clifford logic on Pauli-stabilizer codes with circuit-level Pauli errors can be efficiently simulated using Pauli-stabilizer formalism, but the non-Clifford operations required to prepare logical magic states render generic simulation inefficient. We introduce Clifford-stabilizer simulation, an exact and efficient algorithm based on updating a Clifford-stabilizer group to simulate noisy preparation protocols for a broad class of logical magic states used to implement non-Clifford gates in the third level of the Clifford hierarchy under circuit-level Pauli errors. Clifford-stabilizer simulation applies to a range of operations that commonly appear in preparation protocols for such logical magic states, including Pauli-stabilizer measurements, logical Clifford measurements, and transversal non-Clifford gates. Our algorithm for Clifford-stabilizer simulation maps a non-Clifford circuit with sampled circuit-level Pauli errors to a Clifford circuit that exactly reproduces its measurement outcome distribution, achieving time and space complexities polynomial in relevant protocol parameters. We perform exact simulation of magic state cultivation up to fault distance 7 by Clifford-stabilizer simulation. Our method provides a route to perform exact benchmarking of large-scale logical magic state preparation protocols required for useful FTQC.

quant-pharXiv:2609.16929Sep 16, 20260 citations

Generalized state spaces and nonlocality in fault-tolerant quantum-computing schemes

N. Ratanje, S. Virmani

We develop connections between generalized 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 nonlocal 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 nonlocal 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.

arXiv:1007.3455Physical Review AMar 14, 201110 citations