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/9610012

Quantum Randomness and Nondeterminism

Emanuel H. Knill

Published Oct 9, 1996• 52 citations
arXivHTMLPDF

Abstract

Does the notion of a quantum randomized or nondeterministic algorithm make sense, and if so, does quantum randomness or nondeterminism add power? Although reasonable quantum random sources do not add computational power, the discussion of quantum randomness naturally leads to several definitions of the complexity of quantum states. Unlike classical string complexity, both deterministic and nondeterministic quantum state complexities are interesting. A notion of \emph{total quantum nondeterminism} is introduced for decision problems. This notion may be a proper extension of classical nondeterminism.

DOI
10.48550/arxiv.quant-ph/9610012

Related papers

Randomness: Quantum versus classical

Andrei Yu. Khrennikov

Recent tremendous development of quantum information theory has led to a number of quantum technological projects, e.g. quantum random generators. This development had stimulated a new wave of interest in quantum foundations. One of the most intriguing problems of quantum foundations is the elaboration of a consistent and commonly accepted interpretation of a quantum state. Closely related problem is the clarification of the notion of quantum randomness and its interrelation with classical randomness. In this short review, we shall discuss basics of classical theory of randomness (which by itself is very complex and characterized by diversity of approaches) and compare it with irreducible quantum randomness. We also discuss briefly “digital philosophy”, its role in physics (classical and quantum) and its coupling to the information interpretation of quantum mechanics (QM).

arXiv:1512.08852•International Journal of Quantum Information•May 27, 2016•27 citations

The algorithmic randomness of quantum measurements

Shahbazi, Mohammad

This paper is a comment on the paper "Quantum Mechanics and Algorithmic Randomness" was written by Ulvi Yurtsever \cite{Yurtsever} and the briefly explanation of the algorithmic randomness of quantum measurements results. There are differences between the computability of probability sources, ( which means there is an algorithm that can define the way that random process or probability source generates the numbers ) and the algorithmic randomness of the sequences or strings which are produced by a source. We may have the source without a computable algorithm for that but it can produce compressible or incompressible strings. For example, so far there is no computable algorithm that can define the abstract meaning of randomness even the easiest one, Bernoulli probability distribution. Historically and philosophically there many scientist believe the existence of the algorithm for a random process is a contradiction because in their opinion, in the definition of a random variable, implicitly assumed that there is no reason for the happening of an event and we just know the probabilities. There is however no need to enter into this matter here. As in the paper mentioned, all the algorithms for simulating a random process try to pass the statistical tests and be close to the abstract meaning of it.

arXiv:1704.01573•Apr 5, 2017•0 citations

DETERMINISTIC COMPUTATIONAL COMPLEXITY OF THE QUANTUM SEPARABILITY PROBLEM

Lawrence M. Ioannou

Ever since entanglement was identified as a computational and cryptographic resource, effort has been made to find an efficient way to tell whether a given density matrix represents an unentangled, or separable, state. Essentially, this is the quantum separability problem. In Section 1, I begin with a brief introduction to separability and entanglement, and a basic formal definition of the quantum separability problem. I conclude with a summary of one-sided tests for separability, including those involving semidefinite programming. In Section 2, I treat the separability problem as a computational decision problem and motivate its approximate formulations. After a review of basic complexity-theoretic notions, I discuss the computational complexity of the separability problem. In Section 3, I give a comprehensive survey of deterministic algorithmic solutions to the (approximate) quantum separability problem. Finally, Section 4 contains a comparison of the complexities of the algorithms surveyed in Section 3. I have attempted to give a comprehensive treatment of the deterministic quantum separability problem from a computational perspective and identify relevant open problems. Features and new results include:

•Jan 1, 2006•4 citations

Very narrow quantum OBDDs and width hierarchies for classical OBDDs

Farid Mansurovich Ablayev, Aida Gainutdinova, Kamil Ravilevich Khadiev +1 more

