Single-qubit gate teleportation provides a quantum advantage
- URL: http://arxiv.org/abs/2209.14158v2
- Date: Sun, 28 May 2023 23:03:31 GMT
- Title: Single-qubit gate teleportation provides a quantum advantage
- Authors: Libor Caha, Xavier Coiteux-Roy, Robert Koenig
- Abstract summary: Gate-teleportation circuits are arguably among the most basic examples of computations believed to provide a quantum computational advantage.
We show that even for single-qubit Clifford-gate-teleportation circuits this simulation problem cannot be solved by constant-depth classical circuits with bounded fan-in gates.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Gate-teleportation circuits are arguably among the most basic examples of
computations believed to provide a quantum computational advantage: In seminal
work [Quantum Inf. Comput., 4(2):134--145], Terhal and DiVincenzo have shown
that these circuits elude simulation by efficient classical algorithms under
plausible complexity-theoretic assumptions. Here we consider possibilistic
simulation [Phys. Rev. A 106, 062430 (2022)], a particularly weak form of this
task where the goal is to output any string appearing with non-zero probability
in the output distribution of the circuit. We show that even for single-qubit
Clifford-gate-teleportation circuits this simulation problem cannot be solved
by constant-depth classical circuits with bounded fan-in gates. Our results are
unconditional and are obtained by a reduction to the problem of computing the
parity, a well-studied problem in classical circuit complexity.
Related papers
- Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth [0.5188841610098435]
We show that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, the output distribution can be efficiently sampled by a classical computer.
We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit.
arXiv Detail & Related papers (2024-03-21T17:55:26Z) - Simulating Quantum Circuits by Model Counting [0.0]
We show for the first time that a strong simulation of universal quantum circuits can be efficiently tackled through weighted model counting.
Our work paves the way to apply the existing array of powerful classical reasoning tools to realize efficient quantum circuit compilation.
arXiv Detail & Related papers (2024-03-11T22:40:15Z) - 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) - A single $T$-gate makes distribution learning hard [56.045224655472865]
This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits.
We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
arXiv Detail & Related papers (2022-07-07T08:04:15Z) - Quantum circuit debugging and sensitivity analysis via local inversions [62.997667081978825]
We present a technique that pinpoints the sections of a quantum circuit that affect the circuit output the most.
We demonstrate the practicality and efficacy of the proposed technique by applying it to example algorithmic circuits implemented on IBM quantum machines.
arXiv Detail & Related papers (2022-04-12T19:39:31Z) - Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task.
Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate.
The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
arXiv Detail & Related papers (2021-06-06T13:15: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) - Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling.
We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
arXiv Detail & Related papers (2020-05-05T20:11:53Z) - On estimating the entropy of shallow circuit outputs [49.1574468325115]
Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing.
We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
arXiv Detail & Related papers (2020-02-27T15:32:08Z) - 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.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.