Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1502.07545

SAT problem and statistical distance

Feng Pan

Published Feb 26, 2015• 0 citations
arXivHTMLPDF

Abstract

In this paper with two equivalent representations of the information contained by a SAT formula, the reason why string generated by succinct SAT formula can be greatly compressed is firstly presented based on Kolmogorov complexity theory. Then what strings can be greatly compressed were classified and discussed. In this way we discovered the SAT problem was composed of a basic distinguish problem: distinguish two different distributions induced under the computer with certain SAT formula ensemble. We then tried to map this problem into quantum mechanics, or the quantum version basic distinguish problem: this time two different distributions are induced under quantum mechanics. Based on the equivalence of statistical distance between probability space and Hilbert space, in the same time this distance is invariant under all unitary transformations. The quantum version basic problem cannot be efficiently solved by any quantum computer. In the worst case, any quantum computer must perform exponential times measurement in order to solve it. In the end we proposed the main theorem : The statistical distance in program space and probability space are identical. We tried to prove it using the relationship of Kolmogorov complexity and entropy. It showed there is no difference to solve the basic problem in SAT formula space or probability space. In the worst case, exponential trials must be performed to solve it. NP!=P.

DOI
10.48550/arxiv.1502.07545

Related papers

Second quantised information distance

Songsong Dai

Abstract The Kolmogorov complexity of a string is the minimum length of a programme that can produce that string. Information distance between two strings based on Kolmogorov complexity is defined as the minimum length of a programme that can transform either string into the other one, both ways. The second quantised Kolmogorov complexity of a quantum state is the minimum average length of a quantum programme that can reproduce that state. In this paper, a second quantised information distance is defined based on the second quantised Kolmogorov complexity. It is described as the minimum average length of a transformation quantum programme between two quantum states. This distance's basic properties are discussed. A practical analogue of quantum information distance is also developed based on quantum data compression.

IET Quantum Communication•Sep 28, 2022•0 citations

Kolmogorov complexity upper bound of probability in computable POVM measurement (New Aspects of Theoretical Computer Science)

孝太郎 只木

We apply algorithmic information theory to quantum mechanics in order to shed light on an algorithmic structure which is inherent in quantum mechanics.There are two equivalent ways to define the (classical) Kolmogorov $\infty \mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{x}\mathrm{i}\mathrm{t}\mathrm{y}$ $K(s)$ of agiven classical finite binary string $s$ .In the standard way, $K(s)$ is defined as the length of the shortest input string for the universal self-delimiting Turing machine to output $s$ .In the other way, we first introduce the so-called universal probability $m$ , and then define $K(s)$ as $-\log_{2}m(s)$ without using the concept of program-size.We generalize the universal probability to amatrix-valued function, and identify this function with apositive operator-valued measure (POVM), which describes the statistics of outcomes in aquantum measurement in the general set- ting.Based on this identification, we study acomputable POVM measurement with countable measurement outcomes performed upon afinite dimensional quantum system.We show that, up to amultiplicative constant, $2^{-K(s)}$ is the upper bound for the probability of each measurement outcome $s$ in such aquantum measurement.In what follows, the upper bound $2^{-K(s)}$ is shown to be optimal in acertain sense.

数理解析研究所講究録•May 1, 2003•0 citations

Two Simple Proofs of Müller's Theorem

Samuel Epstein

Due to Mü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.

arXiv:2402.05328•Feb 8, 2024•0 citations

Classical-quantum mixing in the random 2-satisfiability problem

Ionut-Dragos Potirniche, Chris R. Laumann, S. L. Sondhi

Classical satisfiability (SAT) and quantum satisfiability (QSAT) are complete problems for the complexity classes NP and QMA, respectively, and they are believed to be intractable for both classical and quantum computers. Statistical ensembles of instances of these problems have been studied previously in an attempt to elucidate their typical, as opposed to worst-case, behavior. In this paper, we introduce a statistical ensemble that interpolates between classical and quantum. For the simplest 2-SAT--2-QSAT ensemble, we find the exact boundary that separates SAT and UNSAT instances. We do so by establishing coincident lower and upper bounds, in the limit of large instances, on the extent of the UNSAT and SAT regions, respectively.

arXiv:1502.04700•Physical Review A•Oct 1, 2015•1 citation

Statistical distance and Hilbert space

William K. Wootters

A concept of "statistical distance" is defined between different preparations of the same quantum system, or in other words, between different rays in the same Hilbert space. Statistical distance is determined entirely by the size of statistical fluctuations occurring in measurements designed to distinguish one state from another. It is not related, a priori, to the usual distance (or angle) between rays. One finds, however, that these two kinds of distance are in fact the same, a result which depends on certain peculiarities of quantum mechanics.

Physical review. D. Particles, fields, gravitation, and cosmology/Physical review. D. Particles and fields•Jan 15, 1981•805 citations

Distances Measures for Probability Distributions

