Related papers: Two Simple Proofs of Müller's Theorem

Two Simple Proofs of Müller's Theorem

URL: http://arxiv.org/abs/2402.05328v4
Date: Tue, 2 Jul 2024 21:40:31 GMT
Title: Two Simple Proofs of Müller's Theorem
Authors: Samuel Epstein,
Abstract summary: M"uller's theorem is arguably the most important result in the intersection of algorithmic information theory and physics. The quantitative amount of information in classical sources is invariant to the physical model used.
Score: 6.5268245109828005
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Due to M\"{u}ller's theorem, the Kolmogorov complexity of a string was shown to be equal to its quantum Kolmogorov complexity. Thus there are no benefits to using quantum mechanics to compress classical information. The quantitative amount of information in classical sources is invariant to the physical model used. These consequences make this theorem arguably the most important result in the intersection of algorithmic information theory and physics. The original proof is quite extensive. This paper contains two simple proofs of this theorem. This paper also contains new bounds for quantum Kolmogorov complexity with error.

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)
Connecting classical finite exchangeability to quantum theory [69.62715388742298]
Exchangeability is a fundamental concept in probability theory and statistics. We show how a de Finetti-like representation theorem for finitely exchangeable sequences requires a mathematical representation which is formally equivalent to quantum theory.
arXiv Detail & Related papers (2023-06-06T17:15:19Z)
On Kirkwood--Dirac quasiprobabilities and unravelings of quantum channel assigned to a tight frame [0.0]
Using vectors of the given tight frame to build principal Kraus operators generates quasiprobabilities with interesting properties. New inequalities for characterizing the location of eigenvalues are derived. A utility of the presented inequalities is exemplified with symmetric informationally complete measurement in dimension two.
arXiv Detail & Related papers (2023-04-27T09:11:11Z)
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)
Connes implies Tsirelson: a simple proof [91.3755431537592]
We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
arXiv Detail & Related papers (2022-09-16T13:59:42Z)
Quantum-inspired permanent identities [0.0]
In quantum computing, the permanent appears in the expression of output amplitudes of linear optical computations. We give quantum-inspired proofs of many existing as well as new remarkable permanent identities.
arXiv Detail & Related papers (2022-07-31T00:24:17Z)
Generalized Gleason theorem and finite amount of information for the context [0.0]
Quantum processes cannot be reduced to classical processes without specifying the context in the description of a measurement procedure. We consider a class of hidden variable theories by assuming that the amount of information about the measurement context is finite.
arXiv Detail & Related papers (2022-06-23T16:55:50Z)
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)
A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
arXiv Detail & Related papers (2019-09-04T11:46:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.