As far as I know, quantum computers are able to solve only some of the NP-Problems in polynomial time, using the Grovers algorithm. I read that if one manages to create a reduction of Grovers algorithm on one of the NP-Complete algorithms, for example 3SAT, then it will be a huge milestone, since we could solve all other NP-Complete problems. I also read that current quantum computers lack error-correcting qubits to create a reduction of Grovers algorithm on 3SAT. What would be a sufficient amount of qubits to solve such problem and what amount do we currently have?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ I don't think these questions are duplicates. Quantum computers being able to solve NP-complete problems does not seem to currently imply in any way P = or != NP (which is a question about classical computers), related: cs.stackexchange.com/questions/73864/… $\endgroup$– Ciro Santilli OurBigBook.comAug 23, 2021 at 10:12
-
$\begingroup$ Being able to build two-way quantum computers: fixing both initial state with state preparation, but also some final states with its CPT symmetry analog (e.g. pull-push, negative-positive radiation pressure, stimulated emission-absorption), in theory would allow to solve NP-complete problems: techrxiv.org/articles/preprint/… $\endgroup$– Jarek DudaAug 25 at 3:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
I also read that current quantum computers lack error-correcting qubits to create a reduction of Grovers algorithm on 3SAT. What would be a sufficient amount of qubits to solve such problem and what amount do we currently have?
First and foremost, complexity-theory wise, it doesn't matter how many qubits a current or future system has - from a complexity classes point of view, a quantum computer 'is' a quantum computer, and a classical computer 'is' a classical computer. The complexity classes are just a distinction in how, for different problems, the total number of steps that you have to take to solve the problem scales with the input of the problem. Any problem for which the (classical) algorithm scales polynomial with the input parameter is in P, any problem for which the (quantum) algorithm scales polynomial with the input parameter is in BQP, etc.
If you're actually going to run the algorithm/solve the problem on a physical machine, then roughly speaking the speed of the machine is just how many steps (of the algorithm) it can take per second. In that sense, a quantum computer is tremendously slow (if, at all). A fancy modern (classical) desktop computer can have 8 cores, which all can take billions of rudimentary steps per second - a quantum computer is not gonna top that for a long time (and I believe never). But that's not the point of the quantum computer - the point is that it can be extremely efficient. There are problems that, to solve them on a classical computer, scale very bad with the input parameter (namely, exponential), whereas we know about quantum algorithms that do it much better (scaling wise). And a quantum computer can run quantum algorithms! It should be noted that we only know about a handful of quantum algorithms that perform exponentially faster than their best-known classical counterparts - and Grover is not one of them.
As far as I know, quantum computers are able to solve only some of the NP-Problems in polynomial time, using the Grovers algorithm.
As explained above, there are some known problems that can be solved by quantum computers in polynomial time, while the best known method for classical computers scales exponentially (to some degree) ~ the quintessential example is Shor's algorithm to factor large coprime numbers.
Grovers algorithm is an algorithm that sorts through an unsorted database in $\sqrt{N}$ steps, while the best known classical method takes $N$ steps. That's a speedup, but its not as dramatic as such an 'exponential' speedup. Moreover, in terms of complexity classes it is, by some view, not even a speedup at all - an NP(-complete) problem is solvable in exponentially many steps, and Grovers algorithm alone can only give a square-root speedup - but the square root of an exponential function is also an exponential function.
I read that if one manages to create a reduction of Grovers algorithm on one of the NP-Complete algorithms, for example 3SAT, then it will be a huge milestone, since we could solve all other NP-Complete problems.
NP complete problems are problems such that, with some simple steps, any other NP problem can be converted into this problem. Thus, if you solve any NP-complete problem, all other NP problems come as a 'freebie' (not just the NP-complete ones). In that sense, it would be a huge milestone. It is widely believed that quantum computers cannot solve NP-complete problems, but it has never been proven. As a matter of fact, it hasn't even been proven that $P \not = NP$ - do that and you'll earn a million dollar (and everlasting fame, whatever seals the deal for you:))!
Currently, we know that $P \subseteq BQP$(i.e. anything you can do with a classic computer you can do with a quantum computer). We don't know, strictly speaking, if that actually is a strict inequality! But many people will be very surprised if it turns out to not be one - not to mention the huge implications it would have. People think that $BQP \not = NP$ but that neither $BQP \subset NP$ nor $NP \subset BQP$ - but proving this is very hard and has not been done either way.
-
$\begingroup$ So nobody still (July 2023) have found any nonlinear regime of quantum mechanics then? $\endgroup$ Jul 24 at 17:04