Physical review. A/Physical review, A · 2022 · 26 citations · 107 references
ComputingComputer SciencePhysicsInformation TheoryQuantum ComputingQuantum MechanicsComplexity TheoryComputational ComplexityQuantum BitsQuantum ComputationQuantum GatesQuantum Information TheoryMany-body Quantum SystemsMulti-qubit GatesQuantum Circuit ComplexityQuantum ComplexityQuantum Many-body SystemsResource Theories Of Quantum InformationResource-bounded ComplexityTwo-qubit Gates
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.
107
<i>Quantum Computation and Quantum Information</i>
Michael A. Nielsen, Isaac L. Chuang, Lov K. Grover · American Journal of Physics · 2002 · 22.7K citations
Quantum computation and quantum information
Jim Law · ACM SIGSOFT Software Engineering Notes · 2001 · 19.2K citations
Computing, Computer Science, Physics +13
Ryszard Horodecki, Paweł Horodecki, Michał Horodecki et al. · Reviews of Modern Physics · 2009 · 10K citations · Full text
Computing, Physics, Cryptography +16
Quantum supremacy using a programmable superconducting processor
Nature · 2019 · 7K citations · Full text
Computing, Computer Science, Physics +14
Tillmann Baumgratz, M. Cramer, Martin B. Plenio · Physical Review Letters · 2014 · 2.7K citations · Full text