26 ms·

A Polynomial Time Bounded-Error Quantum Algorithm for Boolean Satisfiability

148 points by user_235711 11y ago

Certhas 11y ago
Wow. Can't wait to see if this holds up. For context: "On the other hand, Bennett et al. [11] gave oracle evidence that NP is not in BQP, and while no one regards such evidence as decisive, today it seems extremely unlikely that quantum computers can solve NP-complete problems in polynomial time." http://www.scottaaronson.com/papers/bqpph.pdf http://www.scottaaronson.com/papers/bqpph.pdf
analogmind 11y ago
Can anyone give me a simplified explanation of this paper and the consequences of it?
- Gladdyu 11y ago
  In essence, if this algorithm is correct, for quantum computers it holds that P = NP, which means that every problem for which the answer can be checked in polynomial time, you can also compute the answer in polynomial time.
  - marcosdumay 11y ago
    Polynomial time in a quantum computer is called QP. (The same way that polynomial time in a non deterministic computer is called NP.)
  - jflatow 11y ago
    Isn't it actually only showing that BQP contains NP, not P = NP?
- im3w1l 11y ago
  This breaks a lot of cryptography. More than Shor's.
  - marcosdumay 11y ago
    Just to add to the GP, this would break any cryptography algorithm that one can run on a classical computer. Currently, quantum computers are believed to break only our most used algorithms, not all of them.
- amalcon 11y ago
  So, to start with, it's worth reminding that this is a preprint. It hasn't necessarily been reviewed or anything, so shouldn't be considered a final result. 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.
  - deleted 11y ago
    [deleted]
  - Scea91 11y ago
    Polynomial complexity doesn't necessarily mean efficient if the polynom is of a high order.
- Dn_Ab 11y ago
  The short version is, if this is correct (which is exceedingly unlikely) then either quantum mechanics is wrong or whether P=NP has just become irrelevant. This is because, as Scott Aaronson is often forced to tirelessly point out, an inability to build a Quantum Computer must also show Quantum mechanics to somehow be in error. If instead, we can build a Quantum computer and this result is true then the universe has suddenly become an incredibly more interesting place (for one example, building this would also solve AI). 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-honor-of-scott-aaronson/ http://windowsontheory.org/2013/05/06/reasons-to-care-in-hon...
sanxiyn 11y ago
If this holds, this is the discovery of the century.
- yxhuvud 11y ago
  Don't be silly. A hundred years take you back to 1915. There are plenty of scientific discoveries that is more important than this will ever be that has been discovered since then. The general theory of relativity, the transistor, DNA and many other are obviously more important. Heck, most of the early groundwork in the computational field is probably more important than an algorithm that is useful only on quantum computers.
  - invernomut0 11y ago
    Note: This century started in 2000, not one hundred years ago.
  - andyjohnson0 11y ago
    "Discovery of the century" is a shorthand for really important. Don't take it literally. Proving P=NP would be extremely significant in mathematics, though.
    - mekkz 11y ago
      Nobody doubts that proving P=NP would be the discovery of the century, but that's not what this paper is trying to prove.
      - andyjohnson0 11y ago
        You're correct. They're claiming an algorithm to solve an NP hard problem in polynomial time. I was thinking of "if this paper is a contribution to eventually proving/disproving P=NP...", but failed to express that.
  - NegativeK 11y ago
    As another commenter pointed out, being able to crack NP problems quickly will give you theorem provers. At that point quantum computing research will receive gobs of funding -- and our knowledge will absolutely explode. You can debate whether it's the absolute top discovery, but this would be a lever to shift around the entire math and computer science field. If it wasn't a shaky paper, of course.
