A Tutorial Quantum Interpreter (draft) 150 lines of code or your money back!
. Computing 775 . Berkeley, CA 94710
June 5, 2018
Simulating a universal, gate-based quantum computer on a classical com- puter has many uses and benefits. The top benefit is the ability to inspect the amplitudes of the system’s state directly. However, while the mathematics is very well understood, implementing a general-purpose simulator has largely been folk knowledge. In this tutorial, we show how to build an interpreter for a general-purpose quantum language called L , capable of executing most kinds of quantum circuits found in literature. It is presented economically, allowing its implementation to take fewer than 150 lines of self-contained Common Lisp code. The language L is very simple to extend, making the interpreter ripe for testing di erent kinds of behavior, such as noise models.
Copyright By PowCoder代写 加微信 powcoder
1. Introduction 2 2. The Language L 3
3. The Quantum State 4 Wheredoesonequbitlive? ………………………… 4 Manyqubits ……………………………….. 5 Bitstring notation and a general quantum state . . . . . . . . . . . . . . . . . . . 6 Evolving the quantum state . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4. Measurement
5. Gates 9 Gatesasmatrices……………………………… 9 Gatesonmulti-qubitmachines ………………………. 11 Multi-qubitgatesonnon-adjacentqubits …………………. 13
6. An Interpreter 16 Thedriverloop………………………………. 16 E ciency …………………………………. 17
7. Examples 17 Bellstate …………………………………. 17 Greenberger–Horne–Zeilingerstate …………………….. 17 ThequantumFouriertransform………………………. 18
Bibliography 19 A. Example Transcript 20 B. Full Source Code and License 21
1. Introduction
Simulating the workings of an ideal quantum computer has many important applications, such as algorithms research and quantum program debugging. A variety of quantum com- puter simulators exist, both free and commercial. However, while the concept of the simulation of quantum computers is generally well understood at a high level, the devil is in the details when it comes to implementation.
Quantum computer simulators found in the wild often have many limitations. The most prevalent limitation is the number of qubits an operator can act on. Usually, one-qubit gates and controlled one-qubit gates are allowed, but nothing more. While these together are su cient for universal quantum computation, it leaves much to be desired when studying quantum algorithms.
In this paper, we present an implementation of a fully general quantum computing language interpreter, allowing measurement as well as arbitrary unitary operators on an arbitrary number of arbitrarily indexed qubits. The implementation weighs in at under 150 lines of code in Common Lisp, though the ideas make implementation simple in other languages as well. All of the code from this tutorial can be found in [1] or in the appendix.
This tutorial is aimed at a quantum computing beginner who has some familiarity with the fundamentals of linear algebra and computer programming. Beyond those subjects, this tutorial is relatively self-contained. We also aim this tutorial at practitioners of quantum computing, who are interested in the brass tacks of simulation, with all of the details filled out. To such practicioners, the bulk of this document will be easy to skim, since we
recapitulate topics such as qubits and unitary operators.
2. The Language L
We wish to construct an interpreter for a small quantum programming language unimagina- tively named L . This language supports both of the fundamental operations of a quantum computer: gates and measurements.
A gate is an operation that modifies a quantum state. (What a quantum state is exactly we will delve into later.) Gates represent the “powerful” operations of a quantum computer. A measurement is a simultaneous observation and collapse of the quantum state. Mea- surements represent the only way in which one can extract information from a quantum
In some sense, one might think of the language L as the simplest non-trivial quantum
programming language. A program in L is just a sequence of gates and measurements. The syntax is as follows:
We borrow Common Lisp’s two-dimensional array syntax for the syntax of matrices. In Common Lisp, the matrix ( 1 2 ) is written #2A((1 2) (3 4)).
An example program might be one to construct and subsequently measure two qubits labeled 0 and 1 in a Bell state configuration:
We will model the semantics of L operationally, by way of an abstract machine. The abstract machine for L is called Mn, where n is a positive but fixed1 number of qubits. The state of the machine Mn is the pair (v, b) where v is a quantum state, and b is an n-bit measurement register.
1With only a little bit of extra work, mostly bookkeeping, we could make n finite but unbounded during the execution of a program by having instead a collection of so-called quantum registers. These would be realized by instead a collection of v’s, which are opportunistically combined with entanglement occurs.
| (MEASURE)
(GATE #2A((0.70710677 0.70710677) (0.70710677 -0.70710677)) 0)
(GATE #2A((1 0 0 0) (0 1 0 0) (0 0 0 1) (0 0 1 0)) 0 1)
The quantum state is an element of the set {ÎvÎ = 1 | v œ (C2)¢n}. In other words, v is a unit vector of dimension 2n over the complex numbers. We will discuss this from first principles in §3.
The measurement register is an element of the set {0,1}n, a sequence of n bits, which we realize as a non-negative integer. Each bit represents an observation of a qubit. We will discuss this in detail in §4. 2
In Common Lisp, it su ces to create a structure machine which holds these two pieces of state.
(defstruct machine quantum-state measurement-register)
The precise way in which the language L is interpreted on Mn is what we describe in this tutorial. Before that, however, we find it most important to describe what exactly a quantum state is, and how to represent it on a computer.
3. The Quantum State Where does one qubit live?
Quantum computers are usually just a collection of interacting computational elements called qubits. A single qubit has two distinguished states3: |0Í and |1Í. If the qubit has a name like q, then we label the states |0Íq and |1Íq.
These distinguished states are understood to be orthonormal basis vectors in a vector space whose scalars are complex numbers C. As such, a qubit can be |0Í, |1Í, or a su- perposition – |0Í + — |1Í, where – and — are complex numbers. The numbers – and — are called probability amplitudes, because |–|2 (resp. |—|2) represent the probability of the qubit being observed in the |0Í (resp. |1Í) state. Since they represent probabilities, there’s an additional constraint, namely that the probabilities add to one: |–|2 + |—|2 = 1.
To those unfamiliar, it may not be obvious why we’ve opted to use the language of linear algebra in the previous paragraph. Why do we consider a qubit as being a linear combination? Why do we suppose that the observable states are orthonormal vectors? Why can’t we simply say that a qubit is just a pair of complex numbers and move on?
The reason for this is scientific, and not mathematical. It turns out that the best theory of quantum mechanics we have is one which describes transformations between states as being
2If we wanted to make our implementation more elaborate, we might opt to create a class instead, so we can make full use of Common Lisp’s object system. Such is discussed in [2] for the purpose of simulating di erent noise models.
3The funny notation is called Dirac notation or braket notation. It happens to be a convenient notation for doing calculations in quantum mechanics, and we just use it for consistency with other texts. The bracket |·Í doesn’t add any special significance, except to denote that the quantity is a vector. One can actually put anything inside the brackets. In usual linear algebra, one often writes ei to denote a basis vector, where in quantum mechanics, one just writes the subscript |iÍ, dropping the e entirely. If the notation throws you o , and you’d like to think in more traditional written linear algebra notation, you can always replace |xÍ with ̨x, and you’ll be safe.
linear. In fact, the evolution of a quantum mechanical system is not only described by an operation that is just linear, but also reversible. These conditions—linear, reversible, and length-preserving—give rise to a special class of transformations called unitary operators, which naturally lead us to the discussion of vector spaces over complex numbers4.
We will discuss the nature of these operations in more depth when we consider how to implement gates in §5. For now, however, it’s su cient to think of a qubit named q as something that lives in a complex, two-dimensional vector space, which we will call Bq := spanC{|0Íq , |1Íq}. (We will use this Bq notation a few times throughout this tutorial. Remember it!) We also understand that this space is equipped5 with a way to calculate lengths of vectors, namely the usual L2-norm |–|2 + |—|2.
Many qubits
Roughly speaking, a single qubit can be described by two probabilities. How do we deal with more?
Suppose we have two qubits named X and Y . As a pair, quantum mechanics tells us that they can interact. Practically, what that means is that their states can be correlated in some way. If they’ve interacted, knowing information about X might give us a clue about what Y might be. One well-known example of this is the Bell state, which can be summarized as follows:
Qubit X |0ÍX |0ÍX
Qubit Y |0ÍY |1ÍY
Prob. Amp.
Probability
0 0% |1Í |0Í 0 0%
|1ÍX |1ÍY 1/ 2 50%
Here, we have an example of a non-factorizable state; qubits X and Y are correlated to each other dependently. If we know X is in the |0ÍX state, then we necessarily know that Y is in the |0ÍY state. Such a correlation means it’s not possible to express the probabilities independently. It might be tempting to think that one can simply think of X having a 50% probability of being in either basis state, and Y having a 50% probability of being in either state—facts which are certainly true—but considering those independently would give us a di erent distribution of probabilities of the system:
4For that matter, why complex numbers, and not just real-valued probabilities? The reason is that a complex number of unit norm can be written as ei◊, where ◊ is called the phase. Phases are a wave-like property, and allow the complex probability amplitudes to interfere. Interference is a known and understood phenomenon of quantum mechanical systems.
5Spaces with all of these properties, including a way to calculate distances, are called Hilbert spaces. 5
Qubit X |0ÍX |0ÍX |1ÍX |1ÍX
Qubit Y |0ÍY |1ÍY |0ÍY |1ÍY
Probability
P(X = |0ÍX)P(Y = |0ÍY ) = 25% P(X = |0ÍX)P(Y = |1ÍY ) = 25% P(X = |1ÍX)P(Y = |0ÍY ) = 25% P(X = |1ÍX)P(Y = |1ÍY ) = 25%
This state is called factorizable because we can express each probability as a product of probabilities pertaining to the original qubits, i.e., each probability has a form that looks like P(X)P(Y). Note that here, knowing something about X gives us no information about Y , since they’re completely independent.
With that said, it should be emphasized that factorizable states are perfectly valid states, but they don’t represent the entirety of possible states.
If qubits X and Y live in the linear spaces BX and BY respectively, then the composite space is written BX ¢ BY . This is called a tensor product, which is a way to combine spaces with the above structure. Formally, if we have an m-dimensional vector spaces V := span{v1,…,vm} and an n-dimensional vector space W := span{w1,…,wn}, then their tensor product T := V ¢W will be an mn-dimensional vector space span{t1, . . . , tmn}, where each ti is a formal combination of basis vectors from V and W . (There are of course mn di erent combinations of v’s and w’s.) To give an example without all the abstraction, consider V with a basis { ̨x, ̨y, ̨z} and W with a basis {p ̨, ̨q}. Then V ¢ W will have a basis
I ̨x¢p ̨, ̨y¢p ̨, ̨z¢p ̨, J. ̨x ¢ ̨q , ̨y ¢ ̨q , ̨z ¢ ̨q
Intuitively, a tensor product “just” gives us a way to associate a number with each pos- sible combination of basis vector. In our case, we need to associate a probability amplitude with each combination of distinguished qubit basis states. We need this ability since—as we’ve established—we need to consider every possible holistic outcome of a collection of qubits, as opposed to the outcomes of the qubits independently. (The former constitute both factorizable and non-factorizable states, while the latter only include factorizable states.)
Bitstring notation and a general quantum state
If we have qubits X, Y , and Z, then they’ll live in the space BX ¢ BY ¢ BZ, which we’ll call Q3. It will be massively inconvenient to write the basis vectors as, for example, |0ÍX ¢ |1ÍY ¢ |1ÍZ , so we instead use the shorthand |011Í when the space has been defined. This is called bitstring notation. A general element |ÂÍ of Q3 can be written
Â0 |000Í+Â1 |001Í+Â2 |010Í+Â3 |011Í+Â4 |100Í+Â5 |101Í+Â6 |110Í+Â7 |111Í. There are two substantial benefits6 from using bitstring notation.
6These benefits are much more thoroughly explained in [3], especially in the context of computer implementation.
The first benefit is that the names of the qubits—X, Y , and Z—have been abstracted away. They’re now just positions in a bitstring, and we can canonically name the qubits according to their position. We record positions from the right starting from zero, so X is in position 2, Y is in position 1, and Z is in position 0.
The second benefit is one relevant to how we implement quantum states on a computer. As written, the probability amplitude Âi has an index i whose binary expansion matches the bitstring of the basis vector whose scalar component is Âi. This is no accident. The main outcome of this is that we can use a non-negative integer as a way of specifying a bitstring, which also acts as an index into an array of probability amplitudes. So for instance, the above state can be written further compactly as
Here, |iÍ refers to the ith bitstring in lexicographic (“dictionary”) order, or equivalently, the binary expansion of i as a bitstring.
Since qubits live in a two-dimensional space, then n qubits will live in a 2n-dimensional space. With a great deal of work, we’ve come to our most general representation of an
n-qubit system:
Âi |iÍ , i=0
Âi |iÍ .
where |Âi|2 gives us the probability of observing the bitstring |iÍ, implying n
i=0 |Âi|2 = 1.
On a computer, representing a quantum state for an n-qubit system is simple: It’s just an array of 2n complex numbers. An index i into the array represents the probability amplitude Âi, which is the scalar component of |iÍ. So, for instance, the state |000Í in a 3-qubit system is represented by an array whose first element is 1 and the rest 0. Here is a function to allocate a new quantum state of n qubits, initialized to be in the |…000Í state:
Sometimes, given a quantum state, or even an operator on a quantum state, we will want to recover how many qubits the state represents, or the operator acts on. In both cases, the question reduces to determining the number of qubits that a dimension represents. Since our dimensions are always powers of two, we need to compute the equivalent of a binary logarithm. In Common Lisp, we can compute this by computing the number of bits an integer takes to represent using integer-length. The number 2n is always a 1 followed by n0’s, so the length of 2n in binary is n+1.
(defun make-quantum-state (n)
(let ((s (make-array (expt 2 n) :initial-element 0.0d0)))
(setf (aref s 0) 1.0d0)
(defun dimension-qubits (d)
(1- (integer-length d)))
Evolving the quantum state
Since the quantum state is a vector, the principal way we change it is through linear operators represented as matrices. As our program proceeds, we say that the quantum state evolves. Matrix–vector multiplication is accomplished with apply-operator and matrix–matrix multiplication is accomplished with compose-operators. There is nothing special about these functions; they are the standard textbook algorithms.
(defun apply-operator (matrix column)
(let* ((matrix-size (array-dimension matrix 0))
(result (make-array matrix-size :initial-element 0.0d0)))
(dotimes (i matrix-size)
(let ((element 0)) (dotimes (j matrix-size)
(incf element (* (aref matrix i j) (aref column j))))
(setf (aref result i) element)))
(replace column result)))
(defun compose-operators (A B)
(destructuring-bind (m n) (array-dimensions A)
(let* ((l (array-dimension B 1))
(result (make-array (list m l) :initial-element 0)))
(dotimes (i m result)
(dotimes (k l)
(dotimes (j n)
(incf (aref result i k)
(* (aref A i j)
(aref B j k)))))))))
These functions will sit at the heart of the interpreter, which will be elaborated upon in §5.
4. Measurement
Already, through the construction of our quantum state, we’ve discussed the idea that the probability amplitudes imply a probability of observing a state. Measurement then amounts to looking at a quantum state as a discrete probability distribution and sampling from it.
Measurement in quantum mechanics is side-e ectful; observation of a quantum state also simultaneously collapses that state. This means that when we measure a state to be a bitstring, then the state will also become that bitstring, zeroing out every other component in the process.
The process of measurement hence happens in two steps: The sampling of the state followed by its collapse.
Note that we’ve recorded our observation into the measurement register. We now proceed to define what we mean by sample and collapse.
How shall we sample? This is a classic problem in computer science. If we have N events {0, 1, . . . , N ≠ 1}, such that event e has probability P (e), then we can sample as follows. Consider the partial sums defined by the recurrence S(0) = 0 and S(k) = S(k≠1)+P (k≠1). If we draw a random number r uniformly from [0, 1), then we wish to find the k such that S(k) Æ r < S(k + 1). Such a k will be a sampling of our events according to the imposed probability distribution.
We can implement this simply by computing successive partial sums, until our condition is satisfied. In fact, we can be a little bit more resourceful. We can find when r≠S(k+1) < 0, which amounts to successive updates r Ω r ≠ P (k).
With a quantum system, we have P(|iÍ) = |Âi|2, and the sampled k is the bitstring |kÍ we find.
Collapsing to |kÍ is simply zeroing out the array and setting Âk to 1. 5. Gates
Gates as matrices
Gates are the meat of most quantum algorithms. They represent the “hard work” a quan- tum computer does. As previously described, a gate g is a transformation that is linear, invertible, and length-preserving.
Linear g(a|ÂÍ+b|„Í)=ag|ÂÍ+bg|„Í.
Invertible There is always an operation h that can cancel out the e ect of g: hg |ÂÍ = gh |ÂÍ = |ÂÍ.
(defun observe (machine)
(let ((b (sample (machine-quantum-state machine))))
(collapse (machine-quantum-state machine) b)
(setf (machine-measurement-register machine) b)
(defun sample (state)
(let ((r (random 1.0d0)))
(dotimes (i (length state))
(decf r (exp
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com