Fredkin Gate, also known as the "Controlled SWAP gate" or a conservative-logic gate, is a computational circuit suitable for reversible computing, invented by Edward Fredkin. It is currently used in quantum computers due to its unique property of not dropping bits (energy & information) during data processing. It behaves similarly to a 4-way light switch, as far as I know.

To be honest, I don't know much of what I'm talking about. Ha ha.

The TRUE purpose of this guide is to provide an open platform for everyone to discuss the Fredkin gate/ CSWAP gate, and document our combined knowledge of it. I plan to update this guide periodically and fill in any missing blanks. In the meantime, feel free to leave a comment!

General Definition:

"A conservative-logic gate is any Boolean function that is invertible and conservative."
- Edward Fredkin (1982)

Invertible & Conservative:

In conservative logic, all signal processing is ultimately reduced to conditional routing of signals. Roughly speaking, signals are treated as unalterable objects that can be moved around in the course of a computation
but never created or destroyed.
- Edward Fredkin (1982)

To put it simply, "invertible" means that any set of outputs (generated by a conservative-logic gate) can be reverse-engineered to recover the original set of inputs, as if the direction of time is reversed. "Conservative" means that the total energy (i.e. the total number of 0s and 1s) is the same across inputs and outputs. No energy is wasted in the process (i.e. no bit is dropped), aside from wire resistance. Moreover, if each signal is marked by a unique colour [^], it is clear to see that their values aren't altered in the process.

Imagine a bowling ball rolling downhill. If you know its outputs (final velocity, acceleration and displacement), you can calculate its inputs (initial velocity, acceleration and displacement) by using the same equations of motion (v^2 = u^2 + 2as), as if time is flowing backwards. The total energy of the ball is also conserved in the process, aside from friction. The bowling ball is not swapped out during its travel.

^ (original) Fredkin gate

This is (probably?) how a Fredkin gate should be implemented. When the Control is OFF, the input-output pairs get swapped. Otherwise, they remain parallel.

The NOT gate is unavoidable here since there isn't a normally-open switch in game.

iC

i1

i2

oC

o1

o2

0

0

0

0

0

0

0

0

1

0

1

0

0

1

0

0

0

1

0

1

1

0

1

1

1

0

0

1

0

0

1

0

1

1

0

1

1

1

0

1

1

0

1

1

1

1

1

1

Note: feeding the outputs of a FRED gate to the inputs of another FRED gate would reverse the FRED operation, and return the original inputs.

^ Controlled SWAP gate

This is (probably?) how a CSWAP gate should be implemented. When the Control is ON, the input-output pairs get swapped. Otherwise, they remain parallel. Basically identical to the Fredkin gate, except the Control is inverted / Output 1 and Output 2 are swapped.

iC

i1

i2

oC

o1

o2

0

0

0

1

0

0

0

0

1

1

0

1

0

1

0

1

1

0

0

1

1

1

1

1

1

0

0

0

0

0

1

0

1

0

1

0

1

1

0

0

0

1

1

1

1

0

1

1

Note: feeding the outputs of a CSWAP gate to the inputs of another CSWAP gate would reverse the CSWAP operation, and return the original inputs.

Assuming no energy is lost in the wires and switches (i.e. Quantum Computers), the outputs can always be reverse-engineered to figure out the original inputs. Hence, no information (energy) is lost in the process.

I have no idea how to do that... I need time to do more research :3

^ Reversible AND gate

This is (probably?) how a RAND gate should be implemented. Sink In should be 0 for a normal AND operation.

si

i1

i2

o

s1

s2

0

0

0

0

0

0

0

0

1

0

0

1

0

1

0

0

1

0

0

1

1

1

1

0

...

...

...

...

...

...

1

1

0

0

1

1

^ Animated .gif showing 2 combinations of RAND designs

Note: feeding the outputs of a RAND gate to the inputs of another RAND gate would reverse the AND operation, and return the original inputs.

"Conservative Logic" (International Journal of Theoretical Physics)
by Edward Fredkin, Tommaso Toffoli
https://link.springer.com/article/10.1007/BF01857727
https://web.cecs.pdx.edu/~mperkows/temp/June16/ConservativeLogic.pdf

"Computing Limit"
by Computerphile
https://www.youtube.com/watch?v=jv2H9fp9dT8

"Reversible Computing"
by Science University of Copenhagen
https://www.youtube.com/watch?v=rVmZTGeIwnc

"Reversible Computing"
by Ed Fredkin
https://www.youtube.com/watch?v=0V5G8am9hEw

