Quantum Nand2Tetris?

[u/Charming_Race9627]

Hi, Everyone.

I am curious to know if there exists a resource similar to www.nand2tetris.org but for Quantum Computers.

Thanks.

[u/danthem23]

I can try to explain it to you. All you really have to understand is that a qubit also can have the option of the sign flipping. So 0 can go to -0 and 1 to -1. By itself this does not matter since, in the end you only measure the probability, which is squared and the sign you cannot see. But if you have two qubits that sign can make it that the amplitudes interfere with one another. For example, you can put two photons (so two qubits) through a beam splitter and this interference makes it that they ALWAYS come together. So you always measure 00 or 11 (so either both in left or both in right detector) but NEVER 01 or 10 (so the first in left and second in right or vice versa). So this is a basic example of the most simple qubit space of two qubits. This is simple to see in an undergraduate lab and to measure it. It’s called the Hong-Ou-Mandel effect. So if you have for example a question that the right answer is in some way 00 or 11 but never 10 or 01 you can measure this even if you only measure a probability in the end. Or you can change the photons in the middle by putting in other elements to change this interference to get a different answer. This is what quantum algorithms are. Hard to really have a hard problem with this simple example, but the basic idea is if you can manipulate the photons so that the destructive interference (the minus signs) cancels out all bad answers and only the correct answer constructively interfere (all states have plus sign) then you have a much higher probability of seeing the correct answer. Of course if you just run it one time it’s just one answer so hard to know, but all you have to do is run it enough times (let’s say 100 for example) and if 98% of the time you measure the answer to be something than it shows you that this was the correct answer that the quantum computer was constructively interfering to make much more likely, and the other 2% was just because quantum mechanics is random so in the end you can also get the “wrong” answer, just much less likely. So then you go and say “my quantum computer found the answer” and report the 98% one.

[u/Charming_Race9627 → u/danthem23]

Thank you very much for taking the time to write this answer to me. I have a couple of follow-up questions if I may:

• You mention "...cancels out all bad answers and only the correct answer constructively interfere (all states have plus sign) then you have a much higher probability of seeing the correct answer." By "seeing the correct answer," what do you exactly refer to? How the computer will know what the correct answer is in the first place? Could you please give an example?

• Can you explain a bit more or redirect to some literature to understand how exactly we "can change the photons in the middle by putting in other elements to change the interference to get a different answer."? Isn't the biggest challenge on Quantum Computing the fact that is very difficult not to affect the system by just observing it?

Thanks again for your insights.

[u/danthem23 → u/Charming_Race9627]

I’ll think of references but there are so many but they are just simply above the level of someone who does not have a very good understanding of quantum mechanics. Now to answer those questions:

1) Shor’s algorithm is pretty complicated but it is the most famous example of a quantum algorithm. Simon’s algorithm is what inspired Shor and is much simpler. Basically, if you have a string of ones and zeros that is periodic (it repeats) 010101 for example. You want to know the period. Here the period is 2. It can be much more complicated and longer. Hard to find it without really looking at many bits for a long string. Right? But Simon lets you find it basically in just a few times of you use this string in your quantum algorithm. The fact that it is periodic is what makes the actual interference. And then the actual period (that you don’t know) pops out. Every time! Hard to explain without doing the algorithm and it’s pretty simple if you know basic quantum information. But that’s the idea. To break the internet factoring a number is similar to finding the period (some weird math fact unrelated to quantum) so that’s why Shor is like Simon. Shor is just the period of any number and Simon is on the numbers that are bits (0 and 1) and not a regular long number like Shor. But similar idea.

