1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – tigerjack89 Dec 11 '18 at 10:16
  • $\begingroup$ 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. $\endgroup$ – DaftWullie Dec 11 '18 at 11:56
  • 1
    $\begingroup$ 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. $\endgroup$ – Craig Gidney Dec 11 '18 at 20:39
  • $\begingroup$ @CraigGidney thanks for the article, pretty useful. $\endgroup$ – tigerjack89 Dec 12 '18 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.