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:quant-ph/9510005

Quantum Algorithmic Information Theory

Karl Svozil

Published Oct 5, 1995• 28 citations
arXivHTMLPDF

Abstract

The agenda of quantum algorithmic information theory, ordered `top-down,' is the quantum halting amplitude, followed by the quantum algorithmic information content, which in turn requires the theory of quantum computation. The fundamental atoms processed by quantum computation are the quantum bits which are dealt with in quantum information theory. The theory of quantum computation will be based upon a model of universal quantum computer whose elementary unit is a two-port interferometer capable of arbitrary $U(2)$ transformations. Basic to all these considerations is quantum theory, in particular Hilbert space quantum mechanics.

DOI
10.3217/jucs-002-05-0311

Related papers

Quantum computing

Andrew M. Steane

The subject of quantum computing brings together ideas from classical information theory, computer science, and quantum physics. This review aims to summarize not just quantum computing, but the whole subject of quantum information theory. Information can be identified as the most general thing which must propagate from a cause to an effect. It therefore has a fundamentally important role in the science of physics. However, the mathematical treatment of information, especially information processing, is quite recent, dating from the mid-20th century. This has meant that the full significance of information as a basic concept in physics is only now being discovered. This is especially true in quantum mechanics. The theory of quantum information and computing puts this significance on a firm footing, and has led to some profound and exciting new insights into the natural world. Among these are the use of quantum states to permit the secure transmission of classical information (quantum cryptography), the use of quantum entanglement to permit reliable transmission of quantum states (teleportation), the possibility of preserving quantum coherence in the presence of irreversible noise processes (quantum error correction), and the use of controlled quantum evolution for efficient computation (quantum computation). The common theme of all these insights is the use of quantum entanglement as a computational resource. It turns out that information theory and quantum mechanics fit together very well. In order to explain their relationship, this review begins with an introduction to classical information theory and computer science, including Shannon's theorem, error correcting codes, Turing machines and computational complexity. The principles of quantum mechanics are then outlined, and the Einstein, Podolsky and Rosen (EPR) experiment described. The EPR-Bell correlations, and quantum entanglement in general, form the essential new ingredient which distinguishes quantum from classical information theory and, arguably, quantum from classical physics. Basic quantum information ideas are next outlined, including qubits and data compression, quantum gates, the `no cloning' property and teleportation. Quantum cryptography is briefly sketched. The universal quantum computer (QC) is described, based on the Church-Turing principle and a network model of computation. Algorithms for such a computer are discussed, especially those for finding the period of a function, and searching a random list. Such algorithms prove that a QC of sufficiently precise construction is not only fundamentally different from any computer which can only manipulate classical information, but can compute a small class of functions with greater efficiency. This implies that some important computational tasks are impossible for any device apart from a QC. To build a universal QC is well beyond the abilities of current technology. However, the principles of quantum information physics can be tested on smaller devices. The current experimental situation is reviewed, with emphasis on the linear ion trap, high- Q optical cavities, and nuclear magnetic resonance methods. These allow coherent control in a Hilbert space of eight dimensions (three qubits) and should be extendable up to a thousand or more dimensions (10 qubits). Among other things, these systems will allow the feasibility of quantum computing to be assessed. In fact such experiments are so difficult that it seemed likely until recently that a practically useful QC (requiring, say, 1000 qubits) was actually ruled out by considerations of experimental imprecision and the unavoidable coupling between any system and its environment. However, a further fundamental part of quantum information physics provides a solution to this impasse. This is quantum error correction (QEC). An introduction to QEC is provided. The evolution of the QC is restricted to a carefully chosen subspace of its Hilbert space. Errors are almost certain to cause a departure from this subspace. QEC provides a means to detect and undo such departures without upsetting the quantum computation. This achieves the apparently impossible, since the computation preserves quantum coherence even though during its course all the qubits in the computer will have relaxed spontaneously many times. The review concludes with an outline of the main features of quantum information physics and avenues for future research.

arXiv:quant-ph/9708022•Reports on Progress in Physics•Feb 1, 1998•1,471 citations

Philosophy of Quantum Information Science

Kervalishvili P.J.