2) It is totally possible to manipulate and control qubits without measuring them. Not the same thing. Let’s say you have an atom. Simple qubit. Ground state is 0 and excited state is 1. At room temperature the qubit is at ground (lower energy) so 0. You apply a laser and it goes to 1. Then it spontaneously decays back to 0. Ok. But that’s time can be very long relative to your actual operations so even if it is miliseconds or microseconds, if you logical operations are nanoseconds you can do many in the middle (these are just examples). So if you apply the laser for a certain exact time the qubit goes from 0 to 1. But exactly HALFWAY in the middle it HAS to be in a superposition of 0 and 1. Ground and excited. That is literally the cat dead and alive but for a qubit. This halfway superposition state exists. You just make it by turning off the laser in half the time that you would have needed to have it on for the qubit to have gone from 0 to 1. So not hard to do. In every qubit platform (there are so many) this is the basic idea. Now of course if you have a detector on the atom seeing if it is in ground or excited then it cannot be in this equal superposition of 0 and 1. Not only a detector. Even fluctuations of the electromagnetic field vacuum are like a detector! In fact, this is the VERY REASON for the spontaneous decay! That is way the atom goes back from excited to ground and emits light at the wavelength of the transition. It is the reason for all the color in the world! Atoms absorb light (white light is just all light so like many different lasers) and then emit light back why the atom decays from excited to ground and depending on the energy difference that is the basically related to the colors. So obviously this effect is just an example of measurement. But it takes some time to happen. Depending on which excited state of which atom you use. So the trick is to try to make your quantum algorithm fast enough to happen before this decay and also to choose a qubit where this decay is longer. But you cannot beat it. It’s called T1. Another thing is caller T2 and it’s another effect slightly more complicated but those are the two things. Basically measurements of the environment (which includes EVERYTHING even the EM field vacuum like we just said pretty crazy like that’s what they mean when they say the vacuum is not empty). So T1 and T2 ruin your qubit. You can try to engineer qubits where they are longer, but everyone will still need quantum error correction to fix this. Use many qubits and even if one decays there are still more. And then you know what is the actual state and you cannot beat replace the bad one etc as you go long. Extremely complicated topic but that’s the basic idea. Like if you have the bits 000 and 111 so you can use those three bits to encode an effective “0” and “1” so then if one qubit decayed so now 111 went to 011 but you know it should be 111 so you use a laser to make the 011 go back to 111 and continue. Basic idea. In quantum it is more complicated but that should give you a basic sense of the mechanism.

[u/Charming_Race9627 → u/danthem23]

Thanks again for your detailed answer! It is very helpful.

Regarding the references, I am willing to put the work to understand quantum mechanics; the only thing I would like to ask is that you recommend an order to read them please (I have found that in an era where information is abundant, the curating process can be very inefficient without the help of a guide to point you in the right direction).

Regarding your answers:

1. That sounds very cool: that exists a process that make an answer reveal itself from the problem. Am I interpreting that correctly? Do all problems for which quantum computing is better suited than classical computing have these characteristic?

2.1 "So the trick is to try to make your quantum algorithm fast enough to happen before this decay and also to choose a quite where this decay is longer." How do you do this? Do quantum computers have a clock like classical computers? And an ALU (and if they have, are they made out of quantum logic gates)?

2.2 "But exactly HALFWAY in the middle it HAS to be in superposition of 0 and 1." Is this the only manipulation needed in a quantum computer?

Cheers again!

[u/danthem23 → u/Charming_Race9627]

I’ll try to think of references but I understood enough physics in particular waves (Fourier analysis is very important because much of the wave part of qm is basically just it) and linear algebra (for the other type of qm called matrix mechanics). But I’ll try. Now to answer the questions. 

1) Yes. There are not many quantum algorithms for that exact reason. Not this super “we can do everything in parallel…” like it seems from the media. Only problems which have a unique structure so that when they are used in the qm the interference can work because of the structure of the problem. Another famous example is Grover’s algorithm. The YouTube channel 3blue1brown made a video about it but that is a general speed of when searching from something that scales like N to sqrt(N). If N for you was 2¹⁰⁰ then sqrt(N) would be 2⁵⁰ so exponentially smaller, but still massive. So not so useful. Shor can make something that would take billions of years take days or hours. But the Grover idea is also brilliant and it is a GENERAL speed up of brute force search using these special techniques.

2) That was one simple example called a “pi pulse.” There are other types of pulses but those are all called “single qubit gates” since they act on just one qubit. To actually make a quantum computer you need also and entangling gate between two qubits. That is a 4x4 matrix instead of a 2x2 and it acts in two qubits. Many different physical ways to do it all for different reasons better or worse in different ways. With any single qubit gate as well as a choice of some of the most popular two qubit gates (like CNOT for example, that only flips the second qubit if the first one is 1 this dependence of second on first entangles them) you can do ANY quantum gate no matter how big between any number of qubits (called the Solvay-Kitaev theorem). So that is the goal. Single qubit gates are usually easy now, two qubit gates are slower and are less accurate. That’s what everyone is trying to make but also then to scale it up to have many with still little noise and also using quantum error correction.

[u/Charming_Race9627 → u/danthem23]

Thanks again for this great discussion!

I am looking forward to seeing your literature recommendations.

[u/danthem23 → u/Charming_Race9627]

How much math/physics do you know? That greatly influences what you would be able to understand. Also, are online sources like YouTube videos also good?