The stupidest, most technologically and resource inefficient way to multiply by two
Or: how to do multiplication on a quantum computer today
What you will read here is a bad idea. Don’t try this at home. You’ve been warned. I’ll be using a metaphorical sledgehammer to crack a hypothetical nut. I am trying to do a much, much lamer version of using a drone to change a light bulb.
What I want is quite simple — I want to calculate 2ⁿ, 2 to the power of n, for any integer n. For example, 2² = 4. That is not a particularly difficult problem. You can work it out pretty reliably by hand using techniques learned in grade school. Or, you can find a table online.
Suppose I asked my digital assistant for the answer, though. I think you will agree that this might be a bit overkill given how much energy and sophistication is necessary to make the cloud work. But, that is not enough. We want the “killing a mosquito with a bazooka” method. For that, we need to move beyond digital technology and consult a quantum computer! That’s right, and I’m going to use a goddamn quantum computer to multiply by 2.
Get Quantum
Great, so for that, we need a quantum algorithm. Let’s get a bit technical for a second. Below is an algorithm that can compute any eight consecutive powers of 2. (Why eight? Well, quantum computers are kind of small right now.) It looks like a standard electronic circuit, with wires and components and such, but it’s quantum. That means, instead of bits of information, it uses quantum bits (qubits). The first wire is a scratch qubit — it’s just there to help with the calculation. The next three are the binary expansion of n — that’s the input data. Below I have input “111”, so I am asking for 2⁸. (The answer is 256, by the way.)
Cool, cool. So, that looks pretty complicated. We’re on the right track. Now, we just need some magic techno machine to run the algorithm on. Luckily, I have access to a quantum computer. (Don’t be too impressed — you do too.) I will use one of IBM’s cloud quantum computers. In particular, I will use the quantum processor called “ibmq_16_melbourne,” which is a quantum chip made of superconducting material sitting in a laboratory device that is one hundred times colder than outer space.
I ran the circuit above on IBM’s quantum computer 1,024 times. Unfortunately, the desired outcome showed up only 8 times — that’s less than 1% accuracy. The most common answer, showing up about 1% of the time, was 160. The correct answer, recall, is 256. So… this is not good.
The quantum Rube Goldberg solution
Alright, so what gives? At the moment, quantum computers are too noisy to perform arithmetic, but that will not deter Progress™. We need to hack this. How can we get this device to calculate 2⁸? First, we need to ask what a quantum computer is really good at (today). That’s easy! So (today), a quantum computer is pretty good at one thing: making random bit strings. And, how many bit strings can n qubits generate? 2ⁿ!
I like this idea. It’s so simple. It presents a little conundrum, though. Imagine we start performing random experiments and recording outcomes with the intent of estimating the total number of possible outcomes, including those we haven’t even seen yet. Seems almost impossible, right? Well, this is the kind of statistics problem Alan Turing and teams of WWII cryptographers faced when trying to crack ciphers. And, when you stop for a moment, you realize that scientists and statisticians estimate the total number of things they haven’t actually counted all the time — the total number of species on Earth, the total number of stars in the galaxy, the total number of lies in a political speech, and so on.
The core idea in estimating totals from incomplete observations is that repeated events give you a lot of information. For example, flip a coin 10 times. Suppose you see H, H, T, H, T, H, H, T, T, T. Without making assumptions, you can’t know for sure that this coin will result in only these two possible outcomes indefinitely into the future. But, the fact that 8 of the 10 events were repeated events gives you a lot of confidence that’s the case. This can all be formalized with some fancy statistics I won’t bore you with.
So, I fired up Old Faithful (that’s what I’m calling it since “ibmq_16_melbourne” doesn’t quite roll off the tongue) and performed the following procedure:
- Select a random instruction.
- Prepare a canonical state of the device.
- Apply the randomly chosen instruction from Step 1.
- Measure the system.
- Repeat 1–4 until r repeated outcomes are seen.
- Estimate the quantum dimension to be roughly k²/(2r), where k was the number of experiments needed.
Since the quantum dimension is 2ⁿ, where n is the number of qubits used, I would have my answer.
Quantum level accuracy
For my first experiment, I used 8 qubits to calculate 2⁸. The number of repeated outcomes I was looking for was 599. This is the number that would guarantee (with 95% probability) that the answer would be within 10% of the correct value. It took 849 repetitions of the experiment to reach the desired number of 599 repetitions. The answer? 259 (within 10% error of the true value, 19 times out of 20). Not bad! That’s within 2% of the correct answer!
More repetitions are obviously better. So, I waited to see 1,116 repetitions, which took 1,372 experiments. The answer then was 257. Ooo, so close! Then I was intrigued and performed a bunch more experiments with differing numbers of sought-after repetitions. The results are below.
Now, since Old Faithful has 15 qubits, the final step was obviously to calculate 2¹⁵. Again, going for 599 repetitions (which took 6,215 experiments), the answer would be accurate within 10% (with 95% confidence). And… drumroll… 2¹⁵ ≈ 32,242. (It’s actually 32,768 as per the table above, but not too shabby!) The full set of results are below.
Is there a point to all this?
No, not really. But, maybe? I was actually surprised by how accurate it was. This procedure is obviously useless for estimating 2ⁿ. But, it might be useful for quickly estimating the dimension of quantum devices. All that is necessary is to perform completely randomized experiments and look for repeated outcomes. With 95% confidence, one can estimate any dimension within 10% error by finding 599 repetitions. It takes about square-root the actual dimension to find them all (for a fixed number of sough-after repetitions), which is the best one could hope for.