In the paper we investigate Ordered Binary Decision Diagrams (OBDDs)–a model for computing Boolean functions. We present a series of results on the comparative complexity for several variants of OBDDmodels. • We present results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k+1. • We consider quantum and classical nondeterminism. We show that quantum nondeterminismcan bemore efficient than classical nondeterminism. In particular, an explicit function is presented that is computed by a quantum nondeterministic OBDD of constant width but any classical nondeterministic OBDD for this function needs non-constant width. • We also present new hierarchies on widths of deterministic and nondeterministic OBDDs.

Lobachevskii Journal of Mathematics•Nov 1, 2016•37 citations

Is Quantum Randomness Algorithmic Random? A Preliminary Attack

Cristian S. Calude, Michael J. Dinneen

Randomness is an essential ingredient for computation.The pitfalls of software-generated pseudo-randomness arewell-known. So, can we do it better?The obvious candidate is quantum randomness.Quantum randomness has been confirmed by theoretical andexperimental research. The first book containing a million ofquantum random digits—generated by using radioactive decayfrom electronic vacuum tubes—was published by the RANDCorporation in 1955.Is it quantum randomness provable better thenpseudo-randomness? If yes, how much better?

•Jan 1, 2005•5 citations

The Paradigm of Complex Probability and Metarelativity

Abdo Abou Jaoudé

All our work in classical probability theory is to compute probabilities. The original idea in this research work is to add new dimensions to our random experiment, which will make the work deterministic. In fact, probability theory is a nondeterministic theory by nature; that means that the outcome of the events is due to chance and luck. By adding new imaginary dimensions to the event in the real set of probabilities R, we make the work deterministic and hence a random experiment will have a certain outcome in the complex set of probabilities and total universe G = C. It is of great importance that the stochastic system, like in the real-world problems, becomes totally predictable since we will be totally knowledgeable to foretell the outcome of chaotic and random events that occur in nature like for example in statistical mechanics or in all stochastic processes. Therefore, the work that should be done is to add to the real set of probabilities R, the contributions of M which is the imaginary set of probabilities which will make the event in G = C = R + M deterministic. If this is found to be fruitful, then a new theory in statistical sciences and in science in general is elaborated and this is to understand absolutely deterministically those phenomena that used to be random phenomena in R. This paradigm was initiated and developed in my previous 25 publications and research works. Moreover, this model will be related to my Theory of Metarelativity which takes into account faster-than-light matter and energy. This is what I called ‘The Metarelativistic Complex Probability Paradigm (MCPP)’ which will be elaborated in the present book.