"What's Inside A 3-way and 4-way Switch?"
by Electrician U
https://www.youtube.com/watch?v=5NfjfhA8zdo

"Quantum computing is now a big step closer thanks to a new breakthrough: the Fredkin gate"
by Katherine Noyes
https://www.pcworld.com/article/420280/quantum-computing-is-now-a-big-step-closer-thanks-to-this-new-breakthrough.html

"A quantum Fredkin gate"
by Raj B. Patel, Joseph Ho, Franck Ferreyrol, Timothy C. Ralph, and Geoff J. Pryde
https://www.science.org/doi/10.1126/sciadv.1501531
https://arxiv.org/abs/1603.08086

"Why are reversible gates not used?"
by Mehdi
https://cs.stackexchange.com/questions/38049/why-are-reversible-gates-not-used

"Fredkin Gate implemented in shapez.io"
by John Meacham
https://www.youtube.com/watch?v=CySN31YrR2U

"Conservative Logic" (Collision-Based Computing)
by Edward Fredkin, Tommaso Toffoli
https://link.springer.com/chapter/10.1007/978-1-4471-0129-1_3
https://fab.cba.mit.edu/classes/MAS.862/notes/computation/Fredkin-2002.pdf
https://link.springer.com/chapter/10.1007/978-1-4471-0129-1_3

"Fredkin gates for finite-valued reversible and conservative logics"
by G Cattaneo, A Leporati, R Leporini
https://iopscience.iop.org/article/10.1088/0305-4470/35/46/304
https://arxiv.org/abs/quant-ph/0205139

"CSwapGate"
by Qiskit
https://qiskit.org/documentation/stubs/qiskit.circuit.library.CSwapGate.html

"cirq.CSWAP"
by Google Quantum AI
https://quantumai.google/reference/python/cirq/CSWAP

"A Quantum Computer Simulator"
by Carsten Urbach
https://rdrr.io/cran/qsimulatR/
https://rdrr.io/cran/qsimulatR/man/cswapgate.html

"Quantum Computing Closer After Scientists Build a Fredkin Gate"
by Jelor Gallego
https://futurism.com/quantum-computing-closer-scientists-build-fredkin-gate

"Quantum Computers Explained – Limits of Human Technology"
by Kurzgesagt – In a Nutshell
https://www.youtube.com/watch?v=JhHMJCUmq28

"Raj Patel - A Quantum Fredkin Gate"
by First Workshop on Multi-Photon Interferometry - Shanghai 2015
https://www.youtube.com/watch?v=VHTe3hEHtFQ

"The Quest for the Quantum Computer"
by Julian Brown
https://books.google.ca/books?id=ECWm59h2pLAC&pg=PAS8&redir_esc=y#v=onepage&q&f=false

"A quantum Fredkin gate"
by Raj B. Patel, Joseph Ho, Franck Ferreyrol, Timothy C. Ralph, Geoff J. Pryde
https://www.science.org/doi/10.1126/sciadv.1501531

"Lecture 7 3 REVERSIBLE COMPUTATION"
by Sandro Mareco
https://www.youtube.com/watch?v=sIuqM_YzDtE

"Fredkin-Toffoli's Billiard Ball Model"
by abacoo
https://www.youtube.com/playlist?list=PLtIA-JFuqjJV-J5ujaGjTKhiXrqTE_mGZ

"Stanford Seminar - Generalized Reversible Computing and the Unconventional Computing Landscape"
by Stanford Online
https://www.youtube.com/watch?v=IQZ_bQbxSXk

"Ed Fredkin - Reversible Computing (Keynote from the CCC's Workshop on Reversible Computing)"
by Computing Research Association
https://www.youtube.com/watch?v=ROv1HX-gdas

"Universal Computing"
by Ed Fredkin
https://www.youtube.com/watch?v=gW1ZAG59u1g

"How Does a Quantum Computer Work?"
by Veritasium
https://www.youtube.com/watch?v=g_IaVepNDT4

"Transistors, How do they work?"
by Lesics
https://www.youtube.com/watch?v=7ukDKVHnac4

"Transistors Explained - How transistors work"
by The Engineering Mindset
https://www.youtube.com/watch?v=J4oO7PT_nzQ

"How Transistors Work"
by The Engineering Mindset
https://www.youtube.com/watch?v=CQtSS6g00h0

"Transistors - Field Effect and Bipolar Transistors: MOSFETs and BJTs"
by Physics Videos by Eugene Khutoryansky
https://www.youtube.com/watch?v=Bine_PbyFSQ

"The Ternary Manifesto"
by Douglas W. Jones, from the University of Iowa
https://homepage.cs.uiowa.edu/~dwjones/ternary/

