REVIEW 5 cited by
Unitary Complexity and the Uhlmann Transformation Problem
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Forward citations
Cited by 5 Pith papers
-
The Keyl-Werner algorithm is not optimal for spectrum estimation
Spectrum estimation of a d-dimensional quantum state is possible with o(d²) copies—specifically O(d² (log log d / log d)²)—beating Keyl–Werner and full tomography.
-
Local transformations of bipartite entanglement are rigid
Optimal Uhlmann transformations are robustly rigid: unitaries achieving fidelity within epsilon of optimal must be within (2 kappa / eta) epsilon of the canonical transformation, where eta and kappa are the spectral g...
-
A complexity theory for non-local quantum computation
f-route, f-measure and CDQS are equivalent under O(1) overhead reductions, so known upper and lower bounds for each transfer to the other two.
-
Optimal fidelity estimation when one state is pure via algorithmic Uhlmann transform
When at least one of two quantum states is pure, the Uhlmann fidelity can be estimated with Θ(1/ε) queries and Θ(1/ε²) samples without knowing which state is pure, matching the optimal lower bounds.
-
A slightly improved upper bound for quantum statistical zero-knowledge
QSZK and its non-interactive variant NIQSZK stay inside QIP(2)∩co-QIP(2), now with an honest prover that runs in quantum linear space and single-exponential time.
Discussion (0). Continue with ORCID to comment.