Scale by the Bay 2018: Constantin Gonciulea: Quantum Computing Modeling in Scala
Recording: Scale by the Bay 2018: Constantin Gonciulea: Quantum Computing Modeling in Scala
What is quantum computing? Okay, so earlier this year I started looking at quantum computing and like a lot of big players we want to be quantum ready. This is the term we use. And I was surprised by two things. One is the quantum mechanics classes I took in school didn't help me a lot. But a lot of principles I knew about state management from classical and probabilistic contexts, they actually matched what quantum state does. And in particular, so we have access to a real quantum computer with reasonably many qubits from our partner. But when you look at algorithms, you want to create algorithms or understand algorithms. The last step is going to the real computer
Before that, you use a simulator or you use math. But there is a big gap between the math and the simulator that comes from the SDK, you know, for the real computer. So what I found very useful was to simulate the quantum computation in Scala. Because I could go from math directly to Scala and even back. That's why I have a bi-directional arrow here. For example, this notation, I probably won't have time to explain it. The outer product, it's a math concept that's used a lot, you know, in quantum. In Scala, you can just implement it as is, right? But there is no such thing in the real computer, right? So in the real computer, we are in the assembly stage
So basically, you have to create individual gates, you know, circuits. So if you want to know if an algorithm works, you first, you know, stay high level and then you go low level. And this helped me a lot. I'll share some of that experience. This is a quote from the standard textbook in quantum computing, Nielsen and Chang. So basically, it's pointing out that after many years of trial and error, quantum experts arrive at four postulates or axioms that capture the essence of quantum mechanics. And the same principles apply to quantum computing. So instead of trying to understand why nature works the way it works, if we just apply those four principles, we can, you know, do a lot with quantum computing
And I'll briefly go through those postulates, four of them. So the first two are about state management. How do we represent state? How do we evolve the state? Right? And this is something that we know very well how to do in functional programming. So you represent the state using a vector, which is a collection of numbers. And you evolve it using, it says here, unitary operator. It's a transformation that preserves an invariant. And we'll talk about the invariant later. So the quantum state fits into this pattern of systems whose state is represented by, let's say, label values
And that's pretty much a histogram. So the number of buckets or bins is fixed. I am representing them by different colors here. And each bucket has an associated value. Such systems are everywhere. For example, portfolio allocations. If you look at your 401k, you'll have a number of investment instruments and percentages. Right? You invest a percentage in one stock, another in another bond and so on
Accounting systems. The buckets are accounts. The values are the balances. Probabilistic systems. The buckets are the possible outcomes. And the values are probabilities of those outcomes. And it turns out quantum systems are very similar. Right? So you'll have the buckets, which are the possible outcomes
And the values are a little bit more complex. They are complex numbers instead of real numbers. And we'll talk about that. Now, what about representing the change? How do we represent the change of the state? And there is a monadic approach, of course. How do we represent the change? What's important is that this is a restricted monad. Right? So we don't get access to the value. You know, A here is a pair. You know, it's a tuple
Bucket value. This is a super class that applies to all those contexts. Right? So let's look at the implementation quickly. So the bins are a list of bin value pairs. And usually the state is valid only if it preserves an invariant. For example, in stocks, you want the sum to be one. Right? The percentages. In probabilities, the sum is one
In accounting systems, the sum is zero. Right? So accounting systems usually have that restriction. And this is a quantum state. What's different about it is that first you don't have straight lines. And straight lines are real numbers. These vectors or arrows, as Richard Feynman calls them, they are complex numbers. And the invariant is the sum of the squares of the lengths is one. Right? For quantum systems
But in each case you have an invariant like this. So, how do you apply a change? So if you look at this flat map, it uses the flat map of the list, but it's restricted. Right? So those changes are relative. These changes are relative. When you move money from a stock to another, you just save the percentage. You don't care how much money was there. Right? So that's a relative change. But you need to know how to go from a relative change to an absolute change
And this is, I call it the distribution rule. Right? Which says, given an account and some payments going out, I need a set of entries that will get combined after that. And if I need to normalize, I normalize and that's the new state. So, going to more details here. I won't spend too much time on this. But if you have, let's say, four instruments and you have 20% in A, you want to keep 25%, move 50% to B, sorry, and 25% to C, what we'll get is, let's take A. 25% of 20%, 5%, right? So, what is the implementation? It's here. Right? This distribution rule is all I need
And the combining rule, which is addition in this case. So, given an account and the change, right? This is the row and this is the column in my histogram image. So, I take part of U, which is part of V, sorry, which is the value of the bucket. And I move it into C. Right? This is a flat map. You know, you can think of it as a flat map because it goes into the real flat map, right? And it's all you need to do linear algebra. So, you don't need to multiply matrices. Multiplying matrices is the same as a flat map, pretty much
So, in account balances, I won't spend too much time here. How do we process changes? So, I need to put in the mix the current value in an account, plus all the payments going out. And then again, when I combine all of these, I'll get the values in all the accounts. And this book over here, so the whole book is about an algebraic treatment of accounting. And they have a similar approach. And they also have this invariant that the sum is zero. Now, probabilistic state. This is something that's pretty interesting
So, I'm taking this example from ThinkBase, the book. It's copied in a lot of places. And it's about the base rule, basically. So, let's say that you have five dice in the shape of the platonic solids, the regular polyhydra, with four, six, eight, twelve, twenty faces. You pick one, and then you roll it multiple times. You need to guess which one it was. So, initially, you have no idea what it is, so you'll assume that you have equal probability, right? Then, let's say that you got a six. What can you say about the probabilities? We can rule out four, right? Clearly, because it doesn't have six faces
And then, they kind of decrease this way. And formally, the rule is the base rule. You take the current probabilities and multiply by the likelihoods. So, the likelihood is either zero or one divided by the number of faces. Let's take eight. What's the likelihood of six being thrown with an eight-side die? It's one over eight, right? So, we multiply by point two, and we get something, but it needs to be normalized. Right? So, in this case, we need the normalization rule. And because the likelihood decreases with the number of faces, you get this shape
And finally, if you throw the die more times, you will see that eight is the most likely. Right? If you follow the rules, why is 20 unlikely? It doesn't have zero probability, but it's unlikely. It's because you would expect a wider range of numbers, right? If you have 20 faces. If you didn't get anything above eight, the likelihood is pretty low, right? So, that's base rule. And it's captured by the same abstraction. Right? So, you can apply the same linear algebra formula here, but when you combine the entries, you'll have to multiply. And then you need the normalization rule. Okay? And finally, quantum state
This is nothing else but the portfolio balancing. Except, instead of real numbers, we use complex numbers. Right? That's it. That's the only difference. Right? So, once you go from real numbers to complex numbers, and you do resource allocation, you rebalance, you know, a portfolio, let's say, you get into quantum state. And I don't know if we need a refresher here for complex numbers. are pairs of real numbers. You can see, if you put the point here, it's a vector or an arrow, as Richard Feynman calls it
And it looks like this. Right? For each output, for each bucket if you want, the value is a complex number called amplitude. And it turns out that, we'll see in another postulate, that the probability of getting an outcome is the square of the magnitude of this amplitude. Right? So, this is the connection with probabilistic state. And the quantum state has something in common with all the other three. Right? So, with a portfolio balancing, you have the same linear algebra. With accounting, you... So, accounts have a value, which is a real number, but also a direction
Right? It's credit or debit, plus or minus. Like this. is a complex number pointing this way, this is pointing another way. And finally, the probabilistic state is really similar, because, you know, these are generalized probabilities. People even say, once you allow negative probabilities, you know, you get into quantum state. If you take a probabilistic context, but you allow negative probabilities, you get quantum state. So, in a previous talk, John covered some of the transformations of a quantum coin. So, I have this example here as well
So, a quantum coin is nothing else but a quantum state with two buckets. So, if you say, I only have two buckets, then you can think of it as a coin. And each coin has two complex numbers, you know, pointing out on the faces if you want. And that's a quantum coin. It's usually bias. Right? Because the lengths of these complex numbers, in general, are not equal. Right? So, when evolving the state of a quantum coin is nothing else but changing those amplitudes, these two complex numbers, and also the bias of the coin will change with that. And this is not unusual
So, Richard Feynman uses this example of any glass or any, if you look at a window, you'll see some partial reflection here. And that partial reflection is the bias of a quantum coin. Right? And that, he says that it varies from zero to 60%. And if you increase the thickness of the glass, it will go up and then down to zero and then up again. So, it's periodic. So, you can think of any window as a quantum coin. Right? Again, I won't spend too much time on this. John already covered the Hadamard, which I have here
So, if you apply to Hadamard, you get identity. So, you see, if you put all the probability in one of the outcomes, you get two of those. And these form a basis. Right? And if you combine, so any state can be written as a combination of the basis. So, this gets you into vector spaces, if you want. And the lack of the implementation that I'll show here was borrowed from a project that also borrowed some ideas from Haskell. So, there was an implementation of a vector space in Haskell using monads. How much time do I have? Okay
So, the other postulates, they are about measurement and composition. Measurement is what happens when you want to get the state out. So, you don't have access to it like John explained in the previous talk. You don't have access to those complex numbers. All you can do is, you know, smash the coin and you see if it's heads or tails. But you have to do this repeatedly to find the pattern. Right? What kind of bias is that? So, measurement, that's what it says. You don't have access to the state
You can only measure it. But you can do it repeatedly. Composition, how do you compose a bigger system from a smaller system? And I'm taking here the example of two quantum coins, let's say. So, we have four outputs in this case. You take all possible pairs from the two systems. And you end up with something which is like a tetrahedron. So, you cannot think about two coins separately. You have to think about the whole system now
And the possible outputs are four. You know. These are all the possible combinations. So, 0, 0, 0, 1, 1, 0, 1, 1. And this is the final slide. I wanted to do a demo. I'll switch to the code. So, I took a classical interview question
How do you... So, you need to list all the binary words without consecutive ones. And if you count how many there are, it's the Fibonacci number. So, how do we implement that with quantum circuits? And there is some machinery here that I had to build. And this is public code. I'll give the link. So, you build a circuit. Let me run it first
Just to see the result. So, if I run it and I count how many states are possible. This is a simulator. It's not a real computer. But if I count how many states are possible, that tells me how many outputs are there, right? And that's... You can see that if I use one qubit, I have two outputs. If I use two qubits, three outputs and so on. Fibonacci numbers, right? How do we do this? So..
We use n qubits and first we put all of them in superposition by using a Hadamard gate. Again, John showed that. means... So, you usually start with zero. If I apply a Hadamard gate, I'll get both zero and one. So, now they are possible. Equally possible. But then, if one qubit will turn out as one, I want the next one to be zero
So, how do I do that? And in Scala, I can just make up a state using the outer product. I'll say I want this to be zero. Right? And I get what you saw. On the real computer, I cannot do that. Right? On the real computer, I have to go and break down. So, basically I have to get rid of the Hadamard. Right? Because I applied Hadamard to all gates. And now, if one qubit is one, the next one I want to apply another Hadamard
And that turns out to be equivalent to a rotation by negative pi over two. Control rotation. And I have that in the code. I don't think I have time to explain that. But, basically, Hadamard is a rotation by pi over two followed by a z. And if you do a negative pi over two, you'll just leave the z there, which is changing the sign of the second amplitude. And in the code, I actually put a lot of unit tests. Gates spec
So, whenever I would capture something and I wanted to keep it, I would write a unit test with property-based testing. So, you have random states running that prove, you know, those identities. For example, what I just said. That Hadamard, I have x, y, z here and so on. So, here. Rotation by pi times z is equal to Hadamard. So, I use property-based testing and I prove it, you know. And that's what I mean by going back and forth between the math and the Scala simulator
I don't need to do the math. A lot of times, I just try it out and then I figure out the math. Right? So, that's why for me, the Scala simulator was pretty useful. And the last slide, I have the code and some credits. Any question? Yeah? So, for each qubit, if it's a one, you change the next one to Hadamard. Zero. Oh, whoa. Okay
So, I applied Hadamard on each of them. Yep. Right? So, if one happens to be one, I want the next one to be zero, so I apply another Hadamard to cancel it out. Right? Because two Hadamard's give me identity and if I start it at zero, I'll end up with zero. So, you measure that qubit before. So, this is something I didn't have time to go into details. The conditionals in quantum, they are not really conditionals because you don't look at the value. Ah
So, you just change half of the states. Right? It's more like a constraint. Right? You say when the qubit is one. And half of them will be one in that position. Any other question? Okay. Thank you. .