yk 11y ago
Can somebody comment, if this actually means that one can essentially solve SAT with a quantum computer? In particular: The algorithm prepares a superposition of all possible variable assignments, then the algorithm evaluates the set of clauses using all the pos-sible variable assignments simultaneously and then amplifies the amplitudes of the state(s) that achieve(s) the maximum satisfaction to the set of clauses using a novel amplitude amplification technique that applies an iterative partial nega-tion and partial measurement. This sounds a bit like hiding some runtime in 'partial measurement.' ( But I did only read the introduction yet, and I don't understand quantum computers.)
- sanxiyn 11y ago
  I am not sure whether this works, but the paper's statement does actually mean that one can solve SAT in polynomial time with high probability with a quantum computer.
  - andrelaszlo 11y ago
    An "arbitrary [sic] high probability" even. If I got it right.
    - sanxiyn 11y ago
      Yup, arbitrarily high probability.
- zitterbewegung 11y ago
  To understand this paper you should read about this problem which they cite in the paper. https://en.wikipedia.org/wiki/MAXEkSAT https://en.wikipedia.org/wiki/MAXEkSAT 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.
andyjohnson0 11y ago
The paper describes a "proposed" algorithm with a lot of theoretical justification [1]. Is there any way to verify it on a real quantum computer or reliable simulation? I'm thinking of the way that Shor's algorithm was verified [2] using a real quantum device. [1] I'm not qualified to understand the detail of the paper, although I can appreciate its general outline and the broad consequences of it being correct. [2] http://arxiv.org/abs/1202.5707 http://arxiv.org/abs/1202.5707
tgb 11y ago
One of the points of Scott Aaronson's excellent "Quantum Computing since Democritus" is that if you can quickly solve NP problems, you basically have super powers. Forget about SAT or Travelling Salesman, you can now do fast automated theorem provers and the like. Depending on how it were solved, you wouldn't read about P=NP on arxiv, you'd read about someone making billions on the stock market. Aaronson describes it as being comparably implausible to having faster than light communication. If this paper is true, then it looks to me like quantum computers would be a means of doing that. I'm skeptical. Know those sci-fi stories where they hand-wave a quantum computer to have infinite computing power? Then they simulate the universe or hack all the computers simultaneously or whatever. That's all a laughable misinterpretation of what current state-of-the-art quantum algorithms can do (even if we remove the technical details of constructing the machine). Well, if this paper holds up, then that's a whole lot closer to the truth, maybe! (Disclaimer: not an expert. I really hope to see Aaronson's analysis of this soon.)
- Rauchg 11y ago
  It's worth pointing out that they already claim to have proven NP ⊆ BQP > 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
  - jsprogrammer 11y ago
    >any NP problem can be polynomially reduced to an NP-hard problem Except that there is some probability that the algorithm will be unable to solve the problem?
    - eru 11y ago
      Success/Failure would be independent between runs. Ie if you fail, you just run again.
bhouston 11y ago
Here is the author's previous publication track record: https://scholar.google.com/citations?hl=en&user=CZz2XFIAAAAJ&view_op=list_works&sortby=pubdate https://scholar.google.com/citations?hl=en&user=CZz2XFIAAAAJ... His co-author is more infleuntial as measured by number of citations: https://scholar.google.com/citations?user=co2yqKoAAAAJ&hl=en https://scholar.google.com/citations?user=co2yqKoAAAAJ&hl=en
- deong 11y ago
  I know Jon Rowe a little bit. He's a very well-respected and reputable researcher.
danbruc 11y ago
1. The presented construction is pretty simple and falls in the category of computing the output for all possible inputs in parallel and then extract the correct or best input. 2. This is exactly the type of construction that is often(?) believed not to work, i.e. even on a quantum computer you have to exploit the structure of the problem and can not just throw quantum parallelism at the problem. 3. They already published a paper in May [1] in which they applied the same techniques to graph partitioning problems. 4. Which option is true? The algorithm is wrong, the believe that quantum computers are of not much help for NP-hard problems was wrong, or there is a way to translate this algorithm to classical computers? The last one would be awesome but the first two seem much more likely. 5. There is one thing in the paper that struck me as a bit odd, namely that they just add a couple of dummy qubits to boost the probability of one measurement. It is certainly possible that something like that works but at least it runs counter to my intuition. It reminds me of zero-padding FFT inputs to get a result with higher frequency resolution which of course is not real. [1] http://arxiv.org/abs/1505.06284 http://arxiv.org/abs/1505.06284
- clemensley 11y ago
  Can you (or someone else) explain why that simple construction where all outputs are computed in parallel is not believed to work? Is it that quantum computers have bounded parallelism in some sense?
  - nhaehnle 11y ago
    It is possible to compute all outputs in parallel with a quantum computer, but what you'll end up is an unintelligibly entangled state. What you really want is a single output, and there's no generic way of disentangling the entangled state in a useful way. The reason why numbers can be factored faster using quantum computers is precisely that factoring has an algebraic structure which can be used to achieve this disentangling.
  - deleted 11y ago
    [deleted]
  - repsilat 11y ago
algorias 11y ago
[Note: I am a master student doing my thesis in this area] Ok, I'm going to go out on a limb here and call bullshit, based on the meta-reason that they cite a paper of theirs which already claims to show that NP is contained in BQP using a different NP-complete problem, published in may 2015 (which is basically the same groundbreaking result as this paper), but this somehow completely failed to make waves in the community. Additionally, on a superficial reading of the paper nothing seems wrong with it, except that it has this air of everything being too easy, too novel, not building on any widely recognized partial results. Considering this problem has been attacked by hundreds (?) of researchers over the years, it seems highly implausible that they just happened to find this one weird trick nobody had thought of before. Anyway, those are just heuristics, and I'd love to be wrong on this occasion, but life is too short to give my full attention to a dubious paper for more than 15 minutes. I could attempt to whip up this algorithm in a quantum simulator, but that would take a considerable amount of time to do right, so I'll let somebody else do the work of debunking/confirming the result.
- yread 11y ago
  Why comment when you don't have the time for more than superficial analysis?
  - algorias 11y ago
    According to that criterion, no one should comment on HN ever, unless they are writing at the level of a peer reviewed journal. I supposed it would be interesting for people here for me to at least point out some obvious red flags.
  - gjm11 11y ago
    Because even the superficial analysis provides more than zero useful information. (Nothing super-obviously wrong. Nothing that looks clever enough to overcome the guess that, none the less, something's probably wrong.)
  - Anderkent 11y ago
    'This relies on their earlier paper from May 2015, and if that paper was correct it would have made big waves' is valuable context.
anukulrm 11y ago
As much as I'd like to be on the cutting edge of science/math, I (suspect most of us here) don't have the tools to understand, let alone evaluate this preprint. So before we make a tweet storm and start blowing our horns, let's try to hold our horses and wait for peer review. That could take well over a year. Well, in the meanwhile, I have a question: what's a good intro resource to quantum computing? For general complexity intro, I like Michael Sipser's Theory Of Computation
- danbruc 11y ago
  I don't think it will take long to get a verdict, the construction is really pretty simple. Maybe if there is a really subtle error this could cause some debate but as far as I can tell there is nothing exotic in there. The only thing that struck me as a bit odd is that they just add a couple of dummy qubits to increase the probability of one measurement.
- gjm11 11y ago
  Here's Scott Aaronson's answer to a similar question on his blog a couple of weeks ago: 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.”
  - anukulrm 11y ago
    Great, thanks! I'll check those out.
  - dmmckay 11y ago
    Lipton wrote a pretty decent and short intro to QC that builds the theory a little differently from usual. It is aimed more towards Mathematicians and Computer Scientists than Physicists, I believe, but I think it is pretty understandable in general. I think Sipser is probably the best introduction to Computation if you do not have a background in Computability and Complexity. Arora and Barak's text has a much larger breadth and is much more detailed as far as Complexity goes. It is the more appropriate of the two if you are just interested in Computational Complexity.
whyleyc 11y ago
Somewhat relevant (If I just proved that P = NP, how do I start taking over the world?): http://www.quora.com/If-I-just-proved-that-P-NP-how-do-I-start-taking-over-the-world http://www.quora.com/If-I-just-proved-that-P-NP-how-do-I-sta...
SFjulie1 11y ago
I still want to have time to explore my won KSAT project. True = UP, False = DOWN Every variables are a spin (node) Every operation are describing a neighborhood (vertex). Mapping physical effects of spin magnetism (magnetism or anti ferro magnetism) to 2 operations Refactoring Boolean equation to only those 2 (boolean algebrae rox) Building a kind of conway game of life cellular automata. Constructing the utility function per variable based on the neighboorhood Make evolve (montecarlo) in a globally slowly moving magnetic field Look at the number of flips per iterations and analyse results. Explore the oscillation time half life Explore the temperature required to avoid too much variations too much convergence in a frustrated loop Explore utility per operation MAKE NICE GRAPHS proove it gives results.
deleted 11y ago
[deleted]
da-bacon 11y ago
Eq. 16. As a grad student in quantum computing we used to have a game where we would race to see who could be the first one to spot the flaw in a paper that claimed an efficient quantum polynomial time algorithm for NP-complete problems. My bet after a few minutes looking at the paper is Eq. 16. Eq. 15 is computing the clauses with a traditional clause oracle \sum_x |x>|C(x)> where C(x) is a vector of the clauses evaluated on the input x. Eq. 16 claims that one can ignore the first register and this becomes \sum_x |C(x)>. That's not correct: the system is entangled across those two registers, and the partial portion of one of those systems is a mixed state. In particular there is no coherence between the |C(x)> states. The next step relies crucially on this property.
- ThePhysicist 11y ago
  My guess is that the problem lies in the M_x operator, which is similar to the Grover rotation operator but supposedly only acts on the control qubits and another control-control qubit (see my other comment here). Would love to get your opinion on that!
- infparadox 11y ago
  I don't think there is a problem in that, they are just considering a subspace of the system.
- irljf 11y ago
  Yes, Eq. 16 certainly does not follow from 15. They should have a mixed state of the system. You should recognize this, since it's the graph isomorphism approach everyone tries. 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.
  - infparadox 11y ago
    I am not expert in the field, I just took a course, but I know that a mixed state is not the same as an entangled state. In their case it is entangled not mixed and so there is no need to take the partial trace. For example, consider a two subsystems entangled with each other, |q1>|q2>. I we want to apply an operator U on the second subsytem we apply I(x)U or we can simply consider the second subsystem and apply U|q2>. This is valid as long as the entanglement holds and Identity gates are assumed to be applied on the first subsystem.
Strilanc 11y ago
The algorithm is: 1. Hadamard transform into a uniform superposition of all variable assignments (very standard step) 2. Add an OFF ancilla bit and rotate it by 1/(2m)'th of a turn for each satisfied clause, where m is the number of clauses, using triply-controlled m'th-root-of-NOT gates. 3. Measure that ancilla qubit 4. If the ancilla stayed OFF, restart the whole algorithm. 5. Repeat steps 2 through 4 a total of R times, without triggering the restart (the appropriate value for R is figured out later) 6. Measure all the variable qubits. 7. Return SATISFIABLE iff all clauses are satisfied by the measured variable values (Note that I simplified the algorithm. The paper uses ancilla bits to hold the clauses in qubits, but they are not needed because they're only measured at the end and otherwise only used as controls.) For starters, I'll just say that up front there's no way this works. It's too simple. Other researchers would have tried it. Repeatedly rotating proportional to the amount satisfied and measuring? Too obvious. I would not be surprised at all if a majority of researchers have come up with this idea, tried it, and understood why it didn't work. Grover's algorithm is more complicated than this. Anyways, why does it actually not work? It becomes clear if we simplify the algorithm a bit more by deferring the conditional restarting measurements. Instead of conditionally continuing the 2-4 loop R times, simply run Step 2 a total of R times up front. Then measure the R ancilla bits you introduced, and restart if any of them was false. This is equivalent to conditionally restarting because a) there's no information dependency between the loops beyond "don't bother doing it" and b) measurements can always be deferred until later [1]. Now make the simplifying assumption that all variable assignments, except for a single satisfying one, satisfy 7/8'ths of the clauses (based on [1]). Note that applying 7/8'ths of a NOT will transition an OFF bit into a state where it has a roughly 96% chance of being ON. Since most possible assignments are not satisfying, and non-satisfying assignments have a 4% chance of causing a restart (the satisfying assignment has a 0% chance, but it gets diluted by the exponentially many non-satisfiers), the ancilla bits' measured value will be dominated by the non-satisfying assignments. Each ancilla bit will have a roughly 4% chance of being OFF. That means the chance of not having to restart is roughly 0.96^R. But the paper says that R increases faster than linear with respect to the number of qubits. So the odds of not-restarting are upper bounded by 0.96^N. That places an exponential multiplier on the running time, because it's so unlikely to succeed as N gets large. Therefore this is not a polynomial time algorithm. 1: https://en.wikipedia.org/wiki/Deferred_Measurement_Principle https://en.wikipedia.org/wiki/Deferred_Measurement_Principle 2: https://en.wikipedia.org/wiki/Karloff%E2%80%93Zwick_algorithm https://en.wikipedia.org/wiki/Karloff%E2%80%93Zwick_algorith...

148 points by user_235711 11y ago

Wow. Can't wait to see if this holds up. For context: "On the other hand, Bennett et al. [11] gave oracle evidence that NP is not in BQP, and while no one regards such evidence as decisive, today it seems extremely unlikely that quantum computers can solve NP-complete problems in polynomial time." http://www.scottaaronson.com/papers/bqpph.pdf http://www.scottaaronson.com/papers/bqpph.pdf

analogmind 11y ago

Can anyone give me a simplified explanation of this paper and the consequences of it?

Gladdyu 11y ago
In essence, if this algorithm is correct, for quantum computers it holds that P = NP, which means that every problem for which the answer can be checked in polynomial time, you can also compute the answer in polynomial time.
- marcosdumay 11y ago
  Polynomial time in a quantum computer is called QP. (The same way that polynomial time in a non deterministic computer is called NP.)
- jflatow 11y ago
  Isn't it actually only showing that BQP contains NP, not P = NP?
im3w1l 11y ago
This breaks a lot of cryptography. More than Shor's.
- marcosdumay 11y ago
  Just to add to the GP, this would break any cryptography algorithm that one can run on a classical computer. Currently, quantum computers are believed to break only our most used algorithms, not all of them.
amalcon 11y ago
So, to start with, it's worth reminding that this is a preprint. It hasn't necessarily been reviewed or anything, so shouldn't be considered a final result. 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.
- deleted 11y ago
  [deleted]
- Scea91 11y ago
  Polynomial complexity doesn't necessarily mean efficient if the polynom is of a high order.
Dn_Ab 11y ago
The short version is, if this is correct (which is exceedingly unlikely) then either quantum mechanics is wrong or whether P=NP has just become irrelevant. This is because, as Scott Aaronson is often forced to tirelessly point out, an inability to build a Quantum Computer must also show Quantum mechanics to somehow be in error. If instead, we can build a Quantum computer and this result is true then the universe has suddenly become an incredibly more interesting place (for one example, building this would also solve AI). 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-honor-of-scott-aaronson/ http://windowsontheory.org/2013/05/06/reasons-to-care-in-hon...

sanxiyn 11y ago

If this holds, this is the discovery of the century.

yxhuvud 11y ago
Don't be silly. A hundred years take you back to 1915. There are plenty of scientific discoveries that is more important than this will ever be that has been discovered since then. The general theory of relativity, the transistor, DNA and many other are obviously more important. Heck, most of the early groundwork in the computational field is probably more important than an algorithm that is useful only on quantum computers.
- invernomut0 11y ago
  Note: This century started in 2000, not one hundred years ago.
- andyjohnson0 11y ago
  "Discovery of the century" is a shorthand for really important. Don't take it literally. Proving P=NP would be extremely significant in mathematics, though.
  - mekkz 11y ago
    Nobody doubts that proving P=NP would be the discovery of the century, but that's not what this paper is trying to prove.
    - andyjohnson0 11y ago
      You're correct. They're claiming an algorithm to solve an NP hard problem in polynomial time. I was thinking of "if this paper is a contribution to eventually proving/disproving P=NP...", but failed to express that.
- NegativeK 11y ago
  As another commenter pointed out, being able to crack NP problems quickly will give you theorem provers. At that point quantum computing research will receive gobs of funding -- and our knowledge will absolutely explode. You can debate whether it's the absolute top discovery, but this would be a lever to shift around the entire math and computer science field. If it wasn't a shaky paper, of course.

yk 11y ago

Can somebody comment, if this actually means that one can essentially solve SAT with a quantum computer? In particular: The algorithm prepares a superposition of all possible variable assignments, then the algorithm evaluates the set of clauses using all the pos-sible variable assignments simultaneously and then amplifies the amplitudes of the state(s) that achieve(s) the maximum satisfaction to the set of clauses using a novel amplitude amplification technique that applies an iterative partial nega-tion and partial measurement. This sounds a bit like hiding some runtime in 'partial measurement.' ( But I did only read the introduction yet, and I don't understand quantum computers.)

sanxiyn 11y ago
I am not sure whether this works, but the paper's statement does actually mean that one can solve SAT in polynomial time with high probability with a quantum computer.
- andrelaszlo 11y ago
  An "arbitrary [sic] high probability" even. If I got it right.
  - sanxiyn 11y ago
    Yup, arbitrarily high probability.
zitterbewegung 11y ago
To understand this paper you should read about this problem which they cite in the paper. https://en.wikipedia.org/wiki/MAXEkSAT https://en.wikipedia.org/wiki/MAXEkSAT 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.

andyjohnson0 11y ago

The paper describes a "proposed" algorithm with a lot of theoretical justification [1]. Is there any way to verify it on a real quantum computer or reliable simulation? I'm thinking of the way that Shor's algorithm was verified [2] using a real quantum device. [1] I'm not qualified to understand the detail of the paper, although I can appreciate its general outline and the broad consequences of it being correct. [2] http://arxiv.org/abs/1202.5707 http://arxiv.org/abs/1202.5707

tgb 11y ago

One of the points of Scott Aaronson's excellent "Quantum Computing since Democritus" is that if you can quickly solve NP problems, you basically have super powers. Forget about SAT or Travelling Salesman, you can now do fast automated theorem provers and the like. Depending on how it were solved, you wouldn't read about P=NP on arxiv, you'd read about someone making billions on the stock market. Aaronson describes it as being comparably implausible to having faster than light communication. If this paper is true, then it looks to me like quantum computers would be a means of doing that. I'm skeptical. Know those sci-fi stories where they hand-wave a quantum computer to have infinite computing power? Then they simulate the universe or hack all the computers simultaneously or whatever. That's all a laughable misinterpretation of what current state-of-the-art quantum algorithms can do (even if we remove the technical details of constructing the machine). Well, if this paper holds up, then that's a whole lot closer to the truth, maybe! (Disclaimer: not an expert. I really hope to see Aaronson's analysis of this soon.)

Rauchg 11y ago
It's worth pointing out that they already claim to have proven NP ⊆ BQP > 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
- jsprogrammer 11y ago
  >any NP problem can be polynomially reduced to an NP-hard problem Except that there is some probability that the algorithm will be unable to solve the problem?
  - eru 11y ago
    Success/Failure would be independent between runs. Ie if you fail, you just run again.

bhouston 11y ago

Here is the author's previous publication track record: https://scholar.google.com/citations?hl=en&user=CZz2XFIAAAAJ&view_op=list_works&sortby=pubdate https://scholar.google.com/citations?hl=en&user=CZz2XFIAAAAJ... His co-author is more infleuntial as measured by number of citations: https://scholar.google.com/citations?user=co2yqKoAAAAJ&hl=en https://scholar.google.com/citations?user=co2yqKoAAAAJ&hl=en

deong 11y ago
I know Jon Rowe a little bit. He's a very well-respected and reputable researcher.

danbruc 11y ago

1. The presented construction is pretty simple and falls in the category of computing the output for all possible inputs in parallel and then extract the correct or best input. 2. This is exactly the type of construction that is often(?) believed not to work, i.e. even on a quantum computer you have to exploit the structure of the problem and can not just throw quantum parallelism at the problem. 3. They already published a paper in May [1] in which they applied the same techniques to graph partitioning problems. 4. Which option is true? The algorithm is wrong, the believe that quantum computers are of not much help for NP-hard problems was wrong, or there is a way to translate this algorithm to classical computers? The last one would be awesome but the first two seem much more likely. 5. There is one thing in the paper that struck me as a bit odd, namely that they just add a couple of dummy qubits to boost the probability of one measurement. It is certainly possible that something like that works but at least it runs counter to my intuition. It reminds me of zero-padding FFT inputs to get a result with higher frequency resolution which of course is not real. [1] http://arxiv.org/abs/1505.06284 http://arxiv.org/abs/1505.06284

clemensley 11y ago
Can you (or someone else) explain why that simple construction where all outputs are computed in parallel is not believed to work? Is it that quantum computers have bounded parallelism in some sense?
- nhaehnle 11y ago
  It is possible to compute all outputs in parallel with a quantum computer, but what you'll end up is an unintelligibly entangled state. What you really want is a single output, and there's no generic way of disentangling the entangled state in a useful way. The reason why numbers can be factored faster using quantum computers is precisely that factoring has an algebraic structure which can be used to achieve this disentangling.
- deleted 11y ago
  [deleted]
- repsilat 11y ago

algorias 11y ago

[Note: I am a master student doing my thesis in this area] Ok, I'm going to go out on a limb here and call bullshit, based on the meta-reason that they cite a paper of theirs which already claims to show that NP is contained in BQP using a different NP-complete problem, published in may 2015 (which is basically the same groundbreaking result as this paper), but this somehow completely failed to make waves in the community. Additionally, on a superficial reading of the paper nothing seems wrong with it, except that it has this air of everything being too easy, too novel, not building on any widely recognized partial results. Considering this problem has been attacked by hundreds (?) of researchers over the years, it seems highly implausible that they just happened to find this one weird trick nobody had thought of before. Anyway, those are just heuristics, and I'd love to be wrong on this occasion, but life is too short to give my full attention to a dubious paper for more than 15 minutes. I could attempt to whip up this algorithm in a quantum simulator, but that would take a considerable amount of time to do right, so I'll let somebody else do the work of debunking/confirming the result.

yread 11y ago
Why comment when you don't have the time for more than superficial analysis?
- algorias 11y ago
  According to that criterion, no one should comment on HN ever, unless they are writing at the level of a peer reviewed journal. I supposed it would be interesting for people here for me to at least point out some obvious red flags.
- gjm11 11y ago
  Because even the superficial analysis provides more than zero useful information. (Nothing super-obviously wrong. Nothing that looks clever enough to overcome the guess that, none the less, something's probably wrong.)
- Anderkent 11y ago
  'This relies on their earlier paper from May 2015, and if that paper was correct it would have made big waves' is valuable context.

anukulrm 11y ago

As much as I'd like to be on the cutting edge of science/math, I (suspect most of us here) don't have the tools to understand, let alone evaluate this preprint. So before we make a tweet storm and start blowing our horns, let's try to hold our horses and wait for peer review. That could take well over a year. Well, in the meanwhile, I have a question: what's a good intro resource to quantum computing? For general complexity intro, I like Michael Sipser's Theory Of Computation

danbruc 11y ago
I don't think it will take long to get a verdict, the construction is really pretty simple. Maybe if there is a really subtle error this could cause some debate but as far as I can tell there is nothing exotic in there. The only thing that struck me as a bit odd is that they just add a couple of dummy qubits to increase the probability of one measurement.
gjm11 11y ago
Here's Scott Aaronson's answer to a similar question on his blog a couple of weeks ago: 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.”
- anukulrm 11y ago
  Great, thanks! I'll check those out.
- dmmckay 11y ago
  Lipton wrote a pretty decent and short intro to QC that builds the theory a little differently from usual. It is aimed more towards Mathematicians and Computer Scientists than Physicists, I believe, but I think it is pretty understandable in general. I think Sipser is probably the best introduction to Computation if you do not have a background in Computability and Complexity. Arora and Barak's text has a much larger breadth and is much more detailed as far as Complexity goes. It is the more appropriate of the two if you are just interested in Computational Complexity.

whyleyc 11y ago

Somewhat relevant (If I just proved that P = NP, how do I start taking over the world?): http://www.quora.com/If-I-just-proved-that-P-NP-how-do-I-start-taking-over-the-world http://www.quora.com/If-I-just-proved-that-P-NP-how-do-I-sta...

SFjulie1 11y ago

I still want to have time to explore my won KSAT project. True = UP, False = DOWN Every variables are a spin (node) Every operation are describing a neighborhood (vertex). Mapping physical effects of spin magnetism (magnetism or anti ferro magnetism) to 2 operations Refactoring Boolean equation to only those 2 (boolean algebrae rox) Building a kind of conway game of life cellular automata. Constructing the utility function per variable based on the neighboorhood Make evolve (montecarlo) in a globally slowly moving magnetic field Look at the number of flips per iterations and analyse results. Explore the oscillation time half life Explore the temperature required to avoid too much variations too much convergence in a frustrated loop Explore utility per operation MAKE NICE GRAPHS proove it gives results.

deleted 11y ago

[deleted]

da-bacon 11y ago

Eq. 16. As a grad student in quantum computing we used to have a game where we would race to see who could be the first one to spot the flaw in a paper that claimed an efficient quantum polynomial time algorithm for NP-complete problems. My bet after a few minutes looking at the paper is Eq. 16. Eq. 15 is computing the clauses with a traditional clause oracle \sum_x |x>|C(x)> where C(x) is a vector of the clauses evaluated on the input x. Eq. 16 claims that one can ignore the first register and this becomes \sum_x |C(x)>. That's not correct: the system is entangled across those two registers, and the partial portion of one of those systems is a mixed state. In particular there is no coherence between the |C(x)> states. The next step relies crucially on this property.

ThePhysicist 11y ago
My guess is that the problem lies in the M_x operator, which is similar to the Grover rotation operator but supposedly only acts on the control qubits and another control-control qubit (see my other comment here). Would love to get your opinion on that!
infparadox 11y ago
I don't think there is a problem in that, they are just considering a subspace of the system.
irljf 11y ago
Yes, Eq. 16 certainly does not follow from 15. They should have a mixed state of the system. You should recognize this, since it's the graph isomorphism approach everyone tries. 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.
- infparadox 11y ago
  I am not expert in the field, I just took a course, but I know that a mixed state is not the same as an entangled state. In their case it is entangled not mixed and so there is no need to take the partial trace. For example, consider a two subsystems entangled with each other, |q1>|q2>. I we want to apply an operator U on the second subsytem we apply I(x)U or we can simply consider the second subsystem and apply U|q2>. This is valid as long as the entanglement holds and Identity gates are assumed to be applied on the first subsystem.

Strilanc 11y ago

The algorithm is: 1. Hadamard transform into a uniform superposition of all variable assignments (very standard step) 2. Add an OFF ancilla bit and rotate it by 1/(2m)'th of a turn for each satisfied clause, where m is the number of clauses, using triply-controlled m'th-root-of-NOT gates. 3. Measure that ancilla qubit 4. If the ancilla stayed OFF, restart the whole algorithm. 5. Repeat steps 2 through 4 a total of R times, without triggering the restart (the appropriate value for R is figured out later) 6. Measure all the variable qubits. 7. Return SATISFIABLE iff all clauses are satisfied by the measured variable values (Note that I simplified the algorithm. The paper uses ancilla bits to hold the clauses in qubits, but they are not needed because they're only measured at the end and otherwise only used as controls.) For starters, I'll just say that up front there's no way this works. It's too simple. Other researchers would have tried it. Repeatedly rotating proportional to the amount satisfied and measuring? Too obvious. I would not be surprised at all if a majority of researchers have come up with this idea, tried it, and understood why it didn't work. Grover's algorithm is more complicated than this. Anyways, why does it actually not work? It becomes clear if we simplify the algorithm a bit more by deferring the conditional restarting measurements. Instead of conditionally continuing the 2-4 loop R times, simply run Step 2 a total of R times up front. Then measure the R ancilla bits you introduced, and restart if any of them was false. This is equivalent to conditionally restarting because a) there's no information dependency between the loops beyond "don't bother doing it" and b) measurements can always be deferred until later [1]. Now make the simplifying assumption that all variable assignments, except for a single satisfying one, satisfy 7/8'ths of the clauses (based on [1]). Note that applying 7/8'ths of a NOT will transition an OFF bit into a state where it has a roughly 96% chance of being ON. Since most possible assignments are not satisfying, and non-satisfying assignments have a 4% chance of causing a restart (the satisfying assignment has a 0% chance, but it gets diluted by the exponentially many non-satisfiers), the ancilla bits' measured value will be dominated by the non-satisfying assignments. Each ancilla bit will have a roughly 4% chance of being OFF. That means the chance of not having to restart is roughly 0.96^R. But the paper says that R increases faster than linear with respect to the number of qubits. So the odds of not-restarting are upper bounded by 0.96^N. That places an exponential multiplier on the running time, because it's so unlikely to succeed as N gets large. Therefore this is not a polynomial time algorithm. 1: https://en.wikipedia.org/wiki/Deferred_Measurement_Principle https://en.wikipedia.org/wiki/Deferred_Measurement_Principle 2: https://en.wikipedia.org/wiki/Karloff%E2%80%93Zwick_algorithm https://en.wikipedia.org/wiki/Karloff%E2%80%93Zwick_algorith...