Finally got around to learning quantum computation. Here’s some notes on the absolute basics, please correct if I’m wrong.
The state of an N-qubit quantum computer is an amplitude distribution on all possible N-bit strings. Let’s define amplitudes as real numbers that (unlike probabilities) can range from −1 to 1 and whose squares sum to 1. So an amplitude distribution is a unit vector in a real 2^N-dimensional space.
(Some people will say amplitudes should be complex numbers, but I read somewhere that using real amplitudes still gives us all the power of quantum computation, and is easier for me to think about.)
Here’s some ways to write amplitude distributions:
|0> is a distribution where the bit string “0” has amplitude 1, and everything else (i.e. the bit string “1″) has amplitude 0.
( |0> + |1> ) / √2 is a distribution where bit strings “0” and “1″ have amplitude 1/√2 each.
|01> is a distribution where the bit string “01” has amplitude 1. We can factor it as |0> ⊗ |1>. The operation ⊗ makes a joint distribution from two independent ones. (It’s called tensor product, but you don’t need to learn it unless you want to.)
( |00> + |01> ) / √2 is a distribution where bit strings “00” and “01″ have amplitude 1/√2 each. It can be factored as |0> ⊗ ( |0> + |1>) / √2, so the two qubits are independent.
( |00> + |11> ) / √2 is a distribution that can’t be factored, so the two qubits are dependent, or “entangled”.
Here’s the operations that a quantum computer can do in constant time:
Initialize the qubits with given values.
Apply a simple logical operation across all bit strings. For example, if you have the distribution ( |00> + |11> ) / √2 and want to flip the first bit in each string, that gives ( |10> + |01> ) / √2. The operation has to be reversible, e.g. XOR is ok but AND isn’t.
Rotate a single qubit by an angle. For example, rotating |0> by 45 degrees becomes ( |0> + |1> ) / √2. To deal with entangled distributions, you need to factor and rotate each component individually, e.g. rotating the first qubit in ( |00> + |11> ) / √2 by 45 degrees will give ( |00> + |10> + |11> - |01> ) / 2. Sometimes things will cancel out, e.g. rotating ( |0> + |1> ) / √2 by 45 degrees will give |1>. This clever use of rotation to reduce randomness is basically the reason for quantum computation’s extra power.
Sample a bit string from the distribution, with probabilities according to squared amplitudes. We can only do this once.
Strong upvote for the very clear explanation of the basics. I would definitely read any further posts elaborating on this—for example, if you explained some of the simple quantum gates and maybe an algorithm or two that asymptotically outperforms its classical analog.
It is interesting if quantum computers’ computations could be used as evidence against “we are in simulation on a classical computer”. Quantum supremacy can’t be modeled on a classical computer. But the simulators could easily overcome the obstacle by using quantum computers too. However, it creates some limits about the nature of their hardware.
One could imagine an experiment to test if we are in a classical simulation by performing a very complex computation of a quantum computer. But this could also end our world.
Hey, I’ve got a sudden question for you.
Probability distribution on a set of binary variables is to a quantum state
as ??? is to a unitary linear operator.
What should ??? be replaced with?
Here’s why I have this question. Somehow I was thinking about Normalizing flows, which are invertible functions which, when applied to a sample from an N-dimensional probability distribution, transform it into a sample from another N-dimensional probability distribution. And then I thought: isn’t this similar to how quantum operator is always unitary? Maybe then I can combine encoding an image as a pure state (like in Stoudenmire 2016 - Supervised learning with quantum-inspired tensor networks with representing quantum operators as tensor networks to get a quantum-inspired generative model similar to normalizing flows.
(1/?)
Finally got around to learning quantum computation. Here’s some notes on the absolute basics, please correct if I’m wrong.
The state of an N-qubit quantum computer is an amplitude distribution on all possible N-bit strings. Let’s define amplitudes as real numbers that (unlike probabilities) can range from −1 to 1 and whose squares sum to 1. So an amplitude distribution is a unit vector in a real 2^N-dimensional space.
(Some people will say amplitudes should be complex numbers, but I read somewhere that using real amplitudes still gives us all the power of quantum computation, and is easier for me to think about.)
Here’s some ways to write amplitude distributions:
|0> is a distribution where the bit string “0” has amplitude 1, and everything else (i.e. the bit string “1″) has amplitude 0.
( |0> + |1> ) / √2 is a distribution where bit strings “0” and “1″ have amplitude 1/√2 each.
|01> is a distribution where the bit string “01” has amplitude 1. We can factor it as |0> ⊗ |1>. The operation ⊗ makes a joint distribution from two independent ones. (It’s called tensor product, but you don’t need to learn it unless you want to.)
( |00> + |01> ) / √2 is a distribution where bit strings “00” and “01″ have amplitude 1/√2 each. It can be factored as |0> ⊗ ( |0> + |1>) / √2, so the two qubits are independent.
( |00> + |11> ) / √2 is a distribution that can’t be factored, so the two qubits are dependent, or “entangled”.
Here’s the operations that a quantum computer can do in constant time:
Initialize the qubits with given values.
Apply a simple logical operation across all bit strings. For example, if you have the distribution ( |00> + |11> ) / √2 and want to flip the first bit in each string, that gives ( |10> + |01> ) / √2. The operation has to be reversible, e.g. XOR is ok but AND isn’t.
Rotate a single qubit by an angle. For example, rotating |0> by 45 degrees becomes ( |0> + |1> ) / √2. To deal with entangled distributions, you need to factor and rotate each component individually, e.g. rotating the first qubit in ( |00> + |11> ) / √2 by 45 degrees will give ( |00> + |10> + |11> - |01> ) / 2. Sometimes things will cancel out, e.g. rotating ( |0> + |1> ) / √2 by 45 degrees will give |1>. This clever use of rotation to reduce randomness is basically the reason for quantum computation’s extra power.
Sample a bit string from the distribution, with probabilities according to squared amplitudes. We can only do this once.
That set of operations is enough for everything.
Strong upvote for the very clear explanation of the basics. I would definitely read any further posts elaborating on this—for example, if you explained some of the simple quantum gates and maybe an algorithm or two that asymptotically outperforms its classical analog.
Oh wait. Here:
Are the signs of |01> and |10> reversed by mistake? I would think the components would rotate as follows:
|00> goes to (|00> + |10>) / √2
|11> goes to (|11> - |01>) / √2
Whoops. Thanks!
It is interesting if quantum computers’ computations could be used as evidence against “we are in simulation on a classical computer”. Quantum supremacy can’t be modeled on a classical computer. But the simulators could easily overcome the obstacle by using quantum computers too. However, it creates some limits about the nature of their hardware.
One could imagine an experiment to test if we are in a classical simulation by performing a very complex computation of a quantum computer. But this could also end our world.
Would it be correct to say that (2) and (3) can be replaced with just “apply any linear operator”?
Also, what advantages does working with amplitudes have compared to working with probabilities? Why don’t we just use probability theory?
Any unitary linear operator (to make sure squared amplitudes still sum to 1). To your second question, I’ll post a toplevel comment.
Hey, I’ve got a sudden question for you. Probability distribution on a set of binary variables is to a quantum state as ??? is to a unitary linear operator.
What should ??? be replaced with?
Here’s why I have this question. Somehow I was thinking about Normalizing flows, which are invertible functions which, when applied to a sample from an N-dimensional probability distribution, transform it into a sample from another N-dimensional probability distribution. And then I thought: isn’t this similar to how quantum operator is always unitary? Maybe then I can combine encoding an image as a pure state (like in Stoudenmire 2016 - Supervised learning with quantum-inspired tensor networks with representing quantum operators as tensor networks to get a quantum-inspired generative model similar to normalizing flows.
Maybe stochastic matrix?