# Multiple random coin flips

Suppose that in my circuit I have to generate multiple, say n, random coin flips. For example, this coin flips could be used to activate n CNOTs half of the time.

The trivial solution could be to use n different qubits and Hadamard them. However, this gets really huge when n is large.

Is there any better way? By better I mean using a small (fixed??) number of qubits and only a few simple quantum gates.

## 1 Answer

This depends on exactly what you want to do with the outcome. If you want to use the $$n$$ outcomes simultaneously, then you need $$n$$ separate coins. Alternatively, you are happy to implement them all in sequence (one after the other), then what you could do is:

• start with qubit in the state $$|0\rangle$$
• apply Hadamard to it
• measure it in the 0/1 basis
• drive the controlled-not off it
• apply Hadamard to it
• measure it in the 0/1 basis
• drive the controlled-not off it
• apply Hadamard to it
• ...

which only requires the one qubit. This is assuming that when you talk about coin flips, you really mean the classical version (which is why I have the measurements in there). If the coherence were important to you, it might be a different matter.

• Thanks. I've thought about it, implementing it in a slightly different way (swapping states 3 and 4). However, I was thinking if this was the only actual one or there are more clever algorithm involving phase shifts or something like that, avoiding the measurement at all. Dec 11 '18 at 10:16
• that probably depends on how you're using the output. I suspect that unless you do the measurement at each step, there will be detectable differences from independent random coins, it just depends on whether what you do with it later would be sensitive to those differences or not. Dec 11 '18 at 11:56
• If you try to re-use the qubit without measuring, you're probably going to accidentally perform a quantum walk instead of a random walk. Dec 11 '18 at 20:39
• @CraigGidney thanks for the article, pretty useful. Dec 12 '18 at 9:49