Unitary Complexity and the Uhlmann Transformation Problem
- URL: http://arxiv.org/abs/2306.13073v2
- Date: Mon, 20 Nov 2023 03:45:51 GMT
- Title: Unitary Complexity and the Uhlmann Transformation Problem
- Authors: John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen
Qian, Henry Yuen
- Abstract summary: 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.
- Score: 41.67228730328207
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: State transformation problems such as compressing quantum information or
breaking quantum commitments are fundamental quantum tasks. However, their
computational difficulty cannot easily be characterized using traditional
complexity theory, which focuses on tasks with classical inputs and outputs.
To study the complexity of such state transformation tasks, 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. We
formalize this as the Uhlmann Transformation Problem, an algorithmic version of
Uhlmann's theorem. Then, we prove structural results relating the complexity of
the Uhlmann Transformation Problem, polynomial space quantum computation, and
zero knowledge protocols.
The Uhlmann Transformation Problem allows us to characterize the complexity
of a variety of tasks in quantum information processing, including decoding
noisy quantum channels, breaking falsifiable quantum cryptographic assumptions,
implementing optimal prover strategies in quantum interactive proofs, and
decoding the Hawking radiation of black holes. Our framework for unitary
complexity thus provides new avenues for studying the computational complexity
of many natural quantum information processing tasks.
Related papers
- 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) - Character Complexity: A Novel Measure for Quantum Circuit Analysis [0.0]
This paper introduces Character Complexity, a novel measure that bridges Group-theoretic concepts with practical quantum computing concerns.
I prove several key properties of character complexity and establish a surprising connection to the classical simulability of quantum circuits.
I present innovative visualization methods for character complexity, providing intuitive insights into the structure of quantum circuits.
arXiv Detail & Related papers (2024-08-19T01:58:54Z) - Parameterized quantum comb and simpler circuits for reversing unknown
qubit-unitary operations [8.630679964089696]
PQComb is a framework leveraging parameterized quantum circuits to explore the capabilities of quantum combs.
We develop a protocol for unknown qubit unitary inversion that reduces the ancilla qubit overhead from 6 to 3.
Our results pave the way for broader PQComb applications in quantum computing and quantum information.
arXiv Detail & Related papers (2024-03-06T14:53:24Z) - 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) - Complexity analysis of weakly noisy quantum states via quantum machine
learning [1.203955415344484]
We focus on the complexity of weakly noisy states, which we define as the size of the shortest quantum circuit required to prepare the noisy state.
We propose a quantum machine learning (QML) algorithm that exploits the intrinsic-connection property of structured quantum neural networks.
arXiv Detail & Related papers (2023-03-31T06:02:44Z) - stateQIP = statePSPACE [0.15229257192293197]
We study the relation between two such state classes:SDPPSPACE, and stateQIP.
Our main result is the reverse inclusion, stateQIP $subseteq$ statePSPACE.
We also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum space.
arXiv Detail & Related papers (2023-01-18T19:00:17Z) - Circuit Symmetry Verification Mitigates Quantum-Domain Impairments [69.33243249411113]
We propose circuit-oriented symmetry verification that are capable of verifying the commutativity of quantum circuits without the knowledge of the quantum state.
In particular, we propose the Fourier-temporal stabilizer (STS) technique, which generalizes the conventional quantum-domain formalism to circuit-oriented stabilizers.
arXiv Detail & Related papers (2021-12-27T21:15:35Z) - 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) - 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) - 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)
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.