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

• URL: http://arxiv.org/abs/2503.10753v1
• Date: Thu, 13 Mar 2025 18:00:01 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: Quantum complexity quantifies the difficulty of preparing a state, or implementing a unitary, using limited resources.<n>Different communities apply different tools to quantum complexity, as well as define complexity differently.<n>We cover multiple definitions of complexity, as well as their key properties and applications.
• 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, using limited resources. Over the past decade, quantum-complexity research has surged. Applications range from quantum computation to condensed matter and quantum gravity. Different communities apply different tools to quantum complexity, as well as define complexity differently. This review bridges the disciplines' approaches. We cover multiple definitions of complexity, as well as their key properties and applications. In quantum information, random quantum circuits proved to be an invaluable tool in extracting properties of the complexity growth of discrete quantum circuits. In quantum many-body systems and quantum field theory (QFT), complexity is defined geometrically through geodesics. Complexity can be defined also in terms of state or operator spreading and tensor-network concepts. In addition to reviewing these approaches, we outline applications to simple quantum systems, quantum many-body models and QFTs, including conformal field theories (CFTs). Finally, we detail the relationship between complexity and gravitational observables within the anti-de Sitter-space (AdS)/CFT correspondence. This review thereby integrates recent quantum-complexity advances across fields.

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)
• 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)
• 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)
• 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.