Book Publisher International (a part of SCIENCEDOMAIN International)•Feb 23, 2024•0 citations
Does the notion of a quantum randomized or nondeterministic algorithm make sense, and if so, does quantum randomness or nondeterminism add power? Although reasonable quantum random sources do not add computational power, the discussion of quantum randomness naturally leads to several definitions of the complexity of quantum states. Unlike classical string complexity, both deterministic and nondeterministic quantum state complexities are interesting. A notion of \emph{total quantum nondeterminism} is introduced for decision problems. This notion may be a proper extension of classical nondeterminism.
Recent tremendous development of quantum information theory has led to a number of quantum technological projects, e.g. quantum random generators. This development had stimulated a new wave of interest in quantum foundations. One of the most intriguing problems of quantum foundations is the elaboration of a consistent and commonly accepted interpretation of a quantum state. Closely related problem is the clarification of the notion of quantum randomness and its interrelation with classical randomness. In this short review, we shall discuss basics of classical theory of randomness (which by itself is very complex and characterized by diversity of approaches) and compare it with irreducible quantum randomness. We also discuss briefly “digital philosophy”, its role in physics (classical and quantum) and its coupling to the information interpretation of quantum mechanics (QM).
This paper is a comment on the paper "Quantum Mechanics and Algorithmic Randomness" was written by Ulvi Yurtsever \cite{Yurtsever} and the briefly explanation of the algorithmic randomness of quantum measurements results. There are differences between the computability of probability sources, ( which means there is an algorithm that can define the way that random process or probability source generates the numbers ) and the algorithmic randomness of the sequences or strings which are produced by a source. We may have the source without a computable algorithm for that but it can produce compressible or incompressible strings. For example, so far there is no computable algorithm that can define the abstract meaning of randomness even the easiest one, Bernoulli probability distribution. Historically and philosophically there many scientist believe the existence of the algorithm for a random process is a contradiction because in their opinion, in the definition of a random variable, implicitly assumed that there is no reason for the happening of an event and we just know the probabilities. There is however no need to enter into this matter here. As in the paper mentioned, all the algorithms for simulating a random process try to pass the statistical tests and be close to the abstract meaning of it.
Ever since entanglement was identified as a computational and cryptographic resource, effort has been made to find an efficient way to tell whether a given density matrix represents an unentangled, or separable, state. Essentially, this is the quantum separability problem. In Section 1, I begin with a brief introduction to separability and entanglement, and a basic formal definition of the quantum separability problem. I conclude with a summary of one-sided tests for separability, including those involving semidefinite programming. In Section 2, I treat the separability problem as a computational decision problem and motivate its approximate formulations. After a review of basic complexity-theoretic notions, I discuss the computational complexity of the separability problem. In Section 3, I give a comprehensive survey of deterministic algorithmic solutions to the (approximate) quantum separability problem. Finally, Section 4 contains a comparison of the complexities of the algorithms surveyed in Section 3. I have attempted to give a comprehensive treatment of the deterministic quantum separability problem from a computational perspective and identify relevant open problems. Features and new results include:
In the paper we investigate Ordered Binary Decision Diagrams (OBDDs)–a model for computing Boolean functions. We present a series of results on the comparative complexity for several variants of OBDDmodels. • We present results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k+1. • We consider quantum and classical nondeterminism. We show that quantum nondeterminismcan bemore efficient than classical nondeterminism. In particular, an explicit function is presented that is computed by a quantum nondeterministic OBDD of constant width but any classical nondeterministic OBDD for this function needs non-constant width. • We also present new hierarchies on widths of deterministic and nondeterministic OBDDs.
Randomness is an essential ingredient for computation.The pitfalls of software-generated pseudo-randomness arewell-known. So, can we do it better?The obvious candidate is quantum randomness.Quantum randomness has been confirmed by theoretical andexperimental research. The first book containing a million ofquantum random digits—generated by using radioactive decayfrom electronic vacuum tubes—was published by the RANDCorporation in 1955.Is it quantum randomness provable better thenpseudo-randomness? If yes, how much better?
All our work in classical probability theory is to compute probabilities. The original idea in this research work is to add new dimensions to our random experiment, which will make the work deterministic. In fact, probability theory is a nondeterministic theory by nature; that means that the outcome of the events is due to chance and luck. By adding new imaginary dimensions to the event in the real set of probabilities R, we make the work deterministic and hence a random experiment will have a certain outcome in the complex set of probabilities and total universe G = C. It is of great importance that the stochastic system, like in the real-world problems, becomes totally predictable since we will be totally knowledgeable to foretell the outcome of chaotic and random events that occur in nature like for example in statistical mechanics or in all stochastic processes. Therefore, the work that should be done is to add to the real set of probabilities R, the contributions of M which is the imaginary set of probabilities which will make the event in G = C = R + M deterministic. If this is found to be fruitful, then a new theory in statistical sciences and in science in general is elaborated and this is to understand absolutely deterministically those phenomena that used to be random phenomena in R. This paradigm was initiated and developed in my previous 25 publications and research works. Moreover, this model will be related to my Theory of Metarelativity which takes into account faster-than-light matter and energy. This is what I called ‘The Metarelativistic Complex Probability Paradigm (MCPP)’ which will be elaborated in the present book.