4 ms·

What would have to happen to change the current thinking to believe that quantum computing is not possible?

hannob 10y ago
I don't think that's what most people familiar with the topic believe. It's just considered to be very hard (and some think it's so hard that it may be practically impossible for a very long time).
adrianN 10y ago
Somebody finding that quantum computers can solve NP-hard problems would be very suspicious. Other than that it would need someone to find a flaw with quantum mechanics.
- Meegul 10y ago
  It was to my understanding that some NP-complete problems - like factorization - are (theoretically) solvable in P time using quantum computing, all within (and indeed as a result of) the constraints of quantum mechanics, perhaps utilizing Shor's algorithm. And that this fact does not imply P=NP, but rather that we'd have a computer that could perform some exponential functions as if some logarithm were applied to them. I'm no expert, but at the very least I believe it's recognized that some subset of NP problems, perhaps not NP-hard, should be solvable as if they were polynomial, using quantum computers. That said, my knowledge of this subject starts and ends with things I've read on the internet, so I could be mistaken. Either way, this[1] was a very interesting introduction to some of the implications/concepts that are involved with this. 1: http://www.scottaaronson.com/papers/philos.pdf http://www.scottaaronson.com/papers/philos.pdf
  - Ar-Curunir 10y ago
    Factorisation is very, very, very unlikely to be NP-complete. P is a separate class from the class of problems considered efficiently solvable; BQP is the class of problems that are efficiently solved by quantum computers, and it is believed that BQP is strictly larger than P.
    - Meegul 10y ago
      Ah alright. Looks like I have some more reading to do this morning.
- kleiba 10y ago
  Somebody finding that quantum computers can solve NP-hard problems [efficiently] would be very suspicious. The missing word here is "efficiently": all problems in NP are solvable.
marcosdumay 10y ago
Are you aware that there are many quantum computers working in labs around the world, right?
- basicplus2 10y ago
  My question does not mean I don't believe in quantum computers

I don't think that's what most people familiar with the topic believe. It's just considered to be very hard (and some think it's so hard that it may be practically impossible for a very long time).

adrianN 10y ago

Somebody finding that quantum computers can solve NP-hard problems would be very suspicious. Other than that it would need someone to find a flaw with quantum mechanics.

Meegul 10y ago
It was to my understanding that some NP-complete problems - like factorization - are (theoretically) solvable in P time using quantum computing, all within (and indeed as a result of) the constraints of quantum mechanics, perhaps utilizing Shor's algorithm. And that this fact does not imply P=NP, but rather that we'd have a computer that could perform some exponential functions as if some logarithm were applied to them. I'm no expert, but at the very least I believe it's recognized that some subset of NP problems, perhaps not NP-hard, should be solvable as if they were polynomial, using quantum computers. That said, my knowledge of this subject starts and ends with things I've read on the internet, so I could be mistaken. Either way, this[1] was a very interesting introduction to some of the implications/concepts that are involved with this. 1: http://www.scottaaronson.com/papers/philos.pdf http://www.scottaaronson.com/papers/philos.pdf
- Ar-Curunir 10y ago
  Factorisation is very, very, very unlikely to be NP-complete. P is a separate class from the class of problems considered efficiently solvable; BQP is the class of problems that are efficiently solved by quantum computers, and it is believed that BQP is strictly larger than P.
  - Meegul 10y ago
    Ah alright. Looks like I have some more reading to do this morning.
kleiba 10y ago
Somebody finding that quantum computers can solve NP-hard problems [efficiently] would be very suspicious. The missing word here is "efficiently": all problems in NP are solvable.

marcosdumay 10y ago

Are you aware that there are many quantum computers working in labs around the world, right?

basicplus2 10y ago
My question does not mean I don't believe in quantum computers