Resource-Dependent Complexity of Quantum Channels

• URL: http://arxiv.org/abs/2303.11304v3
• Date: Tue, 31 Oct 2023 17:11:14 GMT
• Title: Resource-Dependent Complexity of Quantum Channels
• Authors: Roy Araiza, Yidong Chen, Marius Junge and Peixue Wu
• Abstract summary: Quantum complexity is concerned with the amount of elementary quantum resources needed to build a quantum system or a quantum operation. We propose a unified framework for textitresource-dependent complexity measures of general quantum channels.
• Score: 6.154271758042505
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum complexity theory is concerned with the amount of elementary quantum resources needed to build a quantum system or a quantum operation. The fundamental question in quantum complexity is to define and quantify suitable complexity measures. This non-trivial question has attracted the attention of quantum information scientists, computer scientists, and high energy physicists alike. In this paper, we combine the approach in \cite{LBKJL} and well-established tools from noncommutative geometry \cite{AC, MR, CS} to propose a unified framework for \textit{resource-dependent complexity measures of general quantum channels}, also known as \textit{Lipschitz complexity}. This framework is suitable to study the complexity of both open and closed quantum systems. The central class of examples in this paper is the so-called \textit{Wasserstein complexity} introduced in \cite{LBKJL, PMTL}. We use geometric methods to provide upper and lower bounds on this class of complexity measures \cite{N1,N2,N3}. Finally, we study the Lipschitz complexity of random quantum circuits and dynamics of open quantum systems in finite dimensional setting. In particular, we show that generically the complexity grows linearly in time before the \textit{return time}. This is the same qualitative behavior conjecture by Brown and Susskind \cite{BS1, BS2}. We also provide an infinite dimensional example where linear growth does not hold.

Related papers

• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• 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)
• 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 Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• 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)
• Quantum Computational Complexity -- From Quantum Information to Black Holes and Back [0.0]
  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.
  arXiv  Detail & Related papers  (2021-10-27T18:00:12Z)
• Resource theory of quantum uncomplexity [0.5872014229110214]
  We prove Brown and Susskind's conjecture that a resource theory of uncomplexity can be defined. This work unleashes on many-body complexity the resource-theory toolkit from quantum information theory.
  arXiv  Detail & Related papers  (2021-10-21T18:00:01Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• How smooth is quantum complexity? [0.0]
  The "quantum complexity" of a unitary operator measures the difficulty of its construction from a set of elementary quantum gates. In this paper, we present a unified perspective on various notions of quantum complexity, viewed as functions on the space of unitary operators.
  arXiv  Detail & Related papers  (2021-06-15T17:58:08Z)
• The Second Law of Quantum Complexity and the Entanglement Wormhole [0.0]
  Quantum complexity arises as an alternative measure to the Fubini metric between two quantum states. It is defined as the least complex unitary operator capable of transforming one state into the other.
  arXiv  Detail & Related papers  (2021-04-11T15:23:47Z)

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.