Quantum complexity in gravity, quantum field theory, and quantum information science

• URL: http://arxiv.org/abs/2503.10753v2
• Date: Wed, 14 May 2025 14:03:44 GMT
• Title: Quantum complexity in gravity, quantum field theory, and quantum information science
• Authors: Stefano Baiguera, Vijay Balasubramanian, Pawel Caputa, Shira Chapman, Jonas Haferkamp, Michal P. Heller, Nicole Yunger Halpern,
• Abstract summary: We describe several definitions of complexity, along with their key properties.<n>In quantum many-body systems and quantum field theory (QFT), we discuss a geometric definition of complexity in terms of geodesics on the unitary group.<n>We also outline applications to simple quantum systems, quantum many-body models, and QFTs including conformal field theories (CFTs)
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum complexity quantifies the difficulty of preparing a state or implementing a unitary transformation with limited resources. Applications range from quantum computation to condensed matter physics and quantum gravity. We seek to bridge the approaches of these fields, which define and study complexity using different frameworks and tools. We describe several definitions of complexity, along with their key properties. In quantum information theory, we focus on complexity growth in random quantum circuits. In quantum many-body systems and quantum field theory (QFT), we discuss a geometric definition of complexity in terms of geodesics on the unitary group. In dynamical systems, we explore a definition of complexity in terms of state or operator spreading, as well as concepts from tensor-networks. We also outline applications to simple quantum systems, quantum many-body models, and QFTs including conformal field theories (CFTs). Finally, we explain the proposed relationship between complexity and gravitational observables within the holographic anti-de Sitter (AdS)/CFT correspondence.

Related papers

• Strict advantage of complex quantum theory in a communication task [0.0]
  We investigate how the presence of complex amplitudes in quantum theory can yield operational advantages over counterpart real formulations.<n>We identify a straightforward communication task for which complex quantum theory exhibits a provably lower communication cost.<n>This substantiates a strict operational advantage of complex quantum theory.
  arXiv  Detail & Related papers  (2025-05-22T11:06:09Z)
• A Survey of Quantum Transformers: Architectures, Challenges and Outlooks [82.4736481748099]
  Quantum Transformers integrate the representational power of classical Transformers with the computational advantages of quantum computing.<n>Since 2022, research in this area has rapidly expanded, giving rise to diverse technical paradigms and early applications.<n>This paper presents the first comprehensive, systematic, and in-depth survey of quantum Transformer models.
  arXiv  Detail & Related papers  (2025-04-04T05:40:18Z)
• On the Complexity of Quantum Field Theory [0.0]
  We show that from minimal assertions, one is naturally led to measure complexity by two integers, called format and degree.<n>We discuss the physical interpretation of our approach in the context of perturbation theory, symmetries, and the renormalization group.
  arXiv  Detail & Related papers  (2024-10-30T18:00:00Z)
• 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)
• Character Complexity: A Novel Measure for Quantum Circuit Analysis [0.0]
  This paper introduces Character Complexity, a novel measure that bridges Group-theoretic concepts with practical quantum computing concerns. I prove several key properties of character complexity and establish a surprising connection to the classical simulability of quantum circuits. I present innovative visualization methods for character complexity, providing intuitive insights into the structure of quantum circuits.
  arXiv  Detail & Related papers  (2024-08-19T01:58:54Z)
• 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 algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Unitary Complexity and the Uhlmann Transformation Problem [41.67228730328207]
  We introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
  arXiv  Detail & Related papers  (2023-06-22T17:46:39Z)
• Learning marginals suffices! [14.322753787990036]
  We investigate the relationship between the sample complexity of learning a quantum state and the circuit complexity of the state. We show that learning its marginals for the quantum state with low circuit complexity suffices for state tomography.
  arXiv  Detail & Related papers  (2023-03-15T21:09:29Z)
• Optimal Stochastic Resource Allocation for Distributed Quantum Computing [50.809738453571015]
  We propose a resource allocation scheme for distributed quantum computing (DQC) based on programming to minimize the total deployment cost for quantum resources. The evaluation demonstrates the effectiveness and ability of the proposed scheme to balance the utilization of quantum computers and on-demand quantum computers.
  arXiv  Detail & Related papers  (2022-09-16T02:37:32Z)
• Wasserstein Complexity of Quantum Circuits [10.79258896719392]
  Given a unitary transformation, what is the size of the smallest quantum circuit that implements it? This quantity, known as the quantum circuit complexity, is a fundamental property of quantum evolutions. We show that our new measure also provides a lower bound for the experimental cost of implementing quantum circuits.
  arXiv  Detail & Related papers  (2022-08-12T14:44:13Z)
• Primordial Gravitational Wave Circuit Complexity [0.0]
  Quantum information theoretic concepts, such as entanglement entropy, and complexity are playing a pivotal role to understand the dynamics of quantum system. This paper is devoted in studying quantum circuit complexity of PGW for various cosmological models.
  arXiv  Detail & Related papers  (2021-08-23T18:00:12Z)
• Quantum Meets the Minimum Circuit Size Problem [3.199102917243584]
  We study the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. We show that these problems are not trivially in NP but in QCMA (or have QCMA protocols)
  arXiv  Detail & Related papers  (2021-08-06T15:34:49Z)
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface [68.8204255655161]
  Advances in isolating, controlling and entangling quantum systems are transforming what was once a curious feature of quantum mechanics into a vehicle for disruptive scientific and technological progress. From the perspective of three domain science theorists, this article compiles thoughts about the interface on entanglement, complexity, and quantum simulation.
  arXiv  Detail & Related papers  (2021-07-10T06:12:06Z)
• On exploring the potential of quantum auto-encoder for learning quantum systems [60.909817434753315]
  We devise three effective QAE-based learning protocols to address three classically computational hard learning problems. Our work sheds new light on developing advanced quantum learning algorithms to accomplish hard quantum physics and quantum information processing tasks.
  arXiv  Detail & Related papers  (2021-06-29T14:01:40Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
  arXiv  Detail & Related papers  (2021-01-21T22:18:49Z)
• 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)

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.