To move fast, quantum maze solvers must forget the past(quantamagazine.org)
quantamagazine.org
To move fast, quantum maze solvers must forget the past
https://www.quantamagazine.org/to-move-fast-quantum-maze-solvers-must-forget-the-past-20230720/
13 comments
The mistake here could also be that they are building a snake and that the real algorithm is about minimal ring containing start and end node. Usually when solving a puzzle the bad decision is taken as the first step and it is some sort of ego barrier that is hard to get over with
I know I'm not part of this domain, but I've always found it interesting how papers really seem to "bury the lede" beyond an abstract.
I feel like if I were writing a paper like this, by the time I get to Lemma 70, I would put in all caps "THIS IS WHAT WE WANT", and then recap backwards to show how this links back to the original idea. It's never in this style though, and I think it's a shame. Both in CS and math papers, people seem to understand the point of pitching abstracts, but would benefit from a bit of a second-level or third-level outline throughout the paper IMO.
I feel like if I were writing a paper like this, by the time I get to Lemma 70, I would put in all caps "THIS IS WHAT WE WANT", and then recap backwards to show how this links back to the original idea. It's never in this style though, and I think it's a shame. Both in CS and math papers, people seem to understand the point of pitching abstracts, but would benefit from a bit of a second-level or third-level outline throughout the paper IMO.
I don’t know, I’ve seen lots of math papers that sketch a high-level outline of the whole proof in section 1 or 2.
My Apollo-era mind tries to digest all this business about forgetting the past (shouts to unattainable parallelism and its complexity curve) and I laugh when I distill it in my mind to... wait for it... "solving a maze by pouring water into it and seeing where it comes out. Then leaving future science to figure it out and clean up the mess."
Does the algorithm keep a classical reference to the end node? If so, it sounds like that would be an O(sqrt(m)) classical speedup as now you can do a double-ended search which reduces depth by 1/2 -> O(2^(x/2)) in classical performance.
I wonder if you could somehow encode the path taken in the exit node (or any of the nodes you do know) & evaluate multiple graphs or if that defeats the speedup & you're back into classical time taken.
This situation is presumably like the double-slit experiment: any surviving record at all anywhere of the specific path taken breaks the superposition that exists between the configurations where different paths were taken. Superposition only works when the result of multiple configurations (where different paths were taken) are exactly the same (besides their quantum amplitudes). Quantum algorithms rely on superposition in order to do better than classical algorithms.
Not unheard of. People have to forget by making generalizations to understand anything. Many algorithms compress data to avoid storing details. Bloom filter is another example. Still interesting.
I feel like this is not the right sort of metaphor to make regarding this paper, nor any quantum algorithm really. Quantum algorithms rely on some wild superposition mechanisms which defy all sort of comparisons to classical algorithms.
if entanglement is part of information compression happening on the human brains, that would be wild indeed
My brain doing the same each morning, curious about the mechanics of this.
starting everywhere and building bigger snake from smaller ones sounds like quantum version of classical inside outside algorithm that is used to check if an input follows certain probabilistic context free grammar. if you don't know it, might be hard to find it https://en.wikipedia.org/wiki/Inside%E2%80%93outside_algorit...
Sounds suspiciously like basian statistics.