Related papers: Stabilizer extent is not multiplicative

Stabilizer extent is not multiplicative

URL: http://arxiv.org/abs/2007.04363v3
Date: Fri, 19 Feb 2021 08:33:22 GMT
Title: Stabilizer extent is not multiplicative
Authors: Arne Heimendahl, Felipe Montealegre-Mora, Frank Vallentin and David Gross
Abstract summary: Gottesman-Knill theorem states that a Clifford circuit acting on stabilizer states can be simulated efficiently on a classical computer. An important open problem is to decide whether the extent is multiplicative under tensor products.
Score: 1.491109220586182
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: The Gottesman-Knill theorem states that a Clifford circuit acting on stabilizer states can be simulated efficiently on a classical computer. Recently, this result has been generalized to cover inputs that are close to a coherent superposition of logarithmically many stabilizer states. The runtime of the classical simulation is governed by the stabilizer extent, which roughly measures how many stabilizer states are needed to approximate the state. An important open problem is to decide whether the extent is multiplicative under tensor products. An affirmative answer would yield an efficient algorithm for computing the extent of product inputs, while a negative result implies the existence of more efficient classical algorithms for simulating largescale quantum circuits. Here, we answer this question in the negative. Our result follows from very general properties of the set of stabilizer states, such as having a size that scales subexponentially in the dimension, and can thus be readily adapted to similar constructions for other resource theories.

Related papers

Learning State Preparation Circuits for Quantum Phases of Matter [0.294944680995069]
We introduce a flexible and efficient framework for obtaining a state preparation circuit for a large class of many-body ground states. We use a variant of the quantum Markov chain condition that remains robust against constant-depth circuits.
arXiv Detail & Related papers (2024-10-31T01:10:46Z)
Faster Computation of Stabilizer Extent [3.8061090528695543]
We propose fast numerical algorithms to compute the stabilizer extent. Our algorithm can compute the stabilizer fidelity and the stabilizer extent for random pure states up to $n=9$ qubits.
arXiv Detail & Related papers (2024-06-24T14:28:15Z)
Stabilizer ground states for simulating quantum many-body physics: theory, algorithms, and applications [0.5735035463793009]
We apply stabilizer states to tackle quantum many-body ground state problems. We develop an exact and linear-scaled algorithm to obtain stabilizer ground states of 1D local Hamiltonians.
arXiv Detail & Related papers (2024-03-13T11:54:25Z)
Bases for optimising stabiliser decompositions of quantum states [14.947570152519281]
We introduce and study the vector space of linear dependencies of $n$-qubit stabiliser states. We construct elegant bases of linear dependencies of constant size three. We use them to explicitly compute the stabiliser extent of states of more qubits than is feasible with existing techniques.
arXiv Detail & Related papers (2023-11-29T06:30:05Z)
The vacuum provides quantum advantage to otherwise simulatable architectures [49.1574468325115]
We consider a computational model composed of ideal Gottesman-Kitaev-Preskill stabilizer states. We provide an algorithm to calculate the probability density function of the measurement outcomes.
arXiv Detail & Related papers (2022-05-19T18:03:17Z)
Efficient simulation of Gottesman-Kitaev-Preskill states with Gaussian circuits [68.8204255655161]
We study the classical simulatability of Gottesman-Kitaev-Preskill (GKP) states in combination with arbitrary displacements, a large set of symplectic operations and homodyne measurements. For these types of circuits, neither continuous-variable theorems based on the non-negativity of quasi-probability distributions nor discrete-variable theorems can be employed to assess the simulatability.
arXiv Detail & Related papers (2022-03-21T17:57:02Z)
Improved Graph Formalism for Quantum Circuit Simulation [77.34726150561087]
We show how to efficiently simplify stabilizer states to canonical form. We characterize all linearly dependent triplets, revealing symmetries in the inner products. Using our novel controlled-Pauli $Z$ algorithm, we improve runtime for inner product computation from $O(n3)$ to $O(nd2)$ where $d$ is the maximum degree of the graph.
arXiv Detail & Related papers (2021-09-20T05:56:25Z)
Efficient simulatability of continuous-variable circuits with large Wigner negativity [62.997667081978825]
Wigner negativity is known to be a necessary resource for computational advantage in several quantum-computing architectures. We identify vast families of circuits that display large, possibly unbounded, Wigner negativity, and yet are classically efficiently simulatable. We derive our results by establishing a link between the simulatability of high-dimensional discrete-variable quantum circuits and bosonic codes.
arXiv Detail & Related papers (2020-05-25T11:03:42Z)
Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
arXiv Detail & Related papers (2019-12-31T19:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.