[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.
After quickly reading through the paper it seems that the
algorithm they employ is very similar to Grover search [1], which provides a quadratic/square-root speed-up for generic search problems, so O(2^m) -> O(2^(n/2)). Basically, they perform the following three steps:
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.
> 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.
The "weird trick" is that they do non unitary things via partial measurement to beat that bound.
There might well be hidden costs here. Or judging from what others have said, it might just be a more straightforward mistake.
I'm not an expert in this subject area, but I know that I've sometimes seen the phenomena that are sometimes called "wavefunction collapse" described as non-unitary (and for good reason). Even if you buy into an interpretation of QM that doesn't include collapse as a separate process (most non-Copenhagen interpretations, in other words), measurements of the quantum state will still have to somehow look non-unitary to any given observer. (Something something projection operators, in the formulation I learned in grad school.)
There are definitely some interesting tricks you can do to exploit these behaviors. (I'm thinking for example of the "quantum Zeno effect", in which one can "find an answer without ever asking the question".[0]) But I don't know remotely enough about quantum computing to know what's actually possible in this context.
How to reconcile them in a satisfactory theory is an open issue, but non-unitary measurements play a crucial role in many quantum protocols, including, for example, quantum teleportation.
Basically if we would look at the wave function of the whole universe it would always behave in a Unitarian way. Non-unitarian behavior (such as qubit readouts) are the result of coupling our -initially isolated- quantum system with an external system that has many degrees of freedom and causes decoherence in the individual components of the original system's wave function. A measurement operation in that sense is an entanglement of the original system with an external quantum system, followed by decoherence of the wavefunction due to the coupling of the external system to another one with a large number of degrees of freedom (which destroys the interference in the components of the wave function and thus turns a quantum state into a "classical" state). The role of decoherence and entanglemenr was not well understood for a long time and led to many of the seeming paradoxes of quantum mechanics, but today the theory of "open quantum systems" explains that behavior quite well and one can even simulate such systems using e.g. a so-called "Master equation" approach. What's important to remember here is that the whole system (so initial quantum system + environment) is always behaving in a Unitarian way, but this must not be true when looking at individual parts of the wave function in isolation.
> Basically if we would look at the wave function of the whole universe it would always behave in a Unitarian way.
There is absolutely no consensus on this. This is merely saying that you believe in Everett style interpretations, which have so far failed to explain the appearance of non-linear processes in quantum mechanics satisfactorily.
Decoherence does _not_ solve the quantum measurement problem. You can not derive the Born rule.
Basically what decoherence does for you is translate a quantum amplitude on the space of operators into a classical distribution on the spectrum of your coupling. It does not tell you why you are allowed to interpret this distribution as a probability distribution.
It does not tell you why you should be able to say that the state with higher amplitude is more likely to occur. In decoherence all states occur. So it is even unclear a priori what should be meant by the probability of a state occurring.
This is not my private opinion, this is the opinion of people like Zeh, who was instrumental in developing our current understanding of decoherence:
"[Decoherence] would explain why we never observe an apparatus pointing, say, to two different results, i.e. decoherence would provide a solution to the measurement problem of quantum mechanics. As pointed out by many authors, however (e.g. Adler 2003; Zeh 1995, pp. 14–15), this claim is not tenable."
> which have so far failed to explain the appearance of non-linear processes in quantum mechanics satisfactorily.
There's a famous theorem that any non-linearity in quantum mechanics (however small) would permit FTL information transfer. Could you link me one paper (either from a reputable journal or a highly cited article on the arXiv) that demonstrates non-linearity other than the exception of instantaneous collapse via measurement?
I wasn't talking about non-linearity other than the one you mention. That should be abundantly obvious from what I posted.
You can't have quantum computation without measurement, and thus without non-linearity. Quantum computation is not simply "doing the computation in each possible world", it also is some trick to extract (collapse) the information into one particular world, and I don't think we currently understand fully what that means, but it's certainly non-linear. After all the information is often in the amplitude.
Conversely there are measurement based models for quantum computation that rely purely on the non-linear process.
As far as I know it, in any recent QM lecture or textbooks a measurement operation is described as an entanglement of the original system with an external quantum system with very large number of degrees of freedom. In older texts you would just find Born's rule.
So, I don't have the theory background a PhD candidate might, so forgive my ignorance, but why would a theory be expected to build on the already proven partial results? I was under the impression their use was as a quality heuristic, not something a proof of a lower bound of the general case could make much use of.
Generally because that’s how mathematics tends to work - people publish a partial result & then they or others build on it to improve that result in various ways[1]. The authors are also usually embedded in a wider community of mathematicians who act as a pre-publication bullshit filter by asking pointed questions at seminars & that kind of thing.
It’s quite rare for a genuinely novel solution to a major problem in mathematics to spring up out of nowhere in the literature.
[1] Think of, eg, the Twin Prime conjecture (that there are infinitely many pairs of primes only 2 integers apart). For decades there was no progress on this problem, before Yitang Zhang published a paper last year proving that there were infinitely many primes less than a finite bound apart (70 million in his case). Then a horde of matheaticians attacked the problem using his & other new approaches to progressively reduce that large bound down to the point where it’s now been proven that there are infinitely many primes < 246 apart (according to the polymath group - I’m not sure whether this is a published result yet). The twin prime conjecture is in sight!
Yea, but to my understanding the partial work done thus far does not apply to an understanding of the general case solution. Let's say there is a linear solution for some form--how does that help establish a lower bound on the general form?
Recognition of past work I can understand. But it seems like occam would argue with me against the use of some of the partial results without understanding why they would be useful.
It's just an exponential overhead. The state of a quantum computer is a superposition over all bitstrings, i.e. a vector of size 2^n for n qubits, and you have to implement quantum operators by multiplying with 2^n x 2^n unitary matrices (you better do that implicitly whenever possible or it will be very slow).
After taking a lecture on quantum computing, it was actually a weekend project to implement a basic quantum simulator myself, very useful to confirm that I actually understood the model as well as I thought.
In fact, you don't even have to understand quantum mechanics to create a quantum simulator. Mostly just linear algebra, and how states evolve through time, given some Hamiltonian.
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 "!" is the "partial measurement" operator. I am not expert in the field but as far as I understand the partial measurement is to collapse the superposition to one of the states relative to its amplitude (probability), while the post-selection operation is to choose the output state regardless its amplitude (probability). For example, measurement on a qubit in state 1/sqrt(2)(|0>+|1>) might give |0> or |1> with 50% chance, while to postselect |0> is to get |0> with 100% regardless its amplitude. Postselection gives you the power to choose the outcomes of certain measurements while normal measurement doesn't give you that power.
As for "but this somehow completely failed to make waves in the community", I think "but life is too short to give my full attention to a dubious paper for more than 15 minutes" is an enough explanation.
Because experts with domain-specific knowledge tend to have better heuristics for this sort of thing than the average interested outsider. (They have to, or else they'd get nothing done except debunking flawed claim after flawed claim. Which might be worthwhile, but doesn't move the field forward.)
I've seen plenty of "theories of particle physics" that evidently look fairly plausible to non-physicists (and maybe even to non-specialists) that I can recognize immediately as crackpottery by my own heuristics (but that would take at least a weekend's work to convincingly demonstrate as such, if I wanted to invest that kind of time: I've done that, too). I'm not saying that anyone should take anyone's heuristic guesses in such cases as gospel (once or twice a century we might actually get a delightful surprise), but they can serve as a useful restraining influence if you're tempted to get excited about a headline.
An expert would be able to skim it, recognize the path of reasoning as something he's seen a before, and narrow down on the error quickly. Reasoning about something by how many "waves in the community" it has made is a deference of personal judgement to the social network an individual is embedded in, which is a useful shortcut when you are not an expert relative to your peers, but dangerous set of mind to operate in for any lengthy amount of time, as it can be the basis of cults and the like.
> An expert would be able to skim it, recognize the path of reasoning as something he's seen a before, and narrow down on the error quickly.
This is almost exactly equivalent to saying that an expert programmer should be able to determine whether an unfamiliar, complicated code base contains a bug by skimming the source. The hard bugs are going to be subtle.
Not at all equivalent, because code isn't meant to be human readable, but computer interpretable. Because of these different goals, computer code is actually quite a bit harder to read than a well structured academic paper. I think programmers have a lot to learn about logical structure from writing meant to be read by humans [1].
Note how many people on this thread seem to be understanding and discussion its contents, whereas if I were to post 13 pages of "unfamiliar, complicated code" that claimed to do something, I can't imagine anyone would help me debug it.
So then the answer is certainly "yes" with the same level of certainty that algorias is claiming. Large, complicated solutions are inherently likely to have subtle flaws.
I agree, but not all bugs are subtle. This seems to be the equivalent to someone having trouble with "hello world" because they forgot to include iostream.
I think debunking crackpottery is helpful for society, at least. I’d even argue that it helps the specific scientific field in question to move forward if the claimer is an active researcher, and is losing their time by not realizing it’s wrong. To sceptically scrutinize claims is what moves us forward. Of course, one has to choose their battle, but if those, who can, debunk crackpottery from time to time, then, I think, the general picture of science gets better. I think public interaction is important for science — the constructive lectures of what we know aswell as the destruction of false claims.
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.)
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.