Nowadays quantum information science is in a state of theoretic completeness; much is invested to research quality physical solution for quantum computer and applications, so the field is led by physicists and information science and technology professionals. This field proved its potential and many (including us) believe it is in the right direction to go. In this paper we'll try to present and analyze the philosophy and nature of quantum information science and discuss hot topics around them. Although there is plenty of space for discussion around this field, we will concentrate on some important issues, such as quantum communication, algorithms and cryptography. Communication promises to be one of the directions where huge breakthroughs will be observed (entanglement as communication), algorithms have already shown exponential advantage (Shor's factoring) over classical counterparts and different paradigm of information processing. Cryptography seems to utilize general achievements in quantum information science and make encryption protocols very secure. Quantum computation can be understood as a generalization of classical computation: The possible states of a quantum computer are superpositions of bit strings, where the tensor factor is called a quantum bit or qubit. To evaluate the computational complexity of an algorithm, either classical or quantum, it is necessary to specify a set of elementary operations, the number of which used during the computation quantities the complexity. If we allow arbitrary permutations classically, or arbitrary unitary transformations quantum mechanically, any state can be reached from any other state in a single step. The general kind of quantum computer should be programmed to perform distinctively quantum operations such as generating two bits in a superposition state. An appropriate measurement on the final superposed state of the computer produces a probabilistic behavior of the output, and because of this quantum parallelization does not reduce the average time required for parallelizable computation completion. The development of quantum computing science and technology as well as quantum computers as thinking machines is very dependent on different achievements of modern research in fundamental and applied physics as well as novel mathematical methods and tools.

NATO science for peace and security series. Sub-series E, Human and societal dynamics•Jan 1, 2012•2 citations

Quantum computation

This chapter introduces the basic principles of quantum computation. We shall adhere to the quantum circuit model of computation, with which it is easy to work and which is close to physical implementations. We shall not discuss the more abstract quantum Turing machine model, which, however, has been shown to be equivalent to the circuit model. The elementary unit of quantum information and the basic building block of quantum computation is the qubit, a two-level quantum system that can be prepared, manipulated and measured in a controlled way. A quantum computer can be seen as a collection of n qubits and therefore its wave function resides in a 2 n -dimensional complex Hilbert space. As far as coupling to the environment may be neglected, its evolution in time is unitary and governed by the Schrödinger equation. A quantum computation is composed of three basic steps: preparation of the input state, implementation of the desired unitary transformation acting on this state and measurement of the output state. The output of the measurement process is inherently probabilistic and the probabilities of the different possible outputs are set by the basic postulates of quantum mechanics. Therefore, in a quantum algorithm we must, in general, repeat several times the algorithm to obtain the correct solution of our problem with probability as close to one as desired. In this sense, quantum algorithms are analogous to classical probabilistic algorithms. However, the superposition principle and quantum entanglement open up new possibilities for computation. Quantum computers are potentially more powerful than classical (deterministic or probabilistic) computers due to quantum interference and entanglement. We show that, analogously to classical computation, there exists a small set of gates that are universal, that is, any unitary transformation can be decomposed into a sequence of these gates. We then discuss the implementation of the basic Boolean functions and arithmetic operations on a quantum computer.

WORLD SCIENTIFIC eBooks•Dec 1, 2018•0 citations

Introduction to Quantum Computing

Walid E. Gomaa

This presentation provides a comprehensive overview of the foundational principles of quantum computation. It begins by contrasting classical and quantum information, highlighting how quantum bits (qubits) leverage superposition, entanglement, and interference to process information in ways that surpass classical limits. The document explains the four postulates of quantum mechanics: state space (qubits as unit vectors in a Hilbert space), time evolution (via unitary operators), measurement (probabilistic collapse of the state), and composite systems (tensor products of subsystems). Key concepts such as the Bloch sphere representation, quantum gates (e.g., Hadamard, CNOT, Pauli gates), and quantum circuits are discussed, illustrating how quantum operations manipulate qubit states. The presentation also covers quantum evolution, the gate model for computation, and the universality of certain gate sets, emphasizing the potential for quantum parallelism and the transformative impact of quantum computing on fields like cryptography and optimization.

•Nov 11, 2025•0 citations

A State-of-the-art Review on Quantum Information Computing

