Quantum Computational Complexity -- From Quantum Information to Black Holes and Back

• URL: http://arxiv.org/abs/2110.14672v1
• Date: Wed, 27 Oct 2021 18:00:12 GMT
• Title: Quantum Computational Complexity -- From Quantum Information to Black Holes and Back
• Authors: Shira Chapman, Giuseppe Policastro
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computational complexity estimates the difficulty of constructing quantum states from elementary operations, a problem of prime importance for quantum computation. Surprisingly, this quantity can also serve to study a completely different physical problem - that of information processing inside black holes. Quantum computational complexity was suggested as a new entry in the holographic dictionary, which extends the connection between geometry and information and resolves the puzzle of why black hole interiors keep growing for a very long time. In this pedagogical review, we present the geometric approach to complexity advocated by Nielsen and show how it can be used to define complexity for generic quantum systems; in particular, we focus on Gaussian states in QFT, both pure and mixed, and on certain classes of CFT states. We then present the conjectured relation to gravitational quantities within the holographic correspondence and discuss several examples in which different versions of the conjectures have been tested. We highlight the relation between complexity, chaos and scrambling in chaotic systems. We conclude with a discussion of open problems and future directions. This article was written for the special issue of EPJ-C Frontiers in Holographic Duality.

Related papers

• Quantum Information Processing with Molecular Nanomagnets: an introduction [49.89725935672549]
  We provide an introduction to Quantum Information Processing, focusing on a promising setup for its implementation. We introduce the basic tools to understand and design quantum algorithms, always referring to their actual realization on a molecular spin architecture. We present some examples of quantum algorithms proposed and implemented on a molecular spin qudit hardware.
  arXiv  Detail & Related papers  (2024-05-31T16:43:20Z)
• Taming Quantum Time Complexity [50.10645865330582]
  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)
• Saturation and recurrence of quantum complexity in random local quantum dynamics [5.803309695504831]
  Quantum complexity is a measure of the minimal number of elementary operations required to prepare a given state or unitary channel. Brown and Susskind conjectured that the complexity of a chaotic quantum system grows linearly in time up to times exponential in the system size, saturating at a maximal value, and remaining maximally complex until undergoing recurrences at doubly-exponential times.
  arXiv  Detail & Related papers  (2022-05-19T17:42:31Z)
• A thorough introduction to non-relativistic matrix mechanics in multi-qudit systems with a study on quantum entanglement and quantum quantifiers [0.0]
  This article provides a deep and abiding understanding of non-relativistic matrix mechanics. We derive and analyze the respective 1-qubit, 1-qutrit, 2-qubit, and 2-qudit coherent and incoherent density operators. We also address the fundamental concepts of quantum nondemolition measurements, quantum decoherence and, particularly, quantum entanglement.
  arXiv  Detail & Related papers  (2021-09-14T05:06:47Z)
• Modave Lectures on Quantum Information: An Introduction to Channels and Applications to Black Holes and AdS/CFT [0.0]
  We will study channels and their properties, and then go on to formulate quantum error correction in terms of quantum channels. We will see how a handful of problems in high energy physics, such as the black hole information problem and bulk reconstruction in AdS/CFT, can be cast in the information-theoretic language being set up.
  arXiv  Detail & Related papers  (2021-02-03T13:52:38Z)
• 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)
• 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 information spreading in a disordered quantum walk [50.591267188664666]
  We design a quantum probing protocol using Quantum Walks to investigate the Quantum Information spreading pattern. We focus on the coherent static and dynamic disorder to investigate anomalous and classical transport. Our results show that a Quantum Walk can be considered as a readout device of information about defects and perturbations occurring in complex networks.
  arXiv  Detail & Related papers  (2020-10-20T20:03:19Z)

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.