9 ms·
A first for physics: Fundamental quantum physics problem proved unsolvable
- mojoe 11y agoI can't determine what the postulates are that this proof is based upon. If someone has a relatively succinct explanation, I'd appreciate it.
- mathgenius 11y agoMathematically, this is in the land of linear algebra (complex vector spaces.) The particular question at hand concerns the spectrum of a (Hermitian) linear operator, known as "the Hamiltonian". The "gap" refers to a separation in the lowest two eigenvalues ("energy levels") of this operator. It seems plausible that one could easily encode a turing incomplete problem into linear algebra (think of tensor networks, constraint satisfaction, etc.) but what these guys have done is place very strong restrictions on the form of the linear operator (in jargon: two dimensional, nearest neighbour interactions, translational invariance). This now comes near to a class of physical systems that one may hope to build, or at least understand theoretically, and the result of the paper puts a stark upper limit on what we may hope to achieve in this vein.
- hndl 11y agoThank you for this.
- colanderman 11y agoThe proof combines Hamiltonian complexity techniques with aperiodic tilings, to construct a Hamiltonian whose ground state encodes the evolution of a quantum phase-estimation algorithm followed by a universal Turing machine. Just when I thought linking quantum mechanics with Turing completeness was cool, they went one step further and linked them using aperiodic tilings.
- adrianN 11y agoTilings are a neat way to simulate Turing machines, so it's not super surprising that they show up in an undecidability proof: https://en.wikipedia.org/wiki/Wang_tile https://en.wikipedia.org/wiki/Wang_tile
- Natanael_L 11y agoNext up: tie this info cryptography and information theoretic complexity, so we can attempt to create meaningful algorithm security proofs.
- fallingfrog 11y agoSo if I'm understanding this right, they proved that you can't calculate the bandgap of some class of systems of arbitrary size in any predetermined finite period of time, right? I guess when you really think about it, the opposite finding would be much more surprising. (That you could calculate the bandgap of any system of any size in some finite time period, however large).
- martincmartin 11y agoThe finite period of time isn't predetermined, and different systems could take different amounts of time. So, its not intuitive in the way you imply.
- lorenzhs 11y agoNo, it's worse than that: From Wikipedia [1]: "In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer." The definition of algorithm includes termination after a finite amount of steps. This number isn't predefined. [1] https://en.wikipedia.org/wiki/Undecidable_problem https://en.wikipedia.org/wiki/Undecidable_problem
- sp332 11y agoIt's not a constant period of time. The amount of time is allowed to increase with the size of the system. In fact it's allowed to increase quadratically, or exponentially, or factorially, or whatever - it will never be enough. Whatever algorithm you come up with for calculating the rate of expansion, you will always underestimate the amount of time (for a sufficiently large system). https://en.wikipedia.org/wiki/Busy_beaver#Non-computability_of_.CE.A3 https://en.wikipedia.org/wiki/Busy_beaver#Non-computability_...
- jmount 11y agoSuch a statement just means they can implement computation in this formalism. Not a huge surprise as you can implement computation with many other structures.
- andbberger 11y agoYou have no idea what you're talking about. That is not what undecidable means. Also take a look at the Church-Turing thesis
- otabdeveloper1 11y ago> Also take a look at the Church-Turing thesis The Church-Turing thesis is an (unprovable) statement of faith, not a mathematical theorem. Effectively, it states that "all algorithms can be computed on a Turing machine, and vice-versa". Note that this thesis is not as radical as it first sounds; I'm assuming that if we ever do find a way of computing functions that cannot be computed on a Turing machine, then we'll just call it something else, not an 'algorithm'. This would make the Church-Turing thesis just a tautological circular definition.
- javra 11y agoWell, normally one makes the thesis concrete by saying that lambda calculus and Turing machines yield an equivalent notion of computability.
- jimhefferon 11y ago> it states that "all algorithms can be computed on a Turing machine, and vice-versa". It is about algorithms of a certain kind, the kind of computation that we do when we, say, factor polynomials or check a step in a euclidean geometry proof. That is the kind of computation called for in the Entscheidungsproblem. Turing's analysis of that kind of computation was very persuasive, and consequently influential. But as to whether there is more, whether we can go farther with some kind of analog computation involving lasers and interference, or some kind of quantum stuff ... well, maybe. It doesn't seem impossible that Turing, in the 1930's, lying on the grassy river bank after a hard run and reflecting on what a device can compute, did not imagine it all. To date (as I understand it) no analysis of what can be done with a real device under current physics has for the community of experts the same persuasiveness of Turing's work. This paper seems to me to at least hint that there may be things that nature computes, but which no Turing machine can compute. It makes me wish to understand the physics.
- drdeca 11y agoWait, Does that imply that it could be possible to construct a system which gives uncomputable results? Does it assume an infinite plane or something? (Assume might be the wrong word) Because, if there's something uncomputable, due to halting problem, how does that fit with the bekenstein bound?
- mathgenius 11y ago> Does that imply that it could be possible to construct a system which gives uncomputable results? They produce a family of systems for which it is not possible to construct an algorithm that can yield a certain property (being gapped) of each system. > Does it assume an infinite plane or something? (Assume might be the wrong word) Yes. The system is infinite. (Or, take a limit as the system size grows to infinity.)
- misja111 11y agoBut spectral gaps do occur in nature. Does that mean that even though it is impossible to compute if a spectral gap will occur or not, we could just observe such a system in nature and that way we could build a computer which would compute uncomputable results?
- mathgenius 11y agoI think not, since these systems are "infinite", ie. you would never know how big to build it before you got close enough to the correct result.
- sharpneli 11y agoIn nature it does not matter if the spectral gap is really tiny. It's de facto without spectral gap if it's just small enough. Whereas for this particular decision problem the mere existence of spectral gap matters.
- selimthegrim 11y agoWho says? Graphene gaps, (it must gap) even though its so small it's impossible to observe in practice. This had very important consequences for topological materials theory...
- mathgenius 11y agoLong version: http://arxiv.org/abs/1502.04573 http://arxiv.org/abs/1502.04573 Short version: http://arxiv.org/abs/1502.04135 http://arxiv.org/abs/1502.04135
- Confusion 11y agoReminds me of an adage I once read and have taken to heart (but I can't recall the source and I'm paraphrasing): what is impossible in theory is often not nearly as interesting as what is possible in practice.
- JoachimS 11y agoBut, but, but - what if I use a D-Wave machine to solve it? ;-)
- kefka 11y agoI know you jest, but is there a proof (or good hypothesis) that allows one to convert a formula to an appropriately sped-up version quantum optimized algorithm? Compare the Sieve of Atkin to Shor's algorithm, for what I am referring to.
- tgb 11y agoMy understanding from reading Scott Aaronson, is that his belief is that most algorithms will not have significant speedups as a quantum algorithm, and that the currently known algorithms with large (exponential) speedups aren't very useful in the sense that they're just breaking cryptographic problems which were used solely because they were hard to break. In other words, don't expect everything to have a Shor's algorithm analogue.
- TheOtherHobbes 11y agoThen you find it's undecidable a million times more quickly.
- incepted 11y agoUncomputable or unsolvable?
- pygy_ 11y agoUndecidable. https://en.wikipedia.org/wiki/Undecidable_problem https://en.wikipedia.org/wiki/Undecidable_problem See here for a concrete example of a similar problem (props to adrianN for the link in the first place): https://en.wikipedia.org/wiki/Wang_tile#Domino_problem https://en.wikipedia.org/wiki/Wang_tile#Domino_problem
- jordigh 11y agoThese two are roughly the same thing. Formally, a proof is just a computation within an axiomatic system. A computation is just transforming one expression into another according to a set of rules. Whether this transformed expression is an algebraic or a logical formula is not a huge difference. In terms that may be more familiar to programmers, lisp's homoiconicity of data and code corresponds roughly to how Gödel was able to express logical formulae as arithmetic statements via Gödel numbering. Once you are able to encode logical formulae as natural numbers, you can then use laws of arithmetic (e.g. Peano's axioms) to compute/prove other statements/numbers.
- littletimmy 11y agoThis might be an ignorant question, but can one still force a decidable solution by assuming a stronger set of axioms? And if so, does this undecidability have any physical significance?
- jordigh 11y agoYes, you can add more axioms, but your new system with more axioms will have other undecidable statements. I don't know much physics, but my interpretation is this: we have a mathematical model of physics in which we have found a "naturally-ocurring" undecidable statement (scare quotes because most famous undecidable statements were specifically constructed to be undecidable). This does not really say anything about the natural world, merely that our mathematical modelling of it is incomplete, but it always must be incomplete.
- noobermin 11y agoIs it really impossible to have some system of axioms where most statements you care about (ie. can make a physical experiment out of) can be decided? If you can't measure something (ie., decide it someway from your theory or leave it as a free parameter), it's not science, string-theory nonwithstanding.
- jordigh 11y ago> Is it really impossible to have some system of axioms where most statements you care about (ie. can make a physical experiment out of) can be decided? Of course it's possible. Most statements we care about are decidable. Otherwise, mathematics would be pretty hopeless. :-) It's just that any system has undecidable statements, as long as it's strong enough to do arithmetic. That's Gödel's theorem.
- noobermin 11y agoI know due to Godel in principle that a logical system can't be complete, but science is a little more specified beyond just logical consistency, it has to be experimentally verifiable, which is a constraint that the mathematics used by science doesn't have. What I'm hinting at is there is a subset of logical statements that the mathematics of science contains defined by the set of experimentally testable statements, and this subset is decidable given independent axioms and free parameters. EDIT: to expand upon this further, things like the continuum hypothesis are interesting from a mathematical perspective, let's say I'm Godel and I assert that CH is false and there is some set A "in between" the reals and N in cardinality. However, if my friend Enrico Fermi wants to do experiments and he wants me to do a calculation, I won't use elements from A because it wouldn't be useful for his experiments in with particle physics. Worse, I can't even use all the real numbers, because he'll need numbers he can compare to his measurements, so I'm restricted to a countable subset of even the reals, and of course, I'm restricted to using statements from the decidable subset of mathematics. There's a big difference between what mathematics is capable of saying and what we observe in the real world. Even if the real world had a set of undecidable facts, the fact that the only way science can understand it is by experiments restricts falsifiable scientific statements to a subset of mathematical statements which is incomplete (because of the need of axioms and free parameters like the mass of particles or their charge, fundamental constants, etc), but decidable within it's axioms, because otherwise, it's not testable and it's not science.
- fitzwatermellow 11y agoCompanion article to original paper: Paradox at the heart of mathematics makes physics problem unanswerable: Gödel’s incompleteness theorems are connected to unsolvable calculations in quantum physics. http://www.nature.com/news/paradox-at-the-heart-of-mathematics-makes-physics-problem-unanswerable-1.18983 http://www.nature.com/news/paradox-at-the-heart-of-mathemati... Toby Cubitt, a "quantum-information theorist" at UCL should win this years relevant username contest ;)
- pavel_lishin 11y agoA great example of nominative determinism.
- ethbro 11y agoTo be fair, his name only collapsed into a determinative state once we looked at it in the context of this article. /pun
- fspeech 11y agoThanks! The companion comment also provides a link to the non-paywalled and full arxiv version: http://arxiv.org/abs/1502.04573 http://arxiv.org/abs/1502.04573
- maxander 11y agoThe companion made clear something that the (abstract of) the original post didn't; this sort of system can't be used to physically perform "hypercomputation," since encoding an undecidable problem requires an infinite lattice. Ah well.
- j2kun 11y agoIt's nice that they showed this for the problem of finding the ground state of a Hamiltonian, but we already knew the axioms of quantum computing encode undecidable problems because it includes all of classical computing.
- clebio 11y agoThe post and linked article titles don't match at all (??).
- hasenj 11y agoSince physical states exist in reality, it makes no sense to me that a physical problem is not mathematically decidable. The only way a problem is mathematically undecidable is when it's malformed (i.e. non-sensical).
- nsns 11y agoBut surely, any physical state would be available to you only as a representation, and not directly. Meaning, that in order to make it decidable, you'll probably have to look at it differently.
- stillsut 11y agoI've wondered if this can go the other way as well: e.g. "If Golbach's conjecture is true, then FTL signalling is possible. Since physics says FTL is impossible, then GC must be false" [If you could reduce GC to a scheme for moving information via quantum entaglement. I use GC as an example because it is famous and an unproved, but maybe a better example is the Erdos Discrepancy [0] which makes statements about aritrarily long sequences in {1,-1} just like sampling quantum states!] [0]: http://arxiv.org/abs/1509.05363 http://arxiv.org/abs/1509.05363
- NickM 11y agoI think most mathematicians would not accept something like that as a proof. Our understanding of physics is based on real-world observations and experiments in a way that math is not.
- swehner 11y agoI can't tell how much of this is "quantum physics" and how much is "mathematical theory that also arises in quantum physics". As in, I doubt their construction allows "building something" which then allows solving a conventionally unsolvable problem. With new physics you may be able to build machines that can compute more; however I don't think they are talking about such physics here. But, they do quote: Marian B. Pour-El and Jonathan I. Richards. Computability in Analysis and Physics. Springer, 1989. M. B. Pour-El and J. Richards have earlier results: http://www.sciencedirect.com/science/article/pii/0001870881900013 http://www.sciencedirect.com/science/article/pii/00018708819...: The wave equation with computable initial data such that its unique solution is not computable (1981) http://philpapers.org/rec/POUTWE http://philpapers.org/rec/POUTWE: The wave equation with computable initial data whose unique solution is nowhere computable (1997) The Spectral Gap authors seem to call these results "easier" (page 8 at http://arxiv.org/pdf/1502.04573v2.pdf http://arxiv.org/pdf/1502.04573v2.pdf)