A Quantum Complexity Lowerbound from Differential Geometry

• URL: http://arxiv.org/abs/2112.05724v1
• Date: Fri, 10 Dec 2021 18:28:01 GMT
• Title: A Quantum Complexity Lowerbound from Differential Geometry
• Authors: Adam R. Brown
• Abstract summary: I apply the Bishop-Gromov bound to Nielsen's complexity geometry to prove lowerbounds on the quantum complexity of a typical unitary. For a broad class of penalty schedules, the typical complexity is shown to be exponentially large in the number of qubits. This method realizes the original vision of Nielsen, which was to apply the tools of differential geometry to study quantum complexity.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Bishop-Gromov bound -- a cousin of the focusing lemmas that Hawking and Penrose used to prove their black hole singularity theorems -- is a differential geometry result that upperbounds the rate of growth of volume of geodesic balls in terms of the Ricci curvature. In this paper, I apply the Bishop-Gromov bound to Nielsen's complexity geometry to prove lowerbounds on the quantum complexity of a typical unitary. For a broad class of penalty schedules, the typical complexity is shown to be exponentially large in the number of qubits. This technique gives results that are tighter than all known lowerbounds in the literature, as well as establishing lowerbounds for a much broader class of complexity geometry metrics than has hitherto been bounded. For some metrics, I prove these lowerbounds are tight. This method realizes the original vision of Nielsen, which was to apply the tools of differential geometry to study quantum complexity.

Related papers

• Gaussian Entanglement Measure: Applications to Multipartite Entanglement of Graph States and Bosonic Field Theory [50.24983453990065]
  An entanglement measure based on the Fubini-Study metric has been recently introduced by Cocchiarella and co-workers. We present the Gaussian Entanglement Measure (GEM), a generalization of geometric entanglement measure for multimode Gaussian states. By providing a computable multipartite entanglement measure for systems with a large number of degrees of freedom, we show that our definition can be used to obtain insights into a free bosonic field theory.
  arXiv  Detail & Related papers  (2024-01-31T15:50:50Z)
• Fluctuations, uncertainty relations, and the geometry of quantum state manifolds [0.0]
  The complete quantum metric of a parametrized quantum system has a real part and a symplectic imaginary part. We show that for a mixed quantum-classical system both real and imaginary parts of the quantum metric contribute to the dynamics.
  arXiv  Detail & Related papers  (2023-09-07T10:31:59Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Continuous percolation in a Hilbert space for a large system of qubits [58.720142291102135]
  The percolation transition is defined through the appearance of the infinite cluster. We show that the exponentially increasing dimensionality of the Hilbert space makes its covering by finite-size hyperspheres inefficient. Our approach to the percolation transition in compact metric spaces may prove useful for its rigorous treatment in other contexts.
  arXiv  Detail & Related papers  (2022-10-15T13:53:21Z)
• Polynomial Equivalence of Complexity Geometries [0.05657375260432172]
  This paper proves the equivalence of a broad class of definitions of quantum computational complexity. We study right-invariant metrics on the unitary group. We delineate the equivalence class of metrics that have the same computational power as quantum circuits.
  arXiv  Detail & Related papers  (2022-05-09T18:00:10Z)
• A singular Riemannian geometry approach to Deep Neural Networks I. Theoretical foundations [77.86290991564829]
  Deep Neural Networks are widely used for solving complex problems in several scientific areas, such as speech recognition, machine translation, image analysis. We study a particular sequence of maps between manifold, with the last manifold of the sequence equipped with a Riemannian metric. We investigate the theoretical properties of the maps of such sequence, eventually we focus on the case of maps between implementing neural networks of practical interest.
  arXiv  Detail & Related papers  (2021-12-17T11:43:30Z)
• Quantum Computational Complexity -- From Quantum Information to Black Holes and Back [0.0]
  Quantum computational complexity was suggested as a new entry in the holographic dictionary. We show how it can be used to define complexity for generic quantum systems. We highlight the relation between complexity, chaos and scrambling in chaotic systems.
  arXiv  Detail & Related papers  (2021-10-27T18:00:12Z)
• Bell's Theorem, Non-Computability and Conformal Cyclic Cosmology: A Top-Down Approach to Quantum Gravity [0.0]
  In IST, the fundamental laws of physics describe the geometry of the phase portrait of the universe as a whole. It becomes possible to explain the experimental violation of Bell Inequalities without having to abandon key ingredients of general relativity.
  arXiv  Detail & Related papers  (2021-08-24T18:12:16Z)
• Geometry of quantum complexity [0.0]
  Computational complexity is a new quantum information concept that may play an important role in holography. We consider quantum computational complexity for $n$ qubits using Nielsen's geometrical approach.
  arXiv  Detail & Related papers  (2020-11-15T18:41:19Z)
• Quantum Geometric Confinement and Dynamical Transmission in Grushin Cylinder [68.8204255655161]
  We classify the self-adjoint realisations of the Laplace-Beltrami operator minimally defined on an infinite cylinder. We retrieve those distinguished extensions previously identified in the recent literature, namely the most confining and the most transmitting.
  arXiv  Detail & Related papers  (2020-03-16T11:37:23Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.