COMPLEXITY MEASURE: A QUANTUM INFORMATION APPROACH
6
Citation
65
Reference
10
Related Paper
Citation Trend
Abstract:
In the past decades, all of the efforts at quantifying systems complexity with a general tool has usually relied on using Shannon's classical information framework to address the disorder of the system through the Boltzmann–Gibbs–Shannon entropy, or one of its extensions. However, in recent years, there were some attempts to tackle the quantification of algorithmic complexities in quantum systems based on the Kolmogorov algorithmic complexity, obtaining some discrepant results against the classical approach. Therefore, an approach to the complexity measure is proposed here, using the quantum information formalism, taking advantage of the generality of the classical-based complexities, and being capable of expressing these systems' complexity on other framework than its algorithmic counterparts. To do so, the Shiner–Davison–Landsberg (SDL) complexity framework is considered jointly with linear entropy for the density operators representing the analyzed systems formalism along with the tangle for the entanglement measure. The proposed measure is then applied in a family of maximally entangled mixed state.Keywords:
Generality
Information Theory
Complex system
Formalism (music)
Quantum computation and information has become a central research area in theoretical computer science. It studies how information is encoded in nature according to the laws of quantum mechanics and what this means for its computational power. On one hand, the ability of a quantum system to be in a superposition of states provides a way to encode an exponential amount of information in a quantum state. However, this information is accessible only indirectly via measurements. The goal of this thesis is precisely to investigate the fundamental question of how information is encoded and processed in quantum mechanical systems. (1) We investigate their power relative to classical encodings in the model of one-way communication complexity and show that they can be exponentially more efficient, answering a long standing open question in the area of quantum communication complexity. (2) We show how the theory developed for the study of quantum information can be employed in order to answer questions about classical coding theory and complexity. We resolve a main open question about the efficiency of Locally Decodable Codes by reducing the problem to one about quantum codes and solving the latter using tools from quantum information theory. This is the first example where quantum techniques are essential in resolving a purely classical question. (3) We investigate the power of quantum encodings in the area of cryptography. We study certain cryptographic primitives, such as Private Information Retrieval, Symmetrically-Private Information Retrieval and Coin Flipping.
Cite
Citations (5)
This dissertation explores results at the intersection of two important branches of theoretical computer science: quantum computation, which studies the power of devices based on quantum physical phenomena, and computational theory, which studies the foundations of machine algorithms. We refer to the area of research at this intersection as quantum computational theory. Like its classical counterpart, quantum computational theory aims to understand the computational and information theoretic requirements of problems and algorithms. However unlike the classical models, the models for quantum learners generally involve quantum sources of information and quantum gates employing quantum physical phenomena such as superposition and entanglement, which do not have classical equivalents.
Our results can be summarized as follows: (1) In Chapter 3, we study the information theoretic requirements of quantum learning, partition and Probably Approximately Correct (PAC) learning. First, we develop a new general quantum algorithm, resolving a conjecture by Hunziker et al. [HMP+03]. Next, we present positive and negative results towards the rather general problem of partition of which both exact learning and computing a binary property are special cases. Finally, we derive an improved lower bound on the number of quantum examples required for PAC learning. (2) In Chapter 4, we consider the problem of unions of high dimensional rectangles over the domain [b]n using membership queries and uniform quantum examples. These classes oral generalizations of classes of DNF formulae over {0,1}n that have been extensively studied in the theory literature. (3) In Chapter 5, we develop quantum algorithms for and testing juntas (Boolean functions that depend on a few variables) and sparse functions. These algorithms are based on the quantum subroutine due to Bshouty and Jackson [BJ99] that enables sampling from the Fourier spectrum.
Quantum sort
Quantum capacity
Cite
Citations (2)
One of the principal themes of information theory is to establish a link between two different kinds of quantities: one is an operational quantity which is defined through the asymptotic optimality on some concrete concept such as code length, compression rate, error probability, etc., while the other is an abstract information quantity such as the entropy, divergence, mutual information, etc. The same theme is now being pursued extensively in quantum information theory, and lots of mathematical results have been reported so far. In the so-called information-spectrum methods in the classical information theory [1], the process of establishing a link between an operatinal quantity and an entropy-like information quantity is intentionally divided into two parts, making the third kind of quantities — information spectrum — intervene. In the methods, the asymptotic optimality of an operational quantity is characterized by a limiting expression on information spectra (asymptotic behavior of logarithmic likelihoods) in the most general setting, while the information-spectrum quantity is rewritten to an entropylike quantity in a specific situation mostly as a direct consequence of a limiting theorem in the probability theory such as the law of large numbers, the Shannon-McMillan-Breiman theorem, etc. Such a framework brings not only generality but also transparency of mathematical arguments. Extending the information-spectrum methods to the quantum case is an attractive subject, which is expected to provide both the asymptotic optimality of operational quantities and the limiting law governing quantum stochastic situations with transparent and comprehensive understanding. In this talk I would like to review recent attempts to develop the quantum informationspectrum methods made by Hayashi, Ogawa and myself, mainly based on [2, 3, 4], and discuss their significance in the quantum information theory.
Information Theory
Generality
Cite
Citations (0)
In this paper, we give a definition for quantum information distance. In the classical setting, information distance between two classical strings is developed based on classical Kolmogorov complexity. It is defined as the length of a shortest transition program between these two strings in a universal Turing machine. We define the quantum information distance based on Berthiaume et al.’s quantum Kolmogorov complexity. The quantum information distance between qubit strings is defined as the length of the shortest quantum transition program between these two qubit strings in a universal quantum Turing machine. We show that our definition of quantum information distance is invariant under the choice of the underlying quantum Turing machine.
Quantum Turing machine
Cite
Citations (2)
The article introduces the field of Information Physics, which combines concepts from information theory, physics, and mathematics to provide insights into information systems and their underlying principles. The concept of information entropy and energy are introduced to describe the information content and processing capabilities of information systems, respectively. The article proposes the idea of "full numbers" to represent information energy in information systems, and derives the Information Energy Exchange Equation (I = (E - mgh) / k), which relates information energy to potential energy, gravitational constant, and a proportionality constant k.The article also explores the application of quantum mechanics to unified field theory, bridging the gap between classical and quantum information systems, and investigates the relationships and roles of data fields and information fields in information systems. Finally, the article addresses the issue of information loss in information systems and proposes potential solutions.Overall, the article provides a comprehensive introduction to Information Physics, highlighting its potential for breakthroughs in information processing, communication, and quantum computing technologies.
Information Theory
Coherent information
Cite
Citations (0)
Information Theory
Classical capacity
Coherent information
Quantum mutual information
Cite
Citations (6)
Information Theory
Shannon–Hartley theorem
Classical capacity
Coherent information
Cornerstone
Cite
Citations (1)
A quantum mechanical compound state of an input state and its output state generated through a communication channel is constructed. The mutual information of quantum communication theory is defined by using the compound state, and its fundamental properties are studied.
Coherent information
Information Theory
Quantum mutual information
Cite
Citations (120)
We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum tasks. These are the fully quantum generalizations of the analogous quantities for bipartite classical tasks that have found many applications recently, in particular for proving communication complexity lower bounds and direct sum theorems. Finding such a quantum generalization of information complexity was one of the open problems recently raised by Braverman (STOC'12).
Quantum capacity
Cite
Citations (41)
No-teleportation theorem
Kolmogorov structure function
Quantum Turing machine
Cite
Citations (1)