StackOverflow:
https://stackoverflow.com/questions/19883001/why-does-feynman-refer-to-this-reversible-gate-as-a-nand

"DeMorgan's Theorems"
by California State University
https://www.csus.edu/indiv/p/pangj/class/cpe64/ademo/l1_demo_demorgan.pdf

"Regular Reversible Structures • Mirror Circuits and Spies"
by Portland State University
https://web.cecs.pdx.edu/~mperkows/CLASS_VHDL_99/tran888/lecture003-reversible-logic.pdf

Forum for Electronics:
https://www.edaboard.com/threads/reversible-logic-vs-combinational-logic.277771/

"Computing exponentially faster: Implementing a nondeterministic universal Turing machine using DNA"
by Andrew Currin, Konstantin Korovin, Maria Ababi, Katherine Roper, Douglas B. Kell, Philip J. Day, Ross D. King
https://arxiv.org/abs/1607.08078
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5378132/

"Lecture 22 - Non-deterministic Turing machines and NP"
by Cheriton School of Computer Science
https://cs.uwaterloo.ca/~s4bendav/files/CS360S21Lec22.pdf

"Turing Machines"
by Carnegie Mellon University
https://www.andrew.cmu.edu/user/ko/pdfs/lecture-14.pdf

"1 Deterministic Turing Machines"
by UMD Department of Computer Science
http://www.cs.umd.edu/~gasarch/COURSES/452/S17/turingmachines.pdf

"On the Simply-Typed Functional Machine Calculus: Categorical Semantics and Strong Normalisation"
by Chris Barrett
https://arxiv.org/abs/2305.16073

"On Universal DNA Computing"
by Grigory Sapunov
https://moocaholic.medium.com/on-universal-dna-computing-241dc1fba568

"Quest for the Quantum Computer"
by Julian Brown
https://www.amazon.ca/Quest-Quantum-Computer-Julian-Brown/dp/0684870045

"The Fundamental Physical Limits of Computation"
by Charles H. Bennett, Rolf Landauer
https://www.scientificamerican.com/article/the-fundamental-physical-limits-of-computation/
https://www.jstor.org/stable/24967723
https://www.academia.edu/3729806/The_Fundamental_Physical_Limits_of_Computation
https://eric.ed.gov/?id=EJ321485

"Ultimate physical limits to computation"
by Seth Lloyd
https://arxiv.org/abs/quant-ph/9908043

"ENERGY AND INFORMATION"
by Myron Tribus, Edward C. McIrvine
http://www.jstor.org/stable/24923125

"Irreversibility and Heat Generation in the Computing Process"
by R. Landauer
https://ieeexplore.ieee.org/abstract/document/5392446
https://www.semanticscholar.org/paper/Irreversibility-and-heat-generation-in-the-process-Landauer/59c60fc1106235ca102473fa1fd0db46e618c6a4
https://www.researchgate.net/publication/298261799_Irreversibility_and_heat_generation_in_the_computing_process_Reprinted_from_IBM_Research_and_Development_vol_5_1961

"Logical Reversibility of Computation"
by C. H. Bennett
https://ieeexplore.ieee.org/document/5391327
https://www.semanticscholar.org/paper/Logical-reversibility-of-computation-Bennett/4c7671550671deba9ec318d867522897f20e19ba

"Energy Cost of Information Transfer"
by Jacob D. Bekenstein
https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.46.623

"Universal upper bound on the entropy-to-energy ratio for bounded systems"
by Jacob D. Bekenstein
https://journals.aps.org/prd/abstract/10.1103/PhysRevD.23.287

"Reversible Computing"
by Kenichi Morita
https://link.springer.com/referenceworkentry/10.1007/978-0-387-30440-3_456#citeas

"Reversible Computing"
by Tommaso Toffoli
https://link.springer.com/chapter/10.1007/3-540-10003-2_104
https://cqi.inf.usi.ch/qic/80_Toffoli.pdf

"Quantum Tunneling"
by University of Illinois Urbana-Champaign
https://courses.physics.illinois.edu/phys485/fa2015/web/tunneling.pdf

"Boltzmann's Tyranny and Quantum Tunneling: The End of Computing?"
by Atoms and Sporks
https://www.youtube.com/watch?v=67S4IyakRko

"What is a gate-all-around transistor?"
by ASML
https://www.asml.com/en/news/stories/2022/what-is-a-gate-all-around-transistor

"Transistor Gates"
by Hyperphysics
http://hyperphysics.phy-astr.gsu.edu/hbase/Electronic/trangate.html

