(untitled)

Quantum computing thread. Perfect for discussing fun stuff like searching an unsorted array in O(sqrt(N)) time, binary search of a sorted one with log_3(N) comparisons, rapid factorization of integers, etc. I'm personally interested in the type systems that languages for quantum computers will use. Linear types seem to describe the semantics of quantum information very well, since a qbit can not be cloned, only moved, measured, or be interacted with. There is another aspect that quantum computers have though. All operations except measurements are necessarily reversible. Has there been any research in type systems for reversible computing?

Well, there is at least one language that was built to express reversible computing: https://en.wikipedia.org/wiki/Janus_(time-reversible_computing_programming_language)

Isn't reversible computing sort of mutually exclusive with garbage collection? If you can reverse any computation, no object will ever end up being unreachable right? Actually, anything that has to do with heap allocation seems tricky. Stack operations a la Forth are easy to reverse. I'm having more trouble figuring out how to reverse heap operations.

posting "babby's first quantum computer" image >>1224 >Janus is an imperative programming language with a global store (there is no stack or heap allocation) using non-explicit resources like stacks or heaps isn't time-reversible.

>>1238 >that pic Absolutely great. The best part is how the combine humour with actual information

I'm totally new to the ideas of quantum computing. All I hear people say is that there is a third state that is neither 0 nor 1 and so it goes beyond what binary can do. This makes no sense since anyone could just use tinary if they wanted but we know that that doesn't get you any benefits. So could someone either explain or link to an explaination of how quantum computing is actually better?

>>1242 /s/tinary/ternary

>>1242 >>1238 's image is pretty good. Basically it takes advantage of the fact that in QM everything is less a discrete state and more of a continuous wavefunctiony thing, and if you get the wavefunctiony things to interfere just right you can make stuff go faster.

>>1242 A single qbit is like a little unit vector. If it points straight up, you have a 1. If it points straight down, you have a 0. If it points in a different direction, measuring it will give you probabilities of one or the other depending on that the Z component is. So unlike classical computing where the only logic gates acting on a single bit are the identity and a not gate, for qbits you have arbitrary rotations of that little vector. For multiple qbits that picture gets slightly more complicated, but you can generate all quantum gates with classsical reversible circuits and one-qbit gates.

Question about reversible computing: If a function is reversible and generic, could that be used to prove stronger free theorems than without the reversibility axiom? Basically you're replacing categories with groupoids.

>>1238 this explanation is soykaf because it doesn't talk how what quantum physicists are working with, physically, when they do these experiments or build machines; which is important to understanding what operating a quantum computer is like and why all the theory babble is organized the way it is https://www.youtube.com/watch?v=zNzzGgr2mhk

>>2429 I disagree. Unlike classical computers, there is no lock-in into a dominant design for quantum computers. There are a lot of designs that are very different from each other and which are based on completely different technologies. Talking about one technology teaches you about one technology, which may have a small chance of maturing into the most practical option, or it might end up being more outdated than Babbage's mechanical relays.

>>1238 >using non-explicit resources like stacks or heaps isn't time-reversible. Not true for stacks, as long as you require that any memory that is released has to be uncomputed into zeroes, and make it undefined behaviour if it isn't.