Lie groups for quantum complexity and barren plateau theory

• URL: http://arxiv.org/abs/2507.22590v1
• Date: Wed, 30 Jul 2025 11:46:09 GMT
• Title: Lie groups for quantum complexity and barren plateau theory
• Authors: P. A. S. de Alcântara, Gabriel Audi, Leandro Morais,
• Abstract summary: We introduce the theory of Lie groups and their algebras to analyze two fundamental problems in quantum computing.<n> Firstly, we describe the geometric formulation of quantum computational complexity.<n> Secondly, we deal with the barren plateau phenomenon in Variational Quantum Algorithms.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Advances in quantum computing over the last two decades have required sophisticated mathematical frameworks to deepen the understanding of quantum algorithms. In this review, we introduce the theory of Lie groups and their algebras to analyze two fundamental problems in quantum computing as done in some recent works. Firstly, we describe the geometric formulation of quantum computational complexity, given by the length of the shortest path on the $SU(2^n)$ manifold with respect to a right-invariant Finsler metric. Secondly, we deal with the barren plateau phenomenon in Variational Quantum Algorithms (VQAs), where we use the Dynamical Lie Algebra (DLA) to identify algebraic sources of untrainability

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• From Entanglement to Universality: A Multiparticle Spacetime Algebra Approach to Quantum Computational Gates Revisited [0.0]
  We focus on testing the usefulness of geometric algebras (GAs) techniques in two applications to quantum computing. First, we offer an explicit algebraic characterization of one- and two-qubit quantum states together with a MSTA description of one- and two-qubit quantum computational gates. In this first application, we devote special attention to the concept of entanglement, focusing on entangled quantum states and two-qubit entangling quantum gates.
  arXiv  Detail & Related papers  (2024-05-13T19:51:26Z)
• Quantum computing topological invariants of two-dimensional quantum matter [0.0]
  We present two quantum circuits for calculating Chern numbers of two-dimensional quantum matter on quantum computers.<n>First algorithm uses many qubits, and we analyze it using a tensor-network simulator of quantum circuits.<n>Second circuit uses fewer qubits, and we implement it experimentally on a quantum computer based on superconducting qubits.
  arXiv  Detail & Related papers  (2024-04-09T06:22:50Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Lower bounds for quantum-inspired classical algorithms via communication complexity [0.5461938536945723]
  We focus on lower bounds for solving linear regressions, supervised clustering, principal component analysis, recommendation systems, and Hamiltonian simulations.<n>We prove a quadratic lower bound in terms of the Frobenius norm of the underlying matrix.<n>As quantum algorithms are linear in the Frobenius norm for those problems, our results mean that the quantum-classical separation is at least quadratic.
  arXiv  Detail & Related papers  (2024-02-24T02:15:00Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• Quantum Circuit Completeness: Extensions and Simplifications [44.99833362998488]
  The first complete equational theory for quantum circuits has only recently been introduced. We simplify the equational theory by proving that several rules can be derived from the remaining ones. The complete equational theory can be extended to quantum circuits with ancillae or qubit discarding.
  arXiv  Detail & Related papers  (2023-03-06T13:31:27Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantum communication complexity of linear regression [0.05076419064097732]
  We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems. We propose an efficient quantum protocol for quantum singular value transformation.
  arXiv  Detail & Related papers  (2022-10-04T13:27:01Z)
• 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)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Linear algebra and quantum algorithm [0.0]
  Quantum algorithm is expressed by linear algebra on a finite dimensional complex inner product space. The mathematical formulations of quantum mechanics had been established in around 1930, by von Neumann.
  arXiv  Detail & Related papers  (2020-08-14T08:09:12Z)

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.