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

• Complexity Theory for Quantum Promise Problems [5.049812996253858]
  We study the relationship between quantum cryptography and complexity theory, especially within Impagliazzo's five worlds framework. We focus on complexity classes p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, and p/mPSPACE, where "p/mC" denotes classes with pure (p) or mixed (m) states. We apply this framework to cryptography, showing that breaking one-way state generators, pseudorandom states, and EFI is bounded by mQCMA or
  arXiv  Detail & Related papers  (2024-11-06T07:29:52Z)
• 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)
• 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)
• 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)
• 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)
• 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)
• 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.