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

• Comparing quantum complexity and quantum fidelity [0.0]
  We show that complexity provides the same information as quantum fidelity and is therefore capable of detecting quantum phase transitions. We conclude that incorporating a notion of spatial locality into the computation of complexity is essential to uncover new physics.
  arXiv  Detail & Related papers  (2025-03-12T13:04:57Z)
• 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.