Related papers: Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums

Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums

URL: http://arxiv.org/abs/2408.02778v1
Date: Mon, 5 Aug 2024 18:56:20 GMT
Title: Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums
Authors: Matthew Amy, Lucas Shigeru Stinchcombe,
Abstract summary: We show that a family of quantum circuits can in fact be simulated in time via symbolic path integrals. We hence resolve an open conjecture about the efficient simulability of this class of circuits-time.
Score: 0.9208007322096532
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Implementations of Roetteler's shifted bent function algorithm have in recent years been used to test and benchmark both classical simulation algorithms and quantum hardware. These circuits have many favorable properties, including a tunable amount of non-Clifford resources and a deterministic output, and moreover do not belong to any class of quantum circuits which is known to be efficiently simulable. We show that this family of circuits can in fact be simulated in polynomial time via symbolic path integrals. We do so by endowing symbolic sums with a confluent rewriting system and show that this rewriting system suffices to reduce the circuit's path integral to the hidden shift in polynomial-time. We hence resolve an open conjecture about the efficient simulability of this class of circuits.

Related papers

Polynomial-Time Classical Simulation of Noisy Circuits with Naturally Fault-Tolerant Gates [0.22499166814992438]
We show that there is no quantum advantage at large depths with realistically noisy Clifford circuits. The key insight behind the algorithm is that interspersed noise causes a decay of long-range entanglement. To prove our results, we merge techniques from percolation theory with tools from Pauli path analysis.
arXiv Detail & Related papers (2024-11-04T19:11:58Z)
A Fourier analysis framework for approximate classical simulations of quantum circuits [0.0]
I present a framework that applies harmonic analysis of groups to circuits with a structure encoded by group parameters. I also discuss generalisations to homogeneous spaces, qudit systems and a way to analyse random circuits via matrix coefficients of irreducible representations.
arXiv Detail & Related papers (2024-10-17T17:59:34Z)
Fast classical simulation of quantum circuits via parametric rewriting in the ZX-calculus [0.0]
We show that it is possible to perform the final stage of classical simulation quickly utilising a high degree of GPU parallelism. We demonstrate speedups upwards of 100x for certain classical simulation tasks vs. the non-parametric approach.
arXiv Detail & Related papers (2024-03-11T14:44:59Z)
Unified framework for efficiently computable quantum circuits [0.0]
Quantum circuits consisting of Clifford and matchgates are two classes of circuits that are known to be efficiently simulatable on a classical computer. We introduce a unified framework that shows in a transparent way the special structure that allows these circuits can be efficiently simulatable.
arXiv Detail & Related papers (2024-01-16T08:04:28Z)
Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
arXiv Detail & Related papers (2023-10-05T07:10:40Z)
Tensor Networks or Decision Diagrams? Guidelines for Classical Quantum Circuit Simulation [65.93830818469833]
tensor networks and decision diagrams have independently been developed with differing perspectives, terminologies, and backgrounds in mind. We consider how these techniques approach classical quantum circuit simulation, and examine their (dis)similarities with regard to their most applicable abstraction level. We provide guidelines for when to better use tensor networks and when to better use decision diagrams in classical quantum circuit simulation.
arXiv Detail & Related papers (2023-02-13T19:00:00Z)
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)
An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
arXiv Detail & Related papers (2021-08-06T19:38:03Z)
Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
We introduce a quantum circuit mapping, QXX, and its machine learning version, QXX-MLP. The latter infers automatically the optimal QXX parameter values such that the layed out circuit has a reduced depth. We present empiric evidence for the feasibility of learning the layout method using approximation.
arXiv Detail & Related papers (2020-07-29T05:26:19Z)
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.