Many problems of statistical and quantum mechanics can be established in terms of a distance between probability distributions. The present work is devoted to review some of the most relevant applications of the notion of distance in the context of statistical mechanics, quantum mechanics and information theory. Although we make a general overview of the most frequently used distances between probability distributions, we will center our presentation in a distance known as the Jensen-Shannon divergence both in their classical and quantum versions. For the classical one we present its main properties and we discuss its relevance as a segmentation tool for symbolic sequences. In the quantum case we show that the quantum Jensen-Shannon divergence is an adequate measure of entanglement.

BENTHAM SCIENCE PUBLISHERS eBooks•Dec 11, 2013•1 citation
In this paper with two equivalent representations of the information contained by a SAT formula, the reason why string generated by succinct SAT formula can be greatly compressed is firstly presented based on Kolmogorov complexity theory. Then what strings can be greatly compressed were classified and discussed. In this way we discovered the SAT problem was composed of a basic distinguish problem: distinguish two different distributions induced under the computer with certain SAT formula ensemble. We then tried to map this problem into quantum mechanics, or the quantum version basic distinguish problem: this time two different distributions are induced under quantum mechanics. Based on the equivalence of statistical distance between probability space and Hilbert space, in the same time this distance is invariant under all unitary transformations. The quantum version basic problem cannot be efficiently solved by any quantum computer. In the worst case, any quantum computer must perform exponential times measurement in order to solve it. In the end we proposed the main theorem : The statistical distance in program space and probability space are identical. We tried to prove it using the relationship of Kolmogorov complexity and entropy. It showed there is no difference to solve the basic problem in SAT formula space or probability space. In the worst case, exponential trials must be performed to solve it. NP!=P.
Abstract The Kolmogorov complexity of a string is the minimum length of a programme that can produce that string. Information distance between two strings based on Kolmogorov complexity is defined as the minimum length of a programme that can transform either string into the other one, both ways. The second quantised Kolmogorov complexity of a quantum state is the minimum average length of a quantum programme that can reproduce that state. In this paper, a second quantised information distance is defined based on the second quantised Kolmogorov complexity. It is described as the minimum average length of a transformation quantum programme between two quantum states. This distance's basic properties are discussed. A practical analogue of quantum information distance is also developed based on quantum data compression.
We apply algorithmic information theory to quantum mechanics in order to shed light on an algorithmic structure which is inherent in quantum mechanics.There are two equivalent ways to define the (classical) Kolmogorov ∞mplexity\infty \mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{x}\mathrm{i}\mathrm{t}\mathrm{y}∞mplexity K(s)K(s)K(s) of agiven classical finite binary string sss .In the standard way, K(s)K(s)K(s) is defined as the length of the shortest input string for the universal self-delimiting Turing machine to output sss .In the other way, we first introduce the so-called universal probability mmm , and then define K(s)K(s)K(s) as −log⁡2m(s)-\log_{2}m(s)−log2​m(s) without using the concept of program-size.We generalize the universal probability to amatrix-valued function, and identify this function with apositive operator-valued measure (POVM), which describes the statistics of outcomes in aquantum measurement in the general set- ting.Based on this identification, we study acomputable POVM measurement with countable measurement outcomes performed upon afinite dimensional quantum system.We show that, up to amultiplicative constant, 2−K(s)2^{-K(s)}2−K(s) is the upper bound for the probability of each measurement outcome sss in such aquantum measurement.In what follows, the upper bound 2−K(s)2^{-K(s)}2−K(s) is shown to be optimal in acertain sense.
Due to Mü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.
Classical satisfiability (SAT) and quantum satisfiability (QSAT) are complete problems for the complexity classes NP and QMA, respectively, and they are believed to be intractable for both classical and quantum computers. Statistical ensembles of instances of these problems have been studied previously in an attempt to elucidate their typical, as opposed to worst-case, behavior. In this paper, we introduce a statistical ensemble that interpolates between classical and quantum. For the simplest 2-SAT--2-QSAT ensemble, we find the exact boundary that separates SAT and UNSAT instances. We do so by establishing coincident lower and upper bounds, in the limit of large instances, on the extent of the UNSAT and SAT regions, respectively.
A concept of "statistical distance" is defined between different preparations of the same quantum system, or in other words, between different rays in the same Hilbert space. Statistical distance is determined entirely by the size of statistical fluctuations occurring in measurements designed to distinguish one state from another. It is not related, a priori, to the usual distance (or angle) between rays. One finds, however, that these two kinds of distance are in fact the same, a result which depends on certain peculiarities of quantum mechanics.
Many problems of statistical and quantum mechanics can be established in terms of a distance between probability distributions. The present work is devoted to review some of the most relevant applications of the notion of distance in the context of statistical mechanics, quantum mechanics and information theory. Although we make a general overview of the most frequently used distances between probability distributions, we will center our presentation in a distance known as the Jensen-Shannon divergence both in their classical and quantum versions. For the classical one we present its main properties and we discuss its relevance as a segmentation tool for symbolic sequences. In the quantum case we show that the quantum Jensen-Shannon divergence is an adequate measure of entanglement.