So if Toffolli gates can serve as a substrate for NAND and NAND is computationally universal. What happens when I build a hash function out of Trofolli-backed NAND gates? Can I run it in reverse and generate pre-images?
Tofolli gates are all you need
31–40 of 45 posts
Re: Tofolli gates are all you need
#32Earlier quoted context omitted.
Actually this is true whichever interpretation you take, give or take some knowledge around black holes. I think hawking actually proved that this is true regardless of how black holes work due to hawking radiation.
> Actually this is true whichever interpretation you take In the Copenhagen interpretation the collapse of the wave function explicitly violates unitarity (and thus reversibility).
(This is way beyond my area of expertise so excuse me that this might be a stupid idea.)
I assume the following happens: while a (small) subsystem is in "pure state" (in quantum coherence), no information flows out of this subsystem. Then, when measuring, information flows out and other information flows in, which disturbs the pure state. This collapses of the wave function (quantum decoherence). For all practical purposes, it looks like quantum decoherence is irreversible, but technically this could still be reversible; it's just that the subsystem (that is in coherence) got much, much larger. Sure, for all practical purposes it's then irreversible, but for us most of physics anyway looks irreversible (eg. black holes).
Re: Tofolli gates are all you need
#33Earlier quoted context omitted.
c is the constant 1. You don't need to store that. > Furthermore [this doesn't scale]. Precisely. https://en.wikipedia.org/wiki/Toffoli_gate has better details.
c is an actual input variable, it's not a constant. You can set it to be the constant 1 which the article does in one of the examples, but this isn't mandatory.
C is computable from (a, b) regardless.
Re: Tofolli gates are all you need
#34So if Toffolli gates can serve as a substrate for NAND and NAND is computationally universal. What happens when I build a hash function out of Trofolli-backed NAND gates? Can I run it in reverse and generate pre-images?
Your circuit will contain auxiliary output bits. That way it's reversible knowing all output bits, but irreversible knowing only the actual hash output.
Quite similar to how SHA3/Keccak is built from a reversible permutation, but becomes irreversible one the output it truncated.
Re: Tofolli gates are all you need
#35It’s Toffoli (two f one l)
Re: Tofolli gates are all you need
#36Earlier quoted context omitted.
> Actually this is true whichever interpretation you take In the Copenhagen interpretation the collapse of the wave function explicitly violates unitarity (and thus reversibility).
(This is way beyond my area of expertise so excuse me that this might be a stupid idea.) I assume the following happens: while a (small) subsystem is in "pure state" (in quantum coherence), no information flows out of this subsystem. Then, when measuring, information flows out and other information flows in, which disturbs the pure state. This collapses of the wave function (quantum decoherence). For all practical pu…
The problem is that the larger subsystem includes an observer in a superposition of states of observing different measured values. And we never observe this. Copenhagen interpretation doesn't deal with this at all. It just states this empirical fact.
Re: Tofolli gates are all you need
#37Earlier quoted context omitted.
(This is way beyond my area of expertise so excuse me that this might be a stupid idea.) I assume the following happens: while a (small) subsystem is in "pure state" (in quantum coherence), no information flows out of this subsystem. Then, when measuring, information flows out and other information flows in, which disturbs the pure state. This collapses of the wave function (quantum decoherence). For all practical pu…
The problem is that the larger subsystem includes an observer in a superposition of states of observing different measured values. And we never observe this. Copenhagen interpretation doesn't deal with this at all. It just states this empirical fact.
So if I understand correctly, you are saying the observer doesn't feel like he is in a superposition (multiple states at once). Sure: I agree that observers never experience being in a superposition.
But don't think that necessarily means we are in a Many-Worlds. I rather think that we don't have enough knowledge in this area. Assuming we live in a simulation, an alternative explanation would be, that unlikely branches are not further simulated to save energy. And in this case, superposition is just branch prediction :-)
Re: Tofolli gates are all you need
#38Earlier quoted context omitted.
> The universe is just one gigantic reversible computation. Assuming that the Many-Worlds interpretation is true.
You just need unitarity.
Unitarity means that information (about quantum states) is not lost, despite it appearing otherwise after a measurement. The Many-Worlds interpretation seems to be the simplest way to explain where this information has gone.
Re: Tofolli gates are all you need
#39Earlier quoted context omitted.
You could package all your data into a zip using this language but you would also have a worthless stretch of memory seemingly filled with noise / things you’re not interested in.
Why do you think so? The code example shows that you can do RLE (run length encoding) without noise / additional space. I'm pretty sure you can do zip as well. It would just be very hard to implement, but it wouldn't necessarily require that the output contains noise. [1] https://topps.diku.dk/pirc/?id=janusP
Hmm. As a physicist my intuition is that information-preserving transformations are unitary (unitary transformations are 1-to-1). If a compression algorithm is going to yield a bit string (the zip file, for example) shorter than the original it can't be 1-to-1. So it must yield the zip file and some other stuff to make up for the space saved by the compression.
Re: Tofolli gates are all you need
#40So if Toffolli gates can serve as a substrate for NAND and NAND is computationally universal. What happens when I build a hash function out of Trofolli-backed NAND gates? Can I run it in reverse and generate pre-images?
Your circuit will contain auxiliary output bits. That way it's reversible knowing all output bits, but irreversible knowing only the actual hash output. Quite similar to how SHA3/Keccak is built from a reversible permutation, but becomes irreversible one the output it truncated.
Ah, got it now. Thank you!