Monday, July 3, 2017

Solution of P versus NP Problem

I know that many people attempted to prove an answer for P versus NP problem.
Also know that it is one of the Seven Millennium Prize problems.

Here is my idea for a proof (possibly with some missing pieces):

Since quantum computers are theoretically capable of infinite calculations per time step (where min could be Planck time),
then we can say quantum computers are definitely more powerful than any equivalent regular computer.
But also there maybe some calculation algorithms where quantum computer cannot provide an answer any faster than a regular computer.
Then we could at least say for sure that:
computingpower(regularcomputer) <= computingpower(quantumcomputer)

If so then if we can prove that, no matter what calculation algorithm is used, a quantum computer cannot solve any of known NP-complete problems in polynomial time, then it would mean that solving any NP-complete problem in polynomial time requires a computer more powerful than any quantum computer.
And that would mean the answer for P versus NP problem is P < NP.
(Keep in mind we already know that, solving any one of NP-complete problems means solving all of them, because each of those problems can be translated to any other in polynomial time.)
(And as for what kind of computer can be more powerful than any quantum computer, keep in mind since a quantum computer is capable of infinite number of calculations at each time step, I think the only kind of computer, which would be more powerful, would be a computer that is capable of infinite number of calculations in zero time step. (Not even one time step, because remember quantum computer already can do that.)
So if solving NP-complete problems in polynimial time requires that kind of computer then the answer is P < NP, again.

I think the only crucial part of this proof is whether we can prove that, quantum computers are incapable of solving NP-complete problems in polynomial time, no matter what algorithm steps are used.

Since all are equivalent, how about we chose Travelling Salesman Problem (TSP) to solve using a quantum computer?

Assume we represented the input graph structure for the problem in the quantum computer in any way we want, like Adjacency list/matrix for example.
Then we could encode that input state using N registers with each register has M qubits.
And for representing the solution output we could use P registers with each has Q qubits.
And we want to set input registers as any given TSP input state and get the answer at least in polynomial number of time steps.
Realize that those polynomial number of time steps can be used following any algorithm we want.

If we look at how a quantum computer allows us to solve integer factoring problem, assuming my understanding is correct, our inputs are two quantum registers with unknown values.
Then we apply multiplication calculation steps and get an output of unknown value in a third quantum register.
(So unknown inputs and unknown calculation output.)
But quantum mechanics allows us to force output register to any certain value and get the input register values for certain, or the reverse, where we can force input registers to certain known values and get the output value for certain.

But realize that for TSP, if we force the output register(s) to the solution for the given input values, (assuming we know the solution already), then input register values cannot be already determined,
because the same (optimal) route can be the optimal solution for many different input register states.
So there is a one-to-many relationship between (optimal) solution state to possible input states.
So if we force a solution state to the output registers then input register values must be indeterminate.
That means quantum computer cannot solve TSP in reverse (unlike Integer Factorization Problem).
And I think this failure in one direction clearly says TSP is a harder problem than Integer Factorization Problem.

Also realize that the reason we can solve Integer Factorization Problem very fast using a quantum computer is because there is entanglement between input and output quantum registers.
(So we can force either input or output registers to any certain values we want and get the certain (an unique) answer for the other side.)
Entanglement requires one-to-one relationship between two sides (input/output or problem/answer) to work and it is a symmetric rule of quantum mechanics.

But also realize that we established above that TSP cannot possibly be solved in both directions using a quantum computer, and using any polynomial time algorithm steps. (Because output to input direction solution is not possible for sure.)
But we also know entanglement needs to work in both directions because of being a symmetric law of nature.

So I think these mean a quantum computer cannot solve TSP in polynomial time no matter what algorithm is used.
And that means solving TSP in polynomial time requires a computer more powerful than any quantum computer.
And that means P < NP.

Is there anything missing in this proof? (Since obviously I cannot see anything wrong with it myself.)

I think we established that no quantum algorithm (that uses entanglement) can solve TSP in polynomial time.
But what about possibility of a classical (non-quantum; no entanglement) algorithm solving it in polynomial time?
Then we need to ask if any classical algorithm can be converted to a quantum algorithm?
Is it really possible to have a classical algorithm that cannot be converted to any quantum algorithm?
Because since there is no quantum algorithm for TSP (that always runs in polynomial time), that means if there is any classical algorithm for TSP (that always runs in polynomial time), it should be impossible to convert that algorithm to a quantum algorithm.
I do not think existence of such algorithms is possible but also I do not have any proof for this claim and I do not know if such proof already exists or not.

Also realize that (assuming what is above is true), if we want an encryption algorithm that cannot be broken by any quantum computer,
that means it needs to be based on an NP problem like TSP, instead of a problem like Integer Factorization.

In above argument we assumed that a quantum computer cannot solve TSP (in polynomial time steps), because if we have the output (solution) we cannot use it to get the input problem state for it
because the input state may not be unique so the input register qubits could not know what bit states to choose. (And so they would stay indeterminate.) But what if that assumption is wrong? What if the input state registers would be set to a solution picked from all possible solutions for that certain output state (with equal probability for each)? Is not that mean it maybe possible to have a polynomial time solution in both directions (input to output and output to input)? I think the total number of possible (valid) input states for a certain given output state would be very large often.
Realize that in TSP problem what we really have is a certain input state and we want to find the optimal solution (output state) for it. If we have a candidate output state and we want to see if that is the optimal solution for our certain input state, and each time we try (set output register(s) to the candidate output state) we get a randomly picked possible valid input state, then we may need to try that so many times until we get the input state matching to what we were trying to solve for. So I do not think we could have a polynomial time solution. Which I think means quantum computer still should be considered unable to solve the problem in both ways.

No comments:

Post a Comment