4 ms·

The proof combines Hamiltonian complexity techniques with aperiodic tilings, to construct a Hamiltonian whose ground state encodes the evolution of a quantum ph

The 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 ago
Tilings 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 ago
Next up: tie this info cryptography and information theoretic complexity, so we can attempt to create meaningful algorithm security proofs.
fallingfrog 11y ago
So 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 ago
  The 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 ago
  No, 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 ago
  It'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_...

adrianN 11y ago

Tilings 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 ago

Next up: tie this info cryptography and information theoretic complexity, so we can attempt to create meaningful algorithm security proofs.

fallingfrog 11y ago

So 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 ago
The 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 ago
No, 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 ago
It'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_...