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

Science

Randomness in Quantum Computation

Juan Pablo Paz

Published Dec 18, 2003• 2 citations
Publisher

Abstract

In ordinary computers, it is sometimes useful to flip a coin. Non?deterministic algorithms (those programs that involve making such random choices at some steps) can be far more efficient in finding solutions to a variety of problems
DOI
10.1126/science.1092977

Related papers

Quantum Complexity

Stefan Heinrich

A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.

Cambridge University Press eBooks•Mar 25, 2004•2 citations

Quantum Coin Flipping

Johnathan Miller Baird, Joshua D. Qualls

Quantum computing (QC) is a radically new approach to computation. Classical computing is based on the idea of bits: strings of 1's and 0's on which we do arithmetic operations. QC, however, is based on quantum bits, qubits, and new physical operations. Despite the complexity of QC, we contend that it is an appropriate and useful topic for undergraduate physics students. In this talk, we present our results from three small QC projects relating to flipping coins. In the first, we investigate the results of a secret coin flip and use QC to guess whether the coin landed on heads or tails. In the second, we determine whether a given coin is fair or unfair using only a single qubit ( instead of multiple bits). In the third, we explore how quantum communication can alleviate dishonest player biases in coin flipping cryptographic primitives.

•Jan 1, 2019•11 citations

‘Quantum supremacy’ revisited: low-complexity, deterministic solutions of the original Deutsch–Jozsa problem in classical physical systems

László B. Kish

The original Deutsch–Jozsa (oDJ) problem is for an oracle (realized here as a database) of size N , where, according to their claim, the deterministic solution of the problem on a classical Turing computer requires O( N ) computational complexity. They produced the famous Deutsch–Jozsa quantum algorithm that offered an exponential speed-up over the classical computer, namely O[log( N )] complexity for the solution in a quantum computer. In this paper, the problem is implemented on an instantaneous noise-based logic processor. It is shown that, similarly to the quantum algorithm, the oDJ problem can deterministically be solved with O[log( N )] complexity. The implication is that by adding a truly random coin to a classical Turing machine and using this classical-physical algorithm can also speed up the deterministic solution of the Deutsch–Jozsa problem exponentially, similarly to the quantum algorithm. Then it is realized that the same database and the solution of the Deutsch–Jozsa problem can also be realized by using an identical algorithmic structure in a simpler way, even without noise/random coin. The only lost function in this new system, as compared with noise-based logic, is the ability to do generic parallel logic operations over the whole database. As the latter feature is not needed for the oDJ problem, it is concluded that the problem can be solved on a classical computer with O[log( N )] complexity even without a random coin. Therefore, while the oDJ algorithm is a historically important step in the developments of quantum computers, it is insufficient to prove quantum supremacy. Note, there is also a simplified Deutsch–Jozsa problem proposed later, which is more popular in the field; however, it is irrelevant for the present paper.

arXiv:2210.07088•Royal Society Open Science•Feb 28, 2023•15 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

Quantum computing in Fortran

Adriaan Albert Markus

Quantum computing is the delicate art of using a quantum-mechanical system to perform some kind of computation. Such a system differs in a number of significant ways from ordinary computers:• A quantum computer actually does a lot of computations at the same time, each solution is represented by a particular possible state. This is inherent to the physical properties of such a system.• Unless you are sure that you have reached the final (unique) solution, you can not "look" at the "values" of the variables in the computer program that is being run: since all solutions are possible at the same time, observing the values will influence the system and put it into one particular, but otherwise arbitrary, state.• All computations must be reversible, that is, a statement like "a = 5" can only appear in the initialization phase of a program, because the previous value will be lost. On the other hand, a statement like "a = a + 5" is reversible, since you can retrieve the original value.The properties of such a quantum computer make it possible to devise very efficient algorithms. One such algorithm, described by L. Grover (see the references), is searching in an unsorted array of items. With ordinary computers this can not be done more efficiently than in O (N) steps (an exhaustive search: each item is examined in the worst case), with this quantum algorithm, however, the number of steps needed is O (N 1/2 ).Devising quantum algorithms requires a thorough understanding of quantum mechanics, there is no doubt about that. Another question is: do we need quantum computers and special programming languages to program (or perhaps emulate) these algorithms? This article tries to show that, at least for the quantum search algorithm, a classical programming language like Fortran is quite fit (yes, the pun is fortunate).

ACM SIGPLAN Fortran Forum•Aug 1, 2004•2 citations

Quantum Random Numbers: A Survey on Sources, Numerical Evidence, and Applications in Security and Computing

Sebastian Raubitzek, Stefan Mühlhauser, Kevin Mallinger

