Resource theory of quantum uncomplexity
- URL: http://arxiv.org/abs/2110.11371v2
- Date: Mon, 19 Dec 2022 21:12:50 GMT
- Title: Resource theory of quantum uncomplexity
- Authors: Nicole Yunger Halpern, Naga B. T. Kothakonda, Jonas Haferkamp, Anthony
Munson, Jens Eisert, Philippe Faist
- Abstract summary: 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.
- Score: 0.5872014229110214
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum complexity is emerging as a key property of many-body systems,
including black holes, topological materials, and early quantum computers. A
state's complexity quantifies the number of computational gates required to
prepare the state from a simple tensor product. The greater a state's distance
from maximal complexity, or "uncomplexity," the more useful the state is as
input to a quantum computation. Separately, resource theories -- simple models
for agents subject to constraints -- are burgeoning in quantum information
theory. We unite the two domains, confirming Brown and Susskind's conjecture
that a resource theory of uncomplexity can be defined. The allowed operations,
fuzzy operations, are slightly random implementations of two-qubit gates chosen
by an agent. We formalize two operational tasks, uncomplexity extraction and
expenditure. Their optimal efficiencies depend on an entropy that we engineer
to reflect complexity. We also present two monotones, uncomplexity measures
that decline monotonically under fuzzy operations, in certain regimes. This
work unleashes on many-body complexity the resource-theory toolkit from quantum
information theory.
Related papers
- 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) - Resource-Dependent Complexity of Quantum Channels [6.154271758042505]
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.
arXiv Detail & Related papers (2023-03-20T17:44:57Z) - 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) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
Coherent control of quantum computations can be used to improve some quantum protocols and algorithms.
We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
arXiv Detail & Related papers (2022-02-10T18:59:52Z) - 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) - Detailed Account of Complexity for Implementation of Some Gate-Based
Quantum Algorithms [55.41644538483948]
In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself.
We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
arXiv Detail & Related papers (2021-06-23T16:33:33Z) - 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) - Operational Resource Theory of Imaginarity [48.7576911714538]
We show that quantum states are easier to create and manipulate if they only have real elements.
As an application, we show that imaginarity plays a crucial role for state discrimination.
arXiv Detail & Related papers (2020-07-29T14:03:38Z)
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.