Quantum vs Classical Randomness

Table of Contents

1. Introduction
2. Defining Randomness
3. Classical Randomness: Pseudorandomness and Entropy
4. Quantum Randomness: Intrinsic and Fundamental
5. Sources of Classical Randomness
6. Sources of Quantum Randomness
7. Determinism in Classical Mechanics
8. Indeterminism in Quantum Mechanics
9. Random Number Generators (RNGs)
10. Pseudorandom Number Generators (PRNGs)
11. Quantum Random Number Generators (QRNGs)
12. Bell’s Theorem and True Randomness
13. Quantum Entanglement and Random Correlations
14. Measurement and Wavefunction Collapse
15. Quantum vs Classical RNG in Cryptography
16. Security Considerations
17. Device-Independent Randomness
18. Certified Randomness from Quantum Experiments
19. Randomness Amplification and Expansion
20. Algorithmic Randomness and Kolmogorov Complexity
21. Randomness in Computational Models
22. Role of Randomness in Algorithms
23. Randomness and Complexity Classes
24. Quantum Supremacy and Randomness Sampling
25. Conclusion

1. Introduction

Randomness is central to computation, cryptography, and the interpretation of nature itself. In classical physics, randomness often reflects ignorance or complexity. In quantum mechanics, however, randomness arises as a fundamental property of the universe.

2. Defining Randomness

Randomness implies unpredictability and lack of pattern. A truly random process produces outcomes with:

• No deterministic pattern
• Maximal entropy
• Statistical uniformity (on average)

3. Classical Randomness: Pseudorandomness and Entropy

Classical randomness is often:

• Pseudorandom: Generated by deterministic algorithms
• Based on chaotic systems, thermal noise, or complexity

Entropy measures unpredictability:
\[
H(X) = -\sum_{i} P(x_i) \log_2 P(x_i)
\]

4. Quantum Randomness: Intrinsic and Fundamental

Quantum randomness is:

• Irreducible
• Arises from measurement collapse
• Unpredictable even with full knowledge of the quantum state

5. Sources of Classical Randomness

• Coin tosses
• Thermal noise
• Chaotic dynamics
• User input entropy (mouse, keyboard, etc.)

But all can be modeled deterministically under ideal conditions.

6. Sources of Quantum Randomness

• Single-photon beam splitters
• Spin measurements
• Polarization filters
• Quantum phase noise

These rely on superposition and non-deterministic collapse.

7. Determinism in Classical Mechanics

Classical physics (e.g., Newtonian mechanics) is deterministic:

• Given initial conditions, future states are predictable
• Apparent randomness reflects limited precision or chaotic dynamics

8. Indeterminism in Quantum Mechanics

Quantum theory:

• Only probabilistically predicts outcomes
• Collapse of the wavefunction introduces true unpredictability
• No hidden variable theory (local or nonlocal) can fully restore determinism (Bell’s theorem)

9. Random Number Generators (RNGs)

Two types:

• True RNGs: Use physical phenomena
• Pseudorandom RNGs: Use deterministic algorithms (e.g., linear congruential generators)

10. Pseudorandom Number Generators (PRNGs)

• Deterministic functions with high entropy outputs
• Seeded to produce repeatable sequences
• Fast, but not truly unpredictable

Used in:

• Simulations
• Games
• Some cryptographic applications (with care)

11. Quantum Random Number Generators (QRNGs)

• Use quantum events (e.g., photon detection)
• Generate truly random bits
• Some commercial QRNGs exist (ID Quantique, QuintessenceLabs)

12. Bell’s Theorem and True Randomness

Bell’s theorem shows:

• No local hidden variables can reproduce quantum predictions
• Violations of Bell inequalities imply non-determinism in nature

13. Quantum Entanglement and Random Correlations

Entangled particles exhibit:

• Correlated outcomes
• That appear random individually
• But obey quantum correlations violating classical bounds

14. Measurement and Wavefunction Collapse

When a quantum system is measured:

• The state collapses probabilistically
• Outcome is truly random based on amplitude squared

\[
P(x_i) = |\langle x_i | \psi \rangle|^2
\]

15. Quantum vs Classical RNG in Cryptography

Quantum RNG:

• Offers unpredictable and irreproducible bits
• More resistant to side-channel attacks
• Preferred in quantum-safe and military-grade cryptography

16. Security Considerations

• PRNGs vulnerable to seed guessing
• QRNGs can fail due to hardware issues or side-channels
• Need certification and verification

17. Device-Independent Randomness

Relies on:

• Quantum correlations (e.g., Bell inequality violation)
• Without trusting internal workings of the devices
• Ensures randomness based on observed statistics alone

18. Certified Randomness from Quantum Experiments

Experiments like:

• Bell tests with loophole closure
• Randomness certified even if devices are partially untrusted
• NIST and others have explored this for high-security uses

19. Randomness Amplification and Expansion

Quantum devices can:

• Amplify weak randomness
• Expand a small random seed into many certified random bits
• Useful for random beacons and quantum-secure protocols

20. Algorithmic Randomness and Kolmogorov Complexity

A string is algorithmically random if it:

• Cannot be compressed
• Has no shorter description than itself
• Quantum processes help generate such strings

21. Randomness in Computational Models

• Randomness powers BPP, RP, ZPP
• Quantum randomness underlies BQP, QMA
• Classical derandomization uses hard functions
• Quantum randomness may be essential in some models

22. Role of Randomness in Algorithms

Used in:

• Monte Carlo methods
• Hashing and sketching
• Cryptographic key generation
• Randomized algorithms for approximation and search

Quantum algorithms exploit randomness at a deeper level (interference, measurement).

23. Randomness and Complexity Classes

• Classical: BPP ⊆ P/poly ⊆ PSPACE
• Quantum: BQP may not be in PH
• Randomness affects class separations and collapses

24. Quantum Supremacy and Randomness Sampling

Google’s Sycamore experiment used:

• Random quantum circuits
• Sampled output distribution hard for classical simulation
• Example of using quantum randomness for experimental advantage

25. Conclusion

Quantum randomness is not just more powerful—it is fundamentally different from classical randomness. While classical unpredictability often stems from ignorance, quantum randomness is built into the fabric of the universe. As quantum technology evolves, harnessing this irreducible randomness will drive innovation in cryptography, simulation, and beyond.