Slashdot Mirror
A Quantum Linear Equation Solver
joe writes "Aram Harrow and colleagues have just published on the arXiv a quantum algorithm for solving systems of linear equations (paper, PDF). Until now, the only quantum algorithms of practical consequence have been Shor's algorithm for prime factoring, and Feynman-inspired quantum simulation algorithms. All other algorithms either solve problems with no known practical applications, or produce only a polynomial speedup versus classical algorithms. Harrow et. al.'s algorithm provides an exponential speedup over the best-known classical algorithms. Since solving linear equations is such a common task in computational science and engineering, this algorithm makes many more important problems that currently use thousands of hours of CPU time on supercomputers amenable to significant quantum speedup. Now we just need a large-scale quantum computer. Hurry up, guys!"
I'll wait until I can program in VB. Will it take long?
Any life is made up of a single moment, the moment in which a man finds out, once and for all, who he is.
Maybe you should READ the damn thing and notice how that's addressed in the first half-page.
When the Prime Minister asked him about a new discovery, "What good is it?", Faraday replied, "What good is a newborn baby?"
Any life is made up of a single moment, the moment in which a man finds out, once and for all, who he is.
You think that quantum computers are not able to justify grants or PhDs? What world are you living in?
Yeah, because classical computers were never useful to anyone (or anyone important) until datacenters existed.
And until then, developments that bring us closer are irrelevant? Applications that could give us more reason to develop the technology are pointless?
What exactly is your point here?
It's not a 'new toy' for computer science. Computer science has pretty much nothing to do with it. Mostly, it's a toy, or rather, academic persuit for theoretical physicists.
You will not be seeing Quantum Computers taking over general-purpose computing tasks anytime soon. Personally, I'm very skeptical to whether we will ever see such a thing happen. Because it will almost certainly never be easy and affordable to deploy; because I very much doubt you could ever get the necessary long decoherence times required for a quantum computer of any size to work, in an easily achievable environment. (by which I mean something approaching room temperatures, for instance).
IOW, a computer that's a fancy elaboration on an NMR machine will never be a easy nor affordable.
I see your point, but think conversely: I make a quantum computer that's cheap enough to fill a data center but there's no algorithms out there? What use is it? We need the physicists our there making the quantum computers and we need the computer scientists out there developing the algorithms. One without the other is useless. Also think of this: Dijkstra's "Go To Statement Considered Harmful" was published in the late 60's, there weren't many cheap computers to fill data centers then. He was working on the theory of algorithms not worrying about how to actually implement it. The same thing here, there are people working on the theory of these algorithms, other people will worry about actually using it when the time come.
I know quantum is the 'new toy' in computer science, but seriously, until these quantum computers exist and are cheap enough to fill datacentres with, no-one outside of academia is going to get any useful work from them.
Er, yes. If there aren't any quantum computers then quantum computers aren't useful. That's not the point of this work. The point of this work is primarily to present a new algorithm for which quantum computing shows exponential speedup, which is an interesting theoretical issue in computer science. If quantum computers ever become practical, then this algorithm will be too, but no one has claimed that this algorithm is useful today. (The submitter noted explicitly that it is not.)
The summary cleverly omits that solving a linear equation is neither NP complete nor NP hard, the speed up is from O(n) to O(log n). I think you'd need a ginormous matrix for this to be useful depending on the constants and such (Of course it'd be crime for me to read paper instead of the abstract to actually find out the details). They already have the applications for quantum computing, it will be much more interesting when they actually figure out a way to build the damn things.
I'm sure it's still a significant result and there's a good chance they did something new that can be used in other applications.
Has anyone spoken on its applications vis-a-vis cryptography and cryptanalysis?
Submission as evidence constitutes plaintiff and/or prosecutorial misconduct.
Yes, because all quantum algorithms are hugely practical these days...
It's not a 'new toy' for computer science. Computer science has pretty much nothing to do with it. Mostly, it's a toy, or rather, academic persuit for theoretical physicists.
No, it's of real interest to theoretical computer science. Quantum computing defines a new class of algorithmic complexity: there are, for instance, sub-exponential quantum algorithms for problems which have only exponential-time classical solutions. There is a whole subindustry of algorithmic complexity theory devoted to exploring the differences between algorithms that can be executed on quantum computers and those which are executed on classical computers. Scott Aaronson's lecture notes are a good introduction to this subject.
I could just as well argue that there is nothing useful about developing quantum computers until we have programs we can run on them.
This is not tangential science. The is the real groundwork for the development of the new technology. Without this sort of work quantum computers will simply never exist.
So pointing out its lack of present utility is like pointing out that after laying the foundation for a house that you still have nothing to live in. That may be true, but in so far as the initial step is pre-requisite to your ultimate goal, it is erroneous to dismiss it as 'not useful.'
When things get complex, multiply by the complex conjugate.
This has been covered in another article
Any life is made up of a single moment, the moment in which a man finds out, once and for all, who he is.
Shor's algorithm (explicitly mentioned in the summary) is an old quantum algorithm to factor primes.
Maybe it's just a story, but I've read something about Faraday that made me think about what you've written.
When the Prime Minister asked him about a new discovery, "What good is it?", Faraday replied,
"What good is a newborn baby?"
Wrong, actually it was in reference to his new electric motor, and the proper quote is 'When asked by the kind what use it was, Faraday replied, 'One day sir, you may tax it'.
Note also at that point the electric motor existed, quantum computers do not, not in any useful sense.
A learning experience is one of those things that say, 'You know that thing you just did? Don't do that.' - D. Adams
Are arXiv articles peer-reviewed?
If not (as I suspect), that puts a serious question mark on them. On the other hadn, there are excellent non-peer reviewed scientific articles - and almost all the scientific articles produced in Europe before the 2nd WW were not peer-reviewed (back then that was an american practice, and a very good one I would add). However, nowadays peer review is a valuable and available resource that should be utilized.
THAT SAID again... some of the best, most innovative scientific articles are not being, nowadays, accepted for publication because the reviewers are one degree too dumb for the article. Eventually they do get published, but with an unnecessary 5-6 year delay.
Also, I have read in my life thousands of published peer-reviewed articles, and many of them contain incredible imbecillities where I have to question whether all the reviewers were high on hallucinogens. Very very high on hallucinogens.
"The agriculture ministry is not in charge of Gundam" - Japanese ministry official.
I think he liked to say things like those, because I just found a page quoting him just like I said.
Any life is made up of a single moment, the moment in which a man finds out, once and for all, who he is.
Finally a cool article on /. This is extremely cool! There are a lot of problems in the real world that have extremely large sparse matrices that need to be inverted. Fluid dynamics and solutions to Maxwells equations come to mind. But I am sure there are other applications in relativity and plasma physics. Estimating a solution to a linear dynamic system of say 2^128 degrees of freedom in only 128 cycles would change a lot of things.
And... Yes, we are working very hard on building the computers.
You think that quantum computers are not able to justify grants or PhDs? What world are you living in?
One where I read peoples comments properly before replying to them. I did not say that at all.
Yeah, because classical computers were never useful to anyone (or anyone important) until datacenters existed.
We use datacentres *now* we didn't use them before. These days people in the real, working world need access to computing power in ways that we didn't before. I am talking practicality. The kinds of applications that get companies investors.
And until then, developments that bring us closer are irrelevant? Applications that could give us more reason to develop the technology are pointless?
What exactly is your point here?
Irrelevant is not the same as useless. It is, 'a lack of relevance', look it up. Academia will continue to explore the issue, but until we see deployments of quantum computers in large enough numbers to start basing the computer 'economy' on them they lack real world relevance.
A learning experience is one of those things that say, 'You know that thing you just did? Don't do that.' - D. Adams
Does this mean they can solve P=NP?
Yes: N=1.
Do you realize, that until they begin solving these problems in academia that there will be no industry-ready solution? I mean this is a whole new advent of computing really with three-dimensional processors coming online at around the same time we may see the same sort of increase in computational power that they did with the first electric computers.
This are some workable challenges that lay ahead in the next few years.
1. Not only will a lot of algorithm design need to be hacked out but I think Quantum Computing needs its own language to really shine and that can be worked on now.
2. A lot of work can be made possible with a clever and cheap single or dual qubit hardware solution that is yet to be designed. Please make the connection USB. The boys and girls down in applied physics may be able to help you. Like Morlocks they usually are underground and desire a eloi/hippy for snackerfice.
3. The ability to run an exponentially greater amount of calculations is going to lead to revolutionary engineering breakthroughs across the board. Lattice work in concrete is particularly linear, curvilinear or hodge-podge; now imagine lattice inside a concrete pylon like a fractal tree, it could be made to withstand force vectors that would turn a standard pylon to dust, sure we have the computing power to do a pylon like that now but not all the components of a 1000 story building.
An Education is the Font of All Liberty
So please cite this as "Harrow, Hassidim and Lloyd" and not "Harrow and coauthors."
That said, we're pleased about that attention. :)
In response to one question: the matrix inversion problem for the parameters we consider is (almost certainly) not NP-complete, but instead is BQP-complete, meaning that it is as difficult as any other problem that quantum computers can solve. We plan to update our arXiv paper shortly with an explanation of this point.
I for one cannot wait until all the appropriate reading materials come out: Knuth's Fundamental Quantum Algorithms, Quantum Algorithms for Dummies, and Quantum Algorithms in a nutshell. :)
Or if P=0, in which case N can be any number.
For large sets, this will be our guide even unto death, for the LORD will work for each type of data it is applied to...
To rephrase the other response, log vs. polynomial is the same as polynomial vs. exponential. Moving from polynomial time to logarithmic time is an exponential speedup (just as is moving from exponential time to polynomial time is).
O(n^3) vs. O(log n)
->
O(exp(n^3)) vs. O(n)
That implies putting the results of a physical measurement on equal footing with 'classical' methods, i.e. what can be done using pure math. If you do that, I think you're turning Computer Science from having been a branch of Mathematics into some completely different animal.
Algorithms are math. They can be proven mathematically, etc. These 'quantum algorithms' are something different - even if they're derived mathematially (which is how physics works nowadays), they're essentially a statement of: Put this physical system in a certain state letting certain properties of the system represent your input. Manipulate it a certain way, and the 'algorithm' shows us that you can achieve a resulting state which - probabilistically - provides a measurable value representing the result of the 'calculation' you wanted to perform. It is not mathematically proven or provable (beyond the proof that the most probable state is the desired result).
Which makes the methods essentially heuristics, not algorithms. And while that's perfectly good and useful for doing calculations and getting results, it is not a new kind of math, or any kind of math.
In this case, when A is sparse and well-conditioned, with largest dimension n, the best classical algorithms can find x and estimate x^\dag M x in O(n) time
First of all, "with largest dimension n" means nothing because if we are solving a linear system, we need A to be square. Then, the complexity of the best classical algorithms does not depend only on the size "n" of the matrix but also on the number "nnz" of non-zero entries.
My first program:
Hell Segmentation fault
In O(log n) time he can't read the entire article.
It's not completely addressed or at least all the implications are not spelled out. They talk about dealing with sparse matrices but they would have to be O(log n) sparse to be useful for a single application of the algorithm. For example, a matrix with n=1000000 would have to have around 15 non-zero values and a trillion zero values. I don't know if that's practical.
It still might be useful if one needs to perform the operation repeatedly say for an iterative algorithm. As long as one only loaded the O(n) data once. However, I doubt that is likely for quantum computers since one probably needs to reset the quantum state. However, perhaps the algorithm can be adapted to solve iterative problems.
Chris Mesterharm
I read an autobiography of Benjamin Franklin which said that when Franklin was in France either negotiating the Treaty of Paris (that's the one where England actually recognized the USA as a separate country, ending the Revolutionary War), or maybe he was still just getting the French to back us, he was observing one of the first balloon flights of the Montgolfier bros, and someone wondered aloud what good was it, and his reply was "What good is a newborn baby?"
BTW, I don't have "heroes", but if I did, Franklin would be my nr 1.
In theory, theory and practice are the same; in practice they're different. (Yogi Berra & A. Einstein)
So you're basically saying that probabilistic computation isn't math? That doesn't make any sense. Just because we have computers that are extremely reliable doesn't mean that probabilistic methods are unimportant. Quantum computers are showing us that they are.
Richard Feynman would disagree. Please read his work on the Manhattan project.
Mad Software: Rantings on Developing So
Eh, in that case your post is irrelevant. It amounts to saying "Until we have x, people won't be able to use x, so it will only be of interest to people studying creating x". It goes without saying, and people on Slashdot are clearly interested in this.
That depends. What is its tensile strength?
Oh come on, this deserves +P Funny.
They talk about dealing with sparse matrices but they would have to be O(log n) sparse to be useful for a single application of the algorithm. For example, a matrix with n=1000000 would have to have around 15 non-zero values and a trillion zero values.
Wrong. An upper bound in big O notation does not give any indication as to constant factors of the "real" bound (nor to other summands which are in o(log n)). In fact, your statement doesn't even make sense, because it is an asymptotical bound and hence can't be applied to a fixed size of the input size.
If you think quantum computing is about putting a physical system in a certain state and manipulating it, then you should also think classical computing is about setting a tape in a certain way and manipulating it.
When Turing first described a computer (a turing machine), it was essentially a mechanism where you put a tape in a certain state, manipulate it according to certain rules and in the end you get the tape in another state containing the "result" of your computation. What was so interesting about it it that it was theoretically possible to build a machine that would be able to do the manipulations automatically.
Quantum computation is analogous: get a certain vector in an n-dimensional Hilbert space, multiply it by these certain matrices in this specific order, and in the end you get a vector that corresponds to the "calculation" you did. This is absolutely only math, it has nothing to do with physics. What's exciting about this is that we expect to be able to build (real) machines that perform these operations way faster than any computer today can, because the specific operations with which be built our algorithm are exactly the things nature is capable of doing fast.
Of course, we only discovered this when we discovered quantum mechanics -- that's the relation to physics.
Did you know that the foundations of computer science were laid down before the existence of the first electrical computer?
Did you know that, when electrical computers came into existence, having this science all laid out already was actually pretty useful? Kept people from standing around going "Okay now what do we do?" for several years.
In short, your view of utility is short-sighted and lacks vision.
The enemies of Democracy are
It's an example, to give a feel for the order of magnitude. If the particular constant was very large, one would have to increase n to show the same effect, but the idea would hold. In addition, it has nothing to do with my argument. You can mentally delete that sentence if it bothers you. It has no impact on my point.
Chris Mesterharm
Can we have a Quantum Linear Racist Resolver? This guy need help!
Am I eval()? - http://www.monst3r.com.br
First, go read the paper and then say that it doesn't contain "any kind of math."
Second, explain how shooting electrons through doped silicon crystal gates, and then measuring the voltage across the end terminals isn't a physical measurement being put on equal footing with "pure math." I think that it is, so deterministic algorithms aren't algorithms either by your definition.
Third, you're wrong. Lets take a 65536 bit long encryption key, the product of two very large primes. Lets factor them! The best known deterministic algorithm is going to take longer than the universe will last. But I bet it takes well under a second to check an answer for correctness! Let's say you have a quantum "algorithm" Q. You are correct, you can't prove Q(key) will produce the correct factorization. But you can CHECK it in only a second. So, run Q(key) until your check passes. There, that's an algorithm by your definition. You just used math to prove that if you run your quantum + classical hybrid computer on that input, it will always output the correct result.
Fourth, an algorithm isn't a mathematical statement, stop redefining words just so you can get all riled up with righteous indignation. An algorithm is near universally defined as "a finite sequence of computational instructions, usually towards the end of computing a certain value or accomplishing a certain task." It's useless if you can't mathematically prove something about the answer. Deterministic algorithms you can always prove the answer is right (hopefully?). With randomized algorithms, you can mathematically prove that the answer is right too (in most cases) but not how long it takes. Conversely, you can usually also prove that it takes a finite amount of time, but then you can only prove a bound on it's probability of success, rather than being 100%. You're saying that it's "pure math" to prove (using math) that a sequence of instructions computes a correct answer in 1 year deterministically, but it's not pure math to prove (using math) that a sequence of instructions computes a correct answer in 1 year with probability of 1 - 1e-900. I submit that while the two are different proofs, for all intents and purposes, the two algorithms are equivalent, since you cannot have a computer that runs with 0 probability of errors, deterministic or not.
ASCII stupid question, get a stupid ANSI
I don't have a clue what a quantum linear equation is or why I'd need to solve it, let alone know how to.
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
What kind of side effects will a progress bar have since you can't know what its doing if you know where it is?
If someone is passing you on the right, you are an asshole for driving in the wrong lane.
He's my number 1 for being a genius AND a manwhore.
RSA security is dependent on the difficulty of factoring large primes, and this seems like it would reduce the time required to solve the problem considerably.
Factoring primes is the easiest freaking thing in the world.
Give me a prime, any prime. Ok, its factors are it and 1.
Perhaps someone more versed in mathematics can shed some light on this.
HTH HAND.
A cool algorithm that should be possible on a quantum computer is "perfect" data compression. IOW, "what is the smallest turing machine + input string that outputs the following string in less than 1 billion steps?"
Such an algorithm would need a quantum computer to run, but the decompression could happen on a classical computer.
Anyone aware if such an algorithm exists? The summary would seem to indicate not.
This looks like a really interesting result, but having look a little at the paper it's not 100% clear to me what the quantum algorithm is being compared to. First a caveat, I study quantum physics but not CS, so my knowledge of algorithms and complexity theory is quite limited. Anyway, in solving problems on a good old classical computer, you can seek to solve a linear system exactly (up to the bounds of finite arithmetic) or you can seek to solve it approximately to within some error.
So the thing I'm wondering is what classical algorithm are they comparing their result to, and is this comparing apples to apples? They say
So it looks like the authors' algorithm gives an approximate solution to the linear system and they're comparing it to a classical algorithm that gives an exact solution to the problem. This seems like comparing apples to oranges. Perhaps someone who knows more about the features of the various classical algorithms can comment on whether it looks like the correct comparison to make and why.
I bring this up because I recall that given a matrix representing the density matrix of a bipartite quantum system, determining whether it represents an entangled or separable quantum state is in general NP-Hard, but IIRC there exist semi-definite programming techniques to get the answer probabilistically in polynomial time. The point is that in that case there's a big gain for accepting an answer that will be wrong every once in a while. I was just curious if settling for an approximate answer in solving linear systems changes the complexity of that problem drastically as well.
"You call it a new way of thinking; I call it regression to ignorance!" -- Operation Ivy
If you do that, I think you're turning Computer Science from having been a branch of Mathematics into some completely different animal.
Algorithmic complexity theory has always depended on what you define a "computer" to be. An algorithm is an algorithm, but its space and time requirements require assumptions about what is executing the algorithm. That doesn't mean that the algorithm is non-mathematical. It means it uses different assumptions about what a computer is. That doesn't make quantum computing any less mathematical than classical computing. It just makes the mathematics different.
It is not mathematically proven or provable (beyond the proof that the most probable state is the desired result).
Non-deterministic algorithms have probabilistic correctness guarantees, not absolute guarantees. That's one of the reasons why they're theoretically interesting to computer scientists.
And while that's perfectly good and useful for doing calculations and getting results, it is not a new kind of math, or any kind of math.
Of course it is math; just read any paper on the subject, or the lecture notes I linked. The mathematics of quantum algorithms is different from the mathematics of classical algorithms. That's why they have different computational complexities.
I don't see a big difference in mathematical content between "if you start with this state, and perform these transformations you will have this other state" and "if you start with this state, and perform some transformations, then you will have this other state".
Those are descriptions of classical and quantum algorithms, basically.
Now the only question is how to translate the final state into "the answer". In the case of classical algorithms the translation is usually very simple. In the quantum case, the final state is a probability distribution, and "the answer" is the mean of the distribution.
That's if you're talking about the computer science aspect of the whole thing. If you're talking about actually building a computer, that's a different story, and you need to worry about your distribution's standard deviation, etc, but let's not mistake that for the theory part.
I should note that there is a long tradition of probabilistic algorithms in classical computer science, by the way.
I should also note that probability theory is generally considered "pure math".
No. Or, not to the best of our knowledge.
Quantum computers solve problems in BQP. We don't even know if that is any larger than BPP, the probabilistic algorithm class.
We also do not know if there are any problems in BQP that are not in BPP; that is, we do not know if a quantum computer can solve any problems a classical computer (with a random source) can't.
We *do* know that there are problems for which the solution with a quantum algorithm is exponentially better than any known solution with a probabilistic classical algorithm (Shor's factoring, and TFA). Since we happen to also care if a problem is solve in a day or in the age of the universe, instead of just whether the problem is solved at all, this matters a great deal.
Third, you're wrong. Lets take a 65536 bit long encryption key, the product of two very large primes. Lets factor them! The best known deterministic algorithm is going to take longer than the universe will last. But I bet it takes well under a second to check an answer for correctness! Let's say you have a quantum "algorithm" Q. You are correct, you can't prove Q(key) will produce the correct factorization. But you can CHECK it in only a second. So, run Q(key) until your check passes. There, that's an algorithm by your definition. You just used math to prove that if you run your quantum + classical hybrid computer on that input, it will always output the correct result.
Well, technically all we know is that it will never output an incorrect result. It could just continue to run until the sun goes nova, though of course this result is vanishingly improbable. Not that I disagree with your main point at all, I just like nitpicking!
That said, I think what the GP is concerned about is that with traditional algorithms you can, if you have enough time and paper, sit down and follow the same steps the computer does to do the calculation by hand. What he doesn't realize is that Quantum algorithms can also be performed on pencil and paper, they would just be extremely inefficient without the particularities of the hardware of a quantum computer.
That's like saying GPGPU is useless, just because GPUs are not very useful for serving web content, or files, or being used for databases (what fills most datacenters). They are great for some (not all) HPC applications, though. A practically useful quantum computer, even if unbelievably expensive, would still be useful for those things that quantum computers do exceedingly well. In the 50s, a small firm would never get a computer to replace accountants. Government agencies and some companies would still get them for the most demanding computation tasks of the time. As a quantum computer moves us firmly outside the von Neumann paradigm, and to some degree outside Turing as well, we can't just look at the cost and whether large deployments are feasible, because even one machine will be useful for those tasks that no machine, or only a million or more machines, can do within a realistic amount of time today.
To clarify:
O(n) vs. O(log n) -> O(2^n) vs. O(n)
"If a nation expects to be ignorant and free in a state of civilization, it expects what never was and never will be."
Is it white? No. Is it black? No.
Actually, it's the next president.
At the very least it can be regarded as pure math, and it can be quite interesting.
On the other hand, the fundamentals of quantum mechanics are still very muddy, quantum measurement is very un-well-defined, nobody has any idea how many qubits you can put together before the system becomes a decoherent macroscopic classical system. Are quantum computers even *theoretically* possible? Or are there some basic laws of nature that deprive Human the access to the computing power that Universe obviously posesses?
You're both wrong. They're equivalent.
From wikipedia:
"A Turing machine can simulate these quantum computers, so such a quantum computer could never solve an undecidable problem like the halting problem. "
This is not the greatest sig in the world, no. This is just a tribute.
Here is a long list of problems that have superpolynomial i.e. more than polynomial speedup compared to classical computation. Even though the author doesn't think so many do have practical applications.
"All cats are gray in the dark."
(Franklin on the advantages of older women. He wrote a whole essay on the subject. His basic thesis was that the "juices" -- I think that was his word -- move down in the body as a woman ages...)
The weak point to me is where they "map A to a quantum-mechanical operator". They completely ignore the timing of this step, which amounts to assuming assuming that multiplication by A takes time O(1). With that assumption I'm sure you can do linear algebra blazingly fast.
In quantum computing, (O)(o) reads you!
That doesn't make sense. But the smiley is nice.
NB: The message above might reflect my opinion right now, but not necessarily tomorrow or next year.
Where is the on-line version of the 'Quantum Linear Equation Solver' built with hookers and blackjack?
Sig this!
Like all real mathematicians, I solve my quantum linear equations by hand.
Except there are white urban thugs too... Don't even bring race into the matter. Direct your hate at thugs, not a race.
A nitpick to avoid confusion: the above comment is talking about the efficiency of computers. So, you should read
Quantum computers solve problems in BQP.
as "Quantum computers efficiently solve problems in BQP" (that is, by the way, the definition of BQP). Ditto for the following paragraph: "we do not know if a quantum computer can efficiently solve any problems a classical computer (with a random source) can't (solve efficiently)."
It also seems a little nonsensical to ask if a quantum computer can solve P=NP. "P=?NP" is a mathematical question, so this is like asking if a quantum computer can prove Fermat's Last Theorem. I think the parent poster sensibly interpreted the question as "does this mean quantum computers can (efficiently) solve NP-complete problems? (That is, does BQP contain NP?)".
"so this is like asking if a quantum computer can prove Fermat's Last Theorem. "
Any hopes for a speed-up on Automated-Theorem-Proving?
It's not a question of computability, it's a question of efficiency (time complexity).
Nondeterministic and deterministic Turing machines are also equivalent in the power of expression, but most likely not equal in terms of time complexity (otherwise P=NP).
Also, I have read in my life thousands of published peer-reviewed articles, and many of them contain incredible imbecillities where I have to question whether all the reviewers were high on hallucinogens. Very very high on hallucinogens.
Could someone mod the parent up +1 whatever [insightful, informative, funny - really, a "tragicomic" mod point would be most appropriate here].
Back in the day, Goro Shimura used to say that something like 50% of all published mathematics is simply rank nonsense, but these days, I'd say that the proportion is closer to 99%.
You miss the point entirely. Turing's machine _always_ gave the same result for the same data and could be mathematically proven to do so.
You can NOT predict the result of a quantum 'calculation'. You can predict the _probabilities_ of the various possible results.
This abandoning of what is mathematically provable is not a casual thing.
Any hopes for a speed-up on Automated-Theorem-Proving?
Automated theorem proving (using propositional calculus) is NP-complete, so it's the same "no, to the best of our knowledge". (Using first order predicate calculus is even worse -- the algorithm is not even guaranteed to terminate).
Ah, so your problem is not with physics, but with probability.
The thing is, there's no "abandoning of what is mathematically provable" in studying probabilistic algorithms. Computer science has studied for decades complexity classes like BPP (bounded-error, probabilistic, polynomial time) which contains many useful algorithms, like for instance the Miller-Rabin primality test, which is used by OpenSSL to check if a number is prime.
So, whether you like it or not, it's already part of computer science.
I think reviewers should be held accountable in some way.
Quis custodiet ipsos custodes?
The truth of the matter is that the problem is inherently intractable.
If you have good people writing papers, then you will get good papers.
If you have lousy people writing papers, then you will get lousy papers.
What people need to realize [and what almost all people in the grant-writing racket lack the strength of character to admit] is that most published "research" is simply false.
And if to "false" you were to add "trivially tautological or essentially meaningless" then you would have classified almost all of published "research" nowadays.
But the grant-writing racket is very powerful politically, and the milk from the teat of that sow tastes oh so good...
What an excellent reply !
I don't think this is nitpicking at all, on the contrary, this is absolutely essential
It is one thing to wonder is P=NP, another thing to not be bothered by whether it is true or not by 'magical' quantum tricks that will basicaly void the interest of the P=NP question for practical ends, and it is yet an entirely different thing to use this to conclude the original question.
Your reply is very insightful, I got confused by the previous answer because I fell for the same trap in confusing the interest of the question with the question itself. thank you very much for putting me back in the right track, really !