Reddit post:
https://www.reddit.com/r/askscience/comments/itiuw8/how_are_chip_manufacturers_getting_around_quantum/

"These Transistor Gates Are Just One Carbon Atom Thick"
by IEEE Spectrum
https://spectrum.ieee.org/smallest-transistor-one-carbon-atom

"Vertical MoS2 transistors with sub-1-nm gate lengths"
by Wu, F., Tian, H., Shen, Y. et al.
https://www.nature.com/articles/s41586-021-04323-3

"Quantum Tunneling Is Not Instantaneous, Physicists Show"
by Anil Ananthaswamy
https://www.scientificamerican.com/article/quantum-tunneling-is-not-instantaneous-physicists-show/

"Measurement of the time spent by a tunnelling atom within the barrier region"
by Ramos, R., Spierings, D., Racicot, I. et al.
https://www.nature.com/articles/s41586-020-2490-7

"Faster than Light?"
by Raymond Y. Chiao
https://www.scientificamerican.com/article/faster-than-light/

Reddit Discussion:
https://www.reddit.com/r/TuringComplete/comments/xh49cm/does_anyone_know_how_to_build_with_cswap/

Wikipedia: Fredkin gate
https://en.wikipedia.org/wiki/Fredkin_gate
^ Never put this in the reference section!

Wikipedia: Landauer's principle
https://en.wikipedia.org/wiki/Landauer%27s_principle
^ Never put this in the reference section!

Wikipedia: Moore's law
https://en.wikipedia.org/wiki/Moore%27s_law
^ Never put this in the reference section!

Wikipedia: Boolean algebra
https://en.wikipedia.org/wiki/Boolean_algebra
^ Never put this in the reference section!

Wikipedia: Toffoli gate
https://en.wikipedia.org/wiki/Toffoli_gate
^ Never put this in the reference section!

Wikipedia: Logic block
https://en.wikipedia.org/wiki/Logic_block
^ Never put this in the reference section!

Wikipedia: Field-programmable gate array
https://en.wikipedia.org/wiki/Field-programmable_gate_array
^ Never put this in the reference section!

Wikipedia: Turing machine
https://en.wikipedia.org/wiki/Turing_machine
^ Never put this in the reference section!

Wikipedia: Nondeterministic Turing machine
https://en.wikipedia.org/wiki/Nondeterministic_Turing_machine
^ Never put this in the reference section!

Wikipedia: Probabilistic Turing machine
https://en.wikipedia.org/wiki/Probabilistic_Turing_machine
^ Never put this in the reference section!

Wikipedia: Moore's law
https://en.wikipedia.org/wiki/Moore%27s_law
^ Never put this in the reference section!

Wikipedia: Quantum tunnelling
https://en.wikipedia.org/wiki/Quantum_tunnelling
^ Never put this in the reference section!

Wikipedia: Combinatory logic
https://en.wikipedia.org/wiki/Combinatory_logic
^ Never put this in the reference section!

Wikipedia: Ternary operation
https://en.wikipedia.org/wiki/Ternary_operation
^ Never put this in the reference section!

Wikipedia: Quantum tunnelling
https://en.wikipedia.org/wiki/Quantum_tunnelling
^ Never put this in the reference section!

Correction:

· "Sink in" should be termed "Source", according to Fredkin's academic paper.

· model a reversible OR gate ingame
· model a reversible XOR gate ingame
· model a reversible NAND gate ingame
· model a reversible NOR gate ingame
· model a reversible XNOR gate ingame
· model a reversible Switch ingame
· model a reversible Adder ingame

· model a reversible Register ingame
· model a reversible CPU ingame
· model a reversible Machine Code ingame
· model a reversible Assembly Language ingame
· finish my computer science thesis
· release an unofficial DLC called "Fredkin Complete"
· be forced to sell the DLC to EA

· understand the meaning of Fredkin gates
· model a Fredkin gate ingame
· understand the meaning of reversible logic gates
· model a reversible AND gate ingame

<unfinished>

[2022-09-17]
· created this guide
· created "Introduction" section
· created "References" section
· created "Translations :)" section

[2022-09-18]
· created "Circuitry" section
· created "AND Gate" section
· created "Updates" section
· edited "Introduction" section
· edited "References" section
· edited "Circuitry" section
· edited "AND Gate" section

[2022-09-19]
· created "Goals" section
· created "Definitions" section
· renamed "AND Gate" section to "RAND Gate"

[2022-09-20]
· renamed "Goals" section to "Todos"
· edited "Definitions" section
· edited "References" section