This is pretty cool. I think it is also notable because an n bit input Boolean function has 2^n possible inputs and (correct me if I am wrong), ( n 2^n /2 ) unique connections between neighboring...
This is pretty cool. I think it is also notable because an n bit input Boolean function has 2^n possible inputs and (correct me if I am wrong), ( n 2^n /2 ) unique connections between neighboring inputs ("edges of the cube.")
To transverse n × 2^n /2 edges is a lot...think about even 32 bit addition. That's 64 input bits or a gazillion transversals that could never be completed in the life of the universe. Then of course you have a 32 bit output, so multiply a gazillion by 32.
It's good to have a proof to tell you what "limits" you might have for problems like this.
Edit: I did the math, and to transverse all edges of a 32 bit adder function would take you more than a trillion years...
Here is the preprint of the proof. The preprint is 6 pages, of which about 2 are actually the proof. If you are familiar with linear algebra and graph theory you might want to take a look here, as...
Here is the preprint of the proof. The preprint is 6 pages, of which about 2 are actually the proof. If you are familiar with linear algebra and graph theory you might want to take a look here, as the proof is relatively accessible.
Also check out Scott Aaronson's blog post about it. His blog in general is usually worth a read when there's a buzz in the CS / QC world.
Just a couple more neat details about this that have come up: Hao Huang (the author of the proof) posted a comment on the blog post that @gpl linked, giving some timeline/background on figuring it...
Just a couple more neat details about this that have come up:
This is pretty cool. I think it is also notable because an n bit input Boolean function has 2^n possible inputs and (correct me if I am wrong), ( n 2^n /2 ) unique connections between neighboring inputs ("edges of the cube.")
To transverse n × 2^n /2 edges is a lot...think about even 32 bit addition. That's 64 input bits or a gazillion transversals that could never be completed in the life of the universe. Then of course you have a 32 bit output, so multiply a gazillion by 32.
It's good to have a proof to tell you what "limits" you might have for problems like this.
Edit: I did the math, and to transverse all edges of a 32 bit adder function would take you more than a trillion years...
Thank you for your math. Reminds me of the story of the math that Emil Konopinski did.
Here is the preprint of the proof. The preprint is 6 pages, of which about 2 are actually the proof. If you are familiar with linear algebra and graph theory you might want to take a look here, as the proof is relatively accessible.
Also check out Scott Aaronson's blog post about it. His blog in general is usually worth a read when there's a buzz in the CS / QC world.
Just a couple more neat details about this that have come up: