So the question was inspired by a seminar which presented the following models of quantum computing:

  • Quantum Computing with Photons
  • Quantum Computing with Rydberg atoms
  • Quantum Computing with trapped ions
  • Quantum Computing with Josephson Junction

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

  • $\begingroup$ Can you link the seminar? $\endgroup$
    – Sagnik
    Commented Nov 24, 2020 at 15:42
  • $\begingroup$ facebook.com/spiechapter.unitn.7 $\endgroup$
    – SagarM
    Commented Nov 24, 2020 at 15:45
  • 3
    $\begingroup$ What were the details of Quantum Computing with Photons? How did they make the photons interact (or did they interact only through being bosons)? Was it all linear optics, or were there some non-linear optical elements? Did they need single photon sources, or were the light sources lasers? Did they mention photodetectors, and were there any efficiency requirements for them? $\endgroup$ Commented Nov 25, 2020 at 2:31
  • 3
    $\begingroup$ Were the Rydberg atoms in a linear array, in a two-dimensional array, or in some other configuration? Were the Rydberg atoms individually addressable, or did the quantum computer simply apply the same constructed Hamiltonian to all the Rydberg atoms? Was the Hamiltonian uniform, or was it stronger in some places than others? $\endgroup$ Commented Nov 25, 2020 at 2:36
  • $\begingroup$ I don't understand details of what was presented, but I would be happy to know only that "Can the complexity of a problem differ greatly in different quantum computational models ?" i.e it's in P in one and in EXPTIME in other in a very similar fashion as presented in the answer to this question : cstheory.stackexchange.com/questions/23783/… $\endgroup$
    – SagarM
    Commented Nov 25, 2020 at 13:36

1 Answer 1


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.


Your Answer

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

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