Estimating the entropy of shallow circuit outputs is hard
- URL: http://arxiv.org/abs/2002.12814v1
- Date: Thu, 27 Feb 2020 15:32:08 GMT
- Title: Estimating the entropy of shallow circuit outputs is hard
- Authors: Alexandru Gheorghiu, Matty J. Hoban
- Abstract summary: Decision problem version of estimating Shannon entropy is the Entropy Difference (ED)
analogous problem with quantum circuits (QED)
We show that relative to an oracle, these problems cannot be as hard as their counterparts with exponentially larger circuits.
- Score: 77.34726150561087
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The decision problem version of estimating the Shannon entropy is the Entropy
Difference problem (ED): given descriptions of two circuits, determine which
circuit produces more entropy in its output when acting on a uniformly random
input. The analogous problem with quantum circuits (QED) is to determine which
circuit produces the state with greater von Neumann entropy, when acting on a
fixed input state and after tracing out part of the output. Based on plausible
complexity-theoretic assumptions, both of these problems are believed to be
intractable for polynomial-time quantum computation. In this paper, we
investigate the hardness of these problems in the case where the input circuits
have logarithmic and constant depth, respectively. We show that, relative to an
oracle, these problems cannot be as hard as their counterparts with
polynomial-size circuits. Furthermore, we show that if a certain type of
reduction from QED to the log-depth version exists, it implies that any
polynomial-time quantum computation can be performed in log depth. While this
suggests that having shallow circuits makes entropy estimation easier, we give
indication that the problem remains intractable for polynomial-time quantum
computation by proving a reduction from Learning-With-Errors (LWE) to
constant-depth ED. We then consider a potential application of our results to
quantum gravity research. First, we introduce a Hamiltonian version of QED
where one is given two local Hamiltonians and asked to estimate the
entanglement entropy difference in their ground states. We show that this
problem is at least as hard as the circuit version and then discuss a potential
experiment that would make use of the AdS/CFT correspondence to solve LWE
efficiently. We conjecture that unless the AdS/CFT bulk to boundary map is
exponentially complex, this experiment would violate the intractability
assumption of LWE.
Related papers
- Dense outputs from quantum simulations [5.295277584890625]
The quantum dense output problem is the process of evaluating time-accumulated observables from time-dependent quantum dynamics.
This problem arises frequently in applications such as quantum control and spectroscopic computation.
We present a range of algorithms designed to operate on both early and fully fault-tolerant quantum platforms.
arXiv Detail & Related papers (2023-07-26T18:16:51Z) - Instantaneous nonlocal quantum computation and circuit depth reduction [7.148511452018054]
Two-party quantum computation is a computation process with bipartite input and output, in which there are initial shared entanglement.
In the first part, we show that a particular simplified subprocedure, known as a garden-hose gadget, cannot significantly reduce the entanglement cost.
In the second part, we show that any unitary circuit consisting of layers of Clifford gates and T gates can be implemented using a circuit with measurements of depth proportional to the T-depth of the original circuit.
arXiv Detail & Related papers (2023-06-15T17:57:50Z) - Hamiltonian variational ansatz without barren plateaus [0.0]
Variational quantum algorithms are one of the most promising applications of a near-term quantum computer.
Despite their huge potential, the utility of variational quantum algorithms beyond tens of qubits is still questioned.
arXiv Detail & Related papers (2023-02-16T19:01:26Z) - 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) - Circuit Complexity in an interacting quenched Quantum Field Theory [0.0]
We explore the effects of a quantum quench on the circuit complexity for a quenched quantum field theory having weakly coupled quartic interaction.
We show the analytical computation of circuit complexity for the quenched and interacting field theory.
arXiv Detail & Related papers (2022-09-07T18:00:03Z) - 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) - Numerical Simulations of Noisy Quantum Circuits for Computational
Chemistry [51.827942608832025]
Near-term quantum computers can calculate the ground-state properties of small molecules.
We show how the structure of the computational ansatz as well as the errors induced by device noise affect the calculation.
arXiv Detail & Related papers (2021-12-31T16:33:10Z) - 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) - Practical Quantum Computing: solving the wave equation using a quantum
approach [0.0]
We show that our implementation of the quantum wave equation solver agrees with the theoretical big-O complexity of the algorithm.
Our implementation proves experimentally that some PDE can be solved on a quantum computer.
arXiv Detail & Related papers (2020-03-27T15:05:31Z) - 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.