R. Ku. Jena, Prabhat Mahanti

The subject of quantum computing brings ideas from classical information theory, computer science, and quantum physics. Quantum mechanics provide new computational paradigms that had not been imagined prior to the 1980's and whose power was not fully appreciated until the mid 1990's.This review aims to succinctly summarize not just quantum computing, but the whole subject of quantum information theory.

International Journal of Engineering•May 31, 2017•2 citations

Quantum information and computation

Jeffrey Bub

This article deals with theoretical developments in the subject of quantum information and quantum computation, and includes an overview of classical information and some relevant quantum mechanics. The discussion covers topics in quantum communication, quantum cryptography, and quantum computation, and concludes by considering whether a perspective in terms of quantum information sheds new light on the conceptual problems of quantum mechanics.

arXiv:quant-ph/0512125•Dec 15, 2005•17 citations
The agenda of quantum algorithmic information theory, ordered `top-down,' is the quantum halting amplitude, followed by the quantum algorithmic information content, which in turn requires the theory of quantum computation. The fundamental atoms processed by quantum computation are the quantum bits which are dealt with in quantum information theory. The theory of quantum computation will be based upon a model of universal quantum computer whose elementary unit is a two-port interferometer capable of arbitrary U(2)U(2)U(2) transformations. Basic to all these considerations is quantum theory, in particular Hilbert space quantum mechanics.
The subject of quantum computing brings together ideas from classical information theory, computer science, and quantum physics. This review aims to summarize not just quantum computing, but the whole subject of quantum information theory. Information can be identified as the most general thing which must propagate from a cause to an effect. It therefore has a fundamentally important role in the science of physics. However, the mathematical treatment of information, especially information processing, is quite recent, dating from the mid-20th century. This has meant that the full significance of information as a basic concept in physics is only now being discovered. This is especially true in quantum mechanics. The theory of quantum information and computing puts this significance on a firm footing, and has led to some profound and exciting new insights into the natural world. Among these are the use of quantum states to permit the secure transmission of classical information (quantum cryptography), the use of quantum entanglement to permit reliable transmission of quantum states (teleportation), the possibility of preserving quantum coherence in the presence of irreversible noise processes (quantum error correction), and the use of controlled quantum evolution for efficient computation (quantum computation). The common theme of all these insights is the use of quantum entanglement as a computational resource. It turns out that information theory and quantum mechanics fit together very well. In order to explain their relationship, this review begins with an introduction to classical information theory and computer science, including Shannon's theorem, error correcting codes, Turing machines and computational complexity. The principles of quantum mechanics are then outlined, and the Einstein, Podolsky and Rosen (EPR) experiment described. The EPR-Bell correlations, and quantum entanglement in general, form the essential new ingredient which distinguishes quantum from classical information theory and, arguably, quantum from classical physics. Basic quantum information ideas are next outlined, including qubits and data compression, quantum gates, the `no cloning' property and teleportation. Quantum cryptography is briefly sketched. The universal quantum computer (QC) is described, based on the Church-Turing principle and a network model of computation. Algorithms for such a computer are discussed, especially those for finding the period of a function, and searching a random list. Such algorithms prove that a QC of sufficiently precise construction is not only fundamentally different from any computer which can only manipulate classical information, but can compute a small class of functions with greater efficiency. This implies that some important computational tasks are impossible for any device apart from a QC. To build a universal QC is well beyond the abilities of current technology. However, the principles of quantum information physics can be tested on smaller devices. The current experimental situation is reviewed, with emphasis on the linear ion trap, high- Q optical cavities, and nuclear magnetic resonance methods. These allow coherent control in a Hilbert space of eight dimensions (three qubits) and should be extendable up to a thousand or more dimensions (10 qubits). Among other things, these systems will allow the feasibility of quantum computing to be assessed. In fact such experiments are so difficult that it seemed likely until recently that a practically useful QC (requiring, say, 1000 qubits) was actually ruled out by considerations of experimental imprecision and the unavoidable coupling between any system and its environment. However, a further fundamental part of quantum information physics provides a solution to this impasse. This is quantum error correction (QEC). An introduction to QEC is provided. The evolution of the QC is restricted to a carefully chosen subspace of its Hilbert space. Errors are almost certain to cause a departure from this subspace. QEC provides a means to detect and undo such departures without upsetting the quantum computation. This achieves the apparently impossible, since the computation preserves quantum coherence even though during its course all the qubits in the computer will have relaxed spontaneously many times. The review concludes with an outline of the main features of quantum information physics and avenues for future research.
Nowadays quantum information science is in a state of theoretic completeness; much is invested to research quality physical solution for quantum computer and applications, so the field is led by physicists and information science and technology professionals. This field proved its potential and many (including us) believe it is in the right direction to go. In this paper we'll try to present and analyze the philosophy and nature of quantum information science and discuss hot topics around them. Although there is plenty of space for discussion around this field, we will concentrate on some important issues, such as quantum communication, algorithms and cryptography. Communication promises to be one of the directions where huge breakthroughs will be observed (entanglement as communication), algorithms have already shown exponential advantage (Shor's factoring) over classical counterparts and different paradigm of information processing. Cryptography seems to utilize general achievements in quantum information science and make encryption protocols very secure. Quantum computation can be understood as a generalization of classical computation: The possible states of a quantum computer are superpositions of bit strings, where the tensor factor is called a quantum bit or qubit. To evaluate the computational complexity of an algorithm, either classical or quantum, it is necessary to specify a set of elementary operations, the number of which used during the computation quantities the complexity. If we allow arbitrary permutations classically, or arbitrary unitary transformations quantum mechanically, any state can be reached from any other state in a single step. The general kind of quantum computer should be programmed to perform distinctively quantum operations such as generating two bits in a superposition state. An appropriate measurement on the final superposed state of the computer produces a probabilistic behavior of the output, and because of this quantum parallelization does not reduce the average time required for parallelizable computation completion. The development of quantum computing science and technology as well as quantum computers as thinking machines is very dependent on different achievements of modern research in fundamental and applied physics as well as novel mathematical methods and tools.
This chapter introduces the basic principles of quantum computation. We shall adhere to the quantum circuit model of computation, with which it is easy to work and which is close to physical implementations. We shall not discuss the more abstract quantum Turing machine model, which, however, has been shown to be equivalent to the circuit model. The elementary unit of quantum information and the basic building block of quantum computation is the qubit, a two-level quantum system that can be prepared, manipulated and measured in a controlled way. A quantum computer can be seen as a collection of n qubits and therefore its wave function resides in a 2 n -dimensional complex Hilbert space. As far as coupling to the environment may be neglected, its evolution in time is unitary and governed by the Schrödinger equation. A quantum computation is composed of three basic steps: preparation of the input state, implementation of the desired unitary transformation acting on this state and measurement of the output state. The output of the measurement process is inherently probabilistic and the probabilities of the different possible outputs are set by the basic postulates of quantum mechanics. Therefore, in a quantum algorithm we must, in general, repeat several times the algorithm to obtain the correct solution of our problem with probability as close to one as desired. In this sense, quantum algorithms are analogous to classical probabilistic algorithms. However, the superposition principle and quantum entanglement open up new possibilities for computation. Quantum computers are potentially more powerful than classical (deterministic or probabilistic) computers due to quantum interference and entanglement. We show that, analogously to classical computation, there exists a small set of gates that are universal, that is, any unitary transformation can be decomposed into a sequence of these gates. We then discuss the implementation of the basic Boolean functions and arithmetic operations on a quantum computer.
This presentation provides a comprehensive overview of the foundational principles of quantum computation. It begins by contrasting classical and quantum information, highlighting how quantum bits (qubits) leverage superposition, entanglement, and interference to process information in ways that surpass classical limits. The document explains the four postulates of quantum mechanics: state space (qubits as unit vectors in a Hilbert space), time evolution (via unitary operators), measurement (probabilistic collapse of the state), and composite systems (tensor products of subsystems). Key concepts such as the Bloch sphere representation, quantum gates (e.g., Hadamard, CNOT, Pauli gates), and quantum circuits are discussed, illustrating how quantum operations manipulate qubit states. The presentation also covers quantum evolution, the gate model for computation, and the universality of certain gate sets, emphasizing the potential for quantum parallelism and the transformative impact of quantum computing on fields like cryptography and optimization.