How do we decide whether a quantum circuit can be realized physically or not ? I was wondering for physical realization of Shor's factoring algorithm using NMR ( I mean can we do it? ).


1 Answer 1


In theory, there is one easy way to decide whether a quantum circuit can be realized in principle: Can we implement a universal gate set with the system? If yes, then we can implement any circuit, if no, then we can just implement circuits with the gates we know how to implement.

So much for simple theory. The question however is much harder. First of all, we will have to worry about errors piling up and destroying our computer. So we need the theory of error correction - but the question remains the same: Can we fault tolerantly implement a universal gate set with the system? If we can, then yes, we can implement any circuit, otherwise, only the gates we know how to implement fault tolerantly.

Okay, so much for that. Now, sadly that's still not really an answer to the question of "physical realizability", it's still theory. So we have to go to the system in question and actually see whether all the gates can be implemented - and then, whether they can be implemented fault tolerantly. For most systems, this is only possible with a very small number of (logical) qubits at the moment (there are systems that can do more than NMR, I wouldn't consider it a very hot approach at the moment - then again, I'm relly not an experimentalist). Then, implementing single qubit gates is often not a big deal, multiple qubit gates, however, usually is a problem - to the point where we can't just "scale" them up to dozens or even hundreds of qubits.

To sum up: There's two sides. First, the theoretical, which is simple: Can you fault tolerantly implement the gates in the circuit? Second, the experimental, which is hard. There is really no way to say something is possible or not until everything has been checked out.

  • $\begingroup$ "multiple qubit gates, however, usually is a problem", could you explain it further? Many thanks! $\endgroup$ Sep 8, 2014 at 1:31
  • $\begingroup$ @EdenHarder: I'm not entirely sure, what would help you. I just know that the experimental fidelities for single qubit rotations are quite good (in the range of >.9, sometimes >.99), while the fidelities for a two-qubit gate (e.g. the CNOT) are generally much smaller (more in the range of >.7). There are several reasons: a) you need to control two qubits instead of one (one is hard enough), b) the qubits must not interfer in any other way, so they will be spatially separated, but you need to act on both, c) transporting qubits to bring them near to each other is a problem. $\endgroup$
    – Martin
    Sep 8, 2014 at 8:17
  • $\begingroup$ Especially c) seems to me to prevent scaling a quantum computer. Of course, there are other schemes (dissipative, measurement based, adiabatic), which may circumvent this problem. Otherwise, please note that I'm a theorist, so I don't have all up to date numbers in my head, but I could take some time and search for some references... $\endgroup$
    – Martin
    Sep 8, 2014 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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