https://www.youtube.com/watch?v=1ud6LNtX014
https://www.stochasticnetwork.com//
It is often claimed that the bits in a quantum computer have no values until you look at them, then they "collapse" into a definite state. However, such a belief is not required by the mathematics but is a personal choice, as it is possible to represent any arbitrary quantum circuit as a Markov chain.
In classical probabilistic computing, you represent the bits using a probability vector we can call p⃗, which holds the current probability distribution for the bits, and we represent logic gates in terms of stochastic perbutations given by the Markov matrix Γ.
The evolution rule then just becomes:
- p⃗'=Γp⃗
The mathematical description does not track the definite values of the bits, but those are indeed believed to exist, because you can create a simulation whereby you start with well-defined values for the bits and stochastically perturb them to new definite values based on the probabilities given by Γ, and the statistics on such a system will reproduce p⃗ at every time step.
Quantum computers use a different evolution rule:
- ψ'=Uψ
Where U is a unitary matrix and ψ is the wavefunction. The main difference is that U and ψ are complex-valued, so it is not obvious what they physically represent or how this could relate to a Markov chain in any way.
Complex numbers aren't magic. They just represent a system with two degrees of freedom. That means we can get rid of the complex numbers by decomposing them into two separate real-valued vectors. Specifically, we can perform a polar decomposition on ψ.
- p⃗=|ψ|²
- φ⃗=arg(ψ)
Notice that, if we perform a polar decomposition on ψ, then one of the two degrees of freedom is quite literally a probability vector. Something interesting happens if we write an update rule for this p⃗ directly so we can evolve p⃗ directly without having to constantly convert back and forth between p⃗ and ψ.
We get this evolution rule:
- p⃗'=Γp⃗+q⃗ where Γ=|U|²
We get what looks like a classical Markov process but with a non-linear correction term called q⃗, which accounts for interference effects. The equation for computing q⃗ has a dependence upon φ⃗, and so φ⃗ acts like a memory effect which can cause the same logic gate to give different behavior if the value of φ⃗ is different at that time.
A prime example is the Hadamard gate. Apply it once then p⃗=[0.5; 0.5]. Apply it twice then the bit deterministically goes back to where it came from. That means it needs a way to "remember" where it came from, and that "memory" is stored in φ⃗. If you apply the Hadamard gate when the bit value begins with a value of 0, then φ⃗=[0; 0]. If you apply it when the bit value begins with 1, then φ⃗=[0; π].
Rather than using φ⃗ to compute q⃗, which is a correction term for Γp⃗, we can instead use φ⃗ to correct Γ, such that the same logic gate can give us a different Γ if the state of φ⃗ is different at a given time. If we do that, then we can represent each logic gate in terms of these corrected Γ, and thus fit the entire system to the evolution rule given by: p⃗'=Γp⃗.
There would be no need to correct Γp⃗ with q⃗ because we already built that correction into our corrected Γ. The method to correct Γ also turns out to be trivially simple, you just apply an algorithm called iterative proportional fitting which comes from optimal transport, which will adjust the initial Γ=|U|² as little as possible such that Γp⃗ maps you to the correct p⃗'.
That means we can fit the entire circuit to a Markov chain where the qubits have definite bit values at all times and each logic gate represents a stochastic pertubation upon the bits that merely permutes them randomly to a new definite configuration, and if you collect statistics on that stochastic process at every step, it will always match the Born rule distribution at that step.