Random numbers are used to generate cryptographic keys, to run Monte Carlo simulations, and to train and sample machine learning models. Most software obtains them from deterministic pseudo-random number generators, which have good statistical properties but are predictable once their internal state is known. Quantum random number generators take their output from measurements on quantum systems, whose outcomes are not fixed by any prior state of the device. This article introduces the types of random number generators, reviews studies that compare quantum and pseudo-random numbers in numerical experiments, and lists the sources of randomness available in current computing systems. It then describes applications of quantum randomness in security, hashing, software, artificial intelligence, and public randomness. The quality of encryption is treated as depending on three factors: the algorithm, its implementation, and the randomness of keys and other security-relevant values. We give arguments for which applications benefit from quantum randomness, name further areas in which it could be tested, and outline next steps.

Entropy•Nov 10, 2026•0 citations
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
Quantum computing (QC) is a radically new approach to computation. Classical computing is based on the idea of bits: strings of 1's and 0's on which we do arithmetic operations. QC, however, is based on quantum bits, qubits, and new physical operations. Despite the complexity of QC, we contend that it is an appropriate and useful topic for undergraduate physics students. In this talk, we present our results from three small QC projects relating to flipping coins. In the first, we investigate the results of a secret coin flip and use QC to guess whether the coin landed on heads or tails. In the second, we determine whether a given coin is fair or unfair using only a single qubit ( instead of multiple bits). In the third, we explore how quantum communication can alleviate dishonest player biases in coin flipping cryptographic primitives.
The original Deutsch–Jozsa (oDJ) problem is for an oracle (realized here as a database) of size N , where, according to their claim, the deterministic solution of the problem on a classical Turing computer requires O( N ) computational complexity. They produced the famous Deutsch–Jozsa quantum algorithm that offered an exponential speed-up over the classical computer, namely O[log( N )] complexity for the solution in a quantum computer. In this paper, the problem is implemented on an instantaneous noise-based logic processor. It is shown that, similarly to the quantum algorithm, the oDJ problem can deterministically be solved with O[log( N )] complexity. The implication is that by adding a truly random coin to a classical Turing machine and using this classical-physical algorithm can also speed up the deterministic solution of the Deutsch–Jozsa problem exponentially, similarly to the quantum algorithm. Then it is realized that the same database and the solution of the Deutsch–Jozsa problem can also be realized by using an identical algorithmic structure in a simpler way, even without noise/random coin. The only lost function in this new system, as compared with noise-based logic, is the ability to do generic parallel logic operations over the whole database. As the latter feature is not needed for the oDJ problem, it is concluded that the problem can be solved on a classical computer with O[log( N )] complexity even without a random coin. Therefore, while the oDJ algorithm is a historically important step in the developments of quantum computers, it is insufficient to prove quantum supremacy. Note, there is also a simplified Deutsch–Jozsa problem proposed later, which is more popular in the field; however, it is irrelevant for the present paper.
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?
Quantum computing is the delicate art of using a quantum-mechanical system to perform some kind of computation. Such a system differs in a number of significant ways from ordinary computers:• A quantum computer actually does a lot of computations at the same time, each solution is represented by a particular possible state. This is inherent to the physical properties of such a system.• Unless you are sure that you have reached the final (unique) solution, you can not "look" at the "values" of the variables in the computer program that is being run: since all solutions are possible at the same time, observing the values will influence the system and put it into one particular, but otherwise arbitrary, state.• All computations must be reversible, that is, a statement like "a = 5" can only appear in the initialization phase of a program, because the previous value will be lost. On the other hand, a statement like "a = a + 5" is reversible, since you can retrieve the original value.The properties of such a quantum computer make it possible to devise very efficient algorithms. One such algorithm, described by L. Grover (see the references), is searching in an unsorted array of items. With ordinary computers this can not be done more efficiently than in O (N) steps (an exhaustive search: each item is examined in the worst case), with this quantum algorithm, however, the number of steps needed is O (N 1/2 ).Devising quantum algorithms requires a thorough understanding of quantum mechanics, there is no doubt about that. Another question is: do we need quantum computers and special programming languages to program (or perhaps emulate) these algorithms? This article tries to show that, at least for the quantum search algorithm, a classical programming language like Fortran is quite fit (yes, the pun is fortunate).
Random numbers are used to generate cryptographic keys, to run Monte Carlo simulations, and to train and sample machine learning models. Most software obtains them from deterministic pseudo-random number generators, which have good statistical properties but are predictable once their internal state is known. Quantum random number generators take their output from measurements on quantum systems, whose outcomes are not fixed by any prior state of the device. This article introduces the types of random number generators, reviews studies that compare quantum and pseudo-random numbers in numerical experiments, and lists the sources of randomness available in current computing systems. It then describes applications of quantum randomness in security, hashing, software, artificial intelligence, and public randomness. The quality of encryption is treated as depending on three factors: the algorithm, its implementation, and the randomness of keys and other security-relevant values. We give arguments for which applications benefit from quantum randomness, name further areas in which it could be tested, and outline next steps.