Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
So the question was inspired by a seminar which presented the following models of quantum computing:
Are these computational models completely equivalent to one another i.e the complexity of every problem is equivalent in all these models ?
I am asking here because the answers I got from Physicists were not very rigorous (I am a Physicist).
Now you've clarified your question, I can answer it. Assuming that the seminar was talking about universal quantum computational models (and there are universal computational models for all of these physical systems), then anything in BQP (quantum polynomial time w/ randomness) for one of these models is in BQP for all of these models. They might differ by smaller factors (e.g., since only nearby Josephson junctions can talk to each other, you might have to multiply run times by the diameter of the chip — but it won't be worse than that, and for many problems you can do much better).
There are non-universal models being considered for Rydberg atoms and for photons. The non-universal Rydberg atom models would be very good for simulating certain physical systems. This has been called analog quantum computation; you make the Rydberg atoms interact with the same dynamics as the system you're trying to simulate. Then even though you can't address Rydberg atoms individually, they still behave the same way as an interesting physical system, maybe even one that doesn't quite exist in nature. Systems like this may actually yield the first scientifically interesting results of quantum computation.
For photons, it's very hard to get two photons to interact, which means that there are proposals for building quantum computers that use photons to demonstrate quantum supremacy (i.e., that you can use quantum mechanics to solve a problem that a classical computer can't) without actually being able to use them for a universal quantum computer. It's not clear to me that these proposals will actually work in real life, because as far as I am aware, these proposals have only been proved to work in the case where the noise levels are very low (i.e., the optical components and photodetectors work almost perfectly). There are also proposals for universal quantum computation that use non-interacting photons, but these also have the problem that you need extremely good (but still finite) accuracy for all the optical components and photodetectors in your computer. You can't make universal quantum computation with linear optics, but you can do it with single photon sources, linear quantum gates, and photodetectors — photodetectors and single photon sources aren't linear in this sense.
