A Polynomial Time Bounded-Error Quantum Algorithm for Boolean Satisfiability

1) Generate an even superposition of all possible solution states using a Hadamard transform (so go from |000000...> to 1/sqrt(N)*(|00000..0>+|000...1>+|1111...1>). This is pretty standard and used in almost all quantum algorithms.

2) Evaluate each clause of their Boolean E3-CNF function on the superposed input state and transfer the results to a register of control qubits, which yields an entangled state of the input state qubits with these control qubits (akin to the Oracle operator in the Grover search algorithm that performs the operation |x>|0> -> |x>|f(x)>, only here they use multiple Oracle functions and control qubits [which is fine of course]). This is a classical operation which we can implement in reversible computing btw, so no quantum magic involved here yet (apart from applying it to a superposed input state).

3) Increase the amplitude of the states that contain the solution to the search problem, very much akin to the rotation operator employed in Grover search that transfers amplitude from non-solution states to the solution state. <- The problem might be here.

So where I have trouble understanding the algorithm is when they apply the operator M_x to increase "the amplitude of the truth vector of clauses with maximum number of satisfied clauses using a partial negation and iterative measurement technique" (page 6 ff.). They seem to want to repeatedly apply that operator to the same state in order to maximize the amplitude transfer to the correct solution states. However, there is a rather simple proof that shows that the maximum amount of amplitude which you can transfer from one component of a quantum state to another using a control qubit is fundamentally limited by the Unitarian nature of quantum operations. This also limits the efficiency of quantum search in the general case and is the reason that we cannot achieve arbitrary speed-up in the Grover algorithm (see e.g. my PhD thesis for a simple explanation [2] or Grover's original paper to get the full picture [3]). Basically this proof states that although we can generate the quantum information about the answer that we're looking for, we cannot get that information out of the quantum system in an (exponentially) efficient way.

It would be very exciting if this algorithm was correct of course, I just can't imagine that someone would publish such an important finding on Arxiv.org without having it cross-checked and backed by some other people in the field first (which does not seem to be the case judging from the text).

That being said, I think it should be not too difficult to simulate this algorithm and see if all of their transformations are actually unitary and possible to implement in reversible computing and if they correctly take into account the entanglement of individual control qubits and the corresponding wave function collapse due to the qubit measurements they perform.

[1] Grover Search Algorithm - https://en.wikipedia.org/wiki/Grover%27s_algorithm

[2] My PhD thesis on an Experimental Realization of Grover's Algorithm - see page 136 ff. for a simple explanation of the effiency of quantum searching http://iramis.cea.fr/spec/Pres/Quantro/static/wp-content/upl...

[3] Grover's Algorithm - Original Paper http://arxiv.org/abs/quant-ph/9605043

[4] The No-Cloning Theorem: https://en.wikipedia.org/wiki/No-cloning_theorem

This is the first time I've heard of a quantum simulator. How expensive would be to run the algorithm in one?

qubit_0="x0"

qubit_1="x1"

qubit_2="x2"

qubit_3="c0"

qubit_4="c1"

qubit_5="d0"

qubit_6="ax"

gateproperty("group_gate10gate11gate12gate13gate14_6068",reps=10.0)

gate0={H:-:-:-:-:-:-}

gate1={-:H:-:-:-:-:-}

gate2={-:-:H:-:-:-:-}

gate3={1:1:1:NOT:-:-:-}

gate4={NOT:-:-:-:-:-:-}

gate5={-:NOT:-:-:-:-:-}

gate6={-:-:NOT:-:-:-:-}

gate7={1:1:1:-:NOT:-:-}

gate8={-:-:NOT:-:-:-:-}

gate9={-:NOT:-:-:-:-:-}

group_gate10gate11gate12gate13gate14_6068.gate10={-:-:-:1:-:-:V}

group_gate10gate11gate12gate13gate14_6068.gate11={-:-:-:-:1:-:V}

group_gate10gate11gate12gate13gate14_6068.gate12={-:-:-:-:-:1:V}

group_gate10gate11gate12gate13gate14_6068.gate13={-:-:-:-:-:-:!}

group_gate10gate11gate12gate13gate14_6068.gate14_6068={-:-:-:-:-:-:NOT}

gate17={-:-:-:!:-:-:-}

gate14={-:-:-:-:!:-:-}

As I can see, the algorithm really works. Below is the code for the example shown in Fig 5, (x0 v x1 v x2)&(~x0 v ~x1 v ~x2). You can try it by yourself and here are the steps:

1- copy the below code to a text editor and save it with extension .jaq.

2- open the file with jaQuzzi.

3- set |c0>=|1>,|c1>=|1>,|d0>=|1>

4- run the circuit.

5- select |c0> and |c1> and press on "plot probability chart" to open the "chart center" and see the correct answer for c's.

6- select |x0>, |x1> and |x2> and press on "plot probability chart" to open the "chart center" and see the probability for the superposition of the correct answer of x's.

Hints:

-You can trace the circuit by selecting |c0> and |c1> and press on "plot probability chart" to open the "chart center", reset the circuit and start pressing on "step forward" to watch the probability of the solution increases during the loop.

-Don't forget to select auto in the "chart center".

If you want to play around,

1-set the number of x’s and c’s as required.

2-add the dummy qubits.

3-initialize c’s and d’s to |1> (required number of d’s calculated using equations in the paper)

4- set V = [0.5(1+exp((ipi)/k)),0.5(1-exp((ipi)/k));0.5(1-exp((ipi)/k)),0.5(1+exp((ipi)/k))], where k is the number of c’s and d’s.

(you have to ungroup the set of gates before you modify V, and group again)

5- set the number of iterations in the properties of the group.

The code in another comment...have fun!!!

infparadox: It's a subsystem, not a subspace. When you discard a subsystem which is entangled (as they specifically say it is) the result cannot be a pure state, and you need to express it in the dentist matrix formalism by taking the partial trace over the discarded system. What they wrote is not correct.

For instance, while SAT can be used to model one-player games (sudoku, 8 queens, etc.), you need QBF to model two-player games (even tic-tac-toe). And stock market looks a lot like a n-players game. So, unless NP = PSPACE, even with P = NP you're stuck with limited superpowers.

> The common belief concerning the relationship between NP and BQP was that NP is not contained in BQP (e.g see chapter 15 of [8]. However, a recent paper by one of the current authors has shown that an NP-hard problem (Graph Bisection) can be efficiently solved, with low failure probability, by a quantum algorithm [13]. This implies that NP is in fact contained within BQP, as any NP problem can be polynomially reduced to an NP-hard problem

This classic argument is flawed, because P=NP doesn't mean that you can "easily" solve all NP problems. Nature is still free to define huge exponents to difficult problems, making them essentially unsolvable in practice. I even heard Knuth recognizing this recently.

The basic idea is that they've found an efficient quantum algorithm for solving an NP-hard problem (MAX-E3-SAT). This is a version of the boolean satisfiability problem: given a boolean expression (in this case, in a certain normal form) with N variables, is there some way to set the variables such that the expression is true?

As those familiar with complexity theory will know, if it's possible to solve one NP-hard problem efficiently, it's also possible to solve every NP problem efficiently by adding efficient algorithmic steps. Therefore, we can now use a quantum computer to solve arbitrary NP problems (well, we could if we had a large enough one).

"NP" is computer science shorthand for problems whose answers can be checked efficiently, but cannot be discovered efficiently.

Prior to this, only a few NP problems were efficiently solvable by quantum computers (factoring and things that reduce to factoring, due to Shor's algorithm). With this discovery, any NP problem shares this characteristic. Technically NP only applies to decision problems, but it's generally not that difficult to extend it to computations that produce additional information.

One consequence of this is that it will completely ruin public-key cryptography in the face of a quantum computer: public-key cryptography relies on a hard instance of an NP problem, and no such instances are hard on a quantum computer anymore. This is relatively minor, as we currently use factorization (RSA) or elliptic-curves for public-key encryption, and those were already breakable with Shor's algorithm.

Quantum computers should also be able to reverse hashes and find collisions easily: the NP algorithm for this is trivial. You may not be able to reverse them to the "correct" input, though. If someone were silly enough to use a perfectly good quantum computer to mine Bitcoin, it would be insanely efficient. This is relatively minor as well -- more important than the public key cryptography, but it's not going to cause all computer security to collapse.

Many useful real-world problems are in the NP space: traveling salesman, protein folding, things of that nature. A quantum computer could be used to solve these problems. This would be a really big deal, and overall a great boon to humanity.

The result also has consequences for quantum computation specifically, in that it also takes care of the negative sign problem, which arises when simulating certain kinds of important quantum many body systems.

And last but certainly not least, all those press releases breathlessly proclaiming Quantum computers work by trying a gazillion possibilities at once (with no worries about the plausibility of actually reading out the correct answer with a non-negligible probability) weren't so far off after all.

All in all, either there is a mistake hidden somewhere in the preprint or this is the greatest scientific achievement since Evolution invented Human Level intelligence.

See here for intuition on why NP-complete problems if at all solvable without brute force, should also be efficiently solvable: http://windowsontheory.org/2013/05/06/reasons-to-care-in-hon...

They are attempting to solve the problem for k=3 and then probably figure out how to run the approximation algorithm for this problem on a quantum computer.

If someone builds a useful NP problem solving machine, that will change the world.

Heck, most of the early groundwork in the computational field is probably more important than an algorithm that is useful only on quantum computers.

Yes, Nielsen and Chuang is the standard textbook for quantum computing; it’s excellent (even though 16 years old by now). If you wanted to start with something shorter and more introductory, you could try David Mermin’s “Introduction to Quantum Computer Science.”

I am the co-author of the textbook mentioned as "Lipton" in the comment by user dmmackay above.