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? ).
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.