On estimating the entropy of shallow circuit outputs
- URL: http://arxiv.org/abs/2002.12814v2
- Date: Fri, 9 Aug 2024 14:41:42 GMT
- Title: On estimating the entropy of shallow circuit outputs
- Authors: Alexandru Gheorghiu, Matty J. Hoban,
- Abstract summary: 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.
- Score: 49.1574468325115
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. Here, we examine the hardness of this task for the case of probability distributions or quantum states produced by shallow circuits. Specifically, 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 (LWE) problem, and thus believed to be intractable even for efficient quantum computation. This illustrates that quantum circuits do not need to be complex to render the computation of entropy a difficult task. We also give complexity-theoretic evidence that this problem for log-depth circuits is not as hard as its counterpart with general polynomial-size circuits, seemingly occupying an intermediate hardness regime. Finally, we discuss potential future applications of our work for quantum gravity research by relating our results to the complexity of the bulk-to-boundary dictionary of AdS/CFT.
Related papers
- Fidelity-dissipation relations in quantum gates [0.0]
Quantum gates in practice are generally affected by dissipative environments, which can significantly reduce their fidelity.
In this study, we elucidate fundamental relations between the average fidelity of generic quantum gates and the dissipation that occurs during the computing processes.
Our results unveil the computational limitations imposed by thermodynamics, shedding light on the profound connection between thermodynamics and quantum computing.
arXiv Detail & Related papers (2023-11-27T12:31:52Z) - Quantum complexity phase transitions in monitored random circuits [0.29998889086656577]
We study the dynamics of the quantum state complexity in monitored random circuits.
We find that the evolution of the exact quantum state complexity undergoes a phase transition when changing the measurement rate.
arXiv Detail & Related papers (2023-05-24T18:00:11Z) - Quantum process tomography of continuous-variable gates using coherent
states [49.299443295581064]
We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit.
We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
arXiv Detail & Related papers (2023-03-02T18:08:08Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - Single-qubit gate teleportation provides a quantum advantage [0.0]
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.
arXiv Detail & Related papers (2022-09-28T15:11:39Z) - 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) - Gaussian initializations help deep variational quantum circuits escape
from the barren plateau [87.04438831673063]
Variational quantum circuits have been widely employed in quantum simulation and quantum machine learning in recent years.
However, quantum circuits with random structures have poor trainability due to the exponentially vanishing gradient with respect to the circuit depth and the qubit number.
This result leads to a general belief that deep quantum circuits will not be feasible for practical tasks.
arXiv Detail & Related papers (2022-03-17T15:06:40Z) - Quantum State Complexity in Computationally Tractable Quantum Circuits [0.0]
We discuss a special class of numerically tractable quantum circuits, known as quantum automaton circuits.
We show that automaton wave functions have high quantum state complexity.
We present evidence of a linear growth of design complexity in local quantum circuits.
arXiv Detail & Related papers (2020-09-11T16:25:11Z) - 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) - Pseudo-dimension of quantum circuits [0.0]
We prove pseudo-dimension bounds on the output probability of quantum circuits.
We show that circuits of known size and depth are PAC-learnable.
arXiv Detail & Related papers (2020-02-04T19:00:13Z)
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.