MASARYK UNIVERSITY FACULTY OF INFORMATICS Unambiguous discrimination using QISKIT BACHELOR'S THESIS Martin Horáček Brno, Spring 2020 MASARYK UNIVERSITY FACULTY OF INFORMATICS Unambiguous discr imination using QISKIT BACHELOR'S THESIS Martin Hor áček Brno, Spring 2020 This is where a copy of the official signed thesis assignment and a copy of the Statement ofan Author is located in the printed version of the document. Declaration Hereby I declare that this paper is my original authorial work, which I have worked out on my own. A l l so urces, references, and literature used or excerpted during elaboration of this work are properly cited and listed in complete reference to the due source. Martin Ho ráček Advisor: doc. RNDr. Jan Bouda, Ph.D. i Acknowledgements I would like to thank my supervisor, doc. RNDr. Jan Bouda, Ph.D., for his guidance. I am also grateful to RNDr. Daniel Reitzner, PhD., for our discussions. iii Abstract We review methods for unambiguous discrimination of pure quantum states. We describe how these methods can be implemented in current quantum computers. We implement unambiguous state discrimination methods in Python3 using the Qiskit library. We implement optimal discrimination of two pure states with the same prior probabilities and optimal discrimination of arbitrary ensembles of pure states with arbitrary prior probabilities. As part of the implementation, we include the decomposition of unitary operators into basic gates and the realization of positive operator valued measure (POVM) measurements. A l l provided discrimination methods can be run on current IBM quantum computers. iv Keywords unambiguous state discrimination, USD, P O V M realization, SDP, timal, Qiskit, unitary decomposition Contents 1 Introduction 1 2 Quantum information processing 3 2.1 Dirac notation 3 2.2 Quantum system 3 2.2.1 Qubit 3 2.2.2 Bloch sphere 4 2.2.3 Multi-qubit systems 4 2.3 Evolution ofa quantum system 6 2.4 Measurement 6 2.4.1 Measurement in the computational basis . . . . 6 2.4.2 Measurement in an orthonormal basis 7 2.4.3 Projective measurement 7 2.4.4 P O V M 8 2.5 Mixed states 9 3 Unambiguous state discrimination 11 3.1 Perfect discrimination 11 3.2 Orthogonal projector discrimination 12 3.3 Optimal discrimination using a sequence of measurements . 14 3.4 Optimal discrimination optimized 15 3.5 2 states with different prior probabilities 16 3.6 Optimal discrimination ofarbitrary ensembles 17 4 Qiskit library 21 4.1 Elements of Qiskit 21 4.2 IBM Quantum 21 4.3 Circuit model of computation 22 4.3.1 Common quantum gates 22 4.4 Transpilers 23 4.5 Providers and backends 24 4.6 Special simulator functions 24 4.7 Register endianity 25 5 Implementation of unambiguous state discrimination 27 5.1 Measurement in an orthonormal basis 27 vii 5.1.1 1-qubit orthonormal basis 28 5.2 Rotation to xz-plane 28 5.3 Conditional termination circuits 29 5.4 Realization ofPOVM 30 5.4.1 P O V M to P O V M with rank 1 elements 30 5.4.2 Neumark theorem construction 31 5.5 Unitary decomposition 31 5.5.1 Multicontrolled U3 32 5.5.2 Two-level unitary 33 5.5.3 Decomposing unitary into two-level unitaries . 33 5.6 Mitigation of problems with floating-point arithmetic . . . . 33 5.6.1 Floating-point number comparison 34 5.6.2 Matrix properties 34 5.6.3 Extending orthogonal states to orthonormal basis 35 6 QUSD package 37 6.1 Used libraries 37 6.2 API 37 6.3 Examples 38 6.4 Tests and evaluation 39 7 Conclusion 41 A Linear algebra for quantum information processing 43 Bibliography 45 viii 1 Introduction Quantum information processing promises improvements over classical information processing in simulation, cryptography, and computation fields. Quantum mechanics introduces new properties that enable these improvements, but it also poses several limitations. One of these limitations is the impossibility of perfectly distinguishing nonorthogonal quantum states. Techniques resolving this impossibility are essential in many applications of quantum information processing. Two important tasks arise from this fundamental problem. The first task is called quantum state tomography or quantum state estimation. It tries to estimate the state of a system by repeated measurements. The second task is called quantum state discrimination, where the set of possible states is previously known, and the goal is to determine the state of the system. There are several strategies for the quantum state discrimination. The minimum-error discrimination minimizes the probability of an incorrect answer, and an incorrect answer can be returned. The strategy examined in this thesis is called unambiguous state discrimination (USD). It allows us to return an inconclusive answer, and whenever a conclusive answer is returned, then it must be the correct one. The probability of the inconclusive answer should be minimized. Unambiguous state discrimination has its applications in cryptographic protocols, where both the user and the attacker can use it. Methods for unambiguous state discrimination of pure states have been proposed, and we think it would be beneficial from the educational and practical point of view to see how these methods can be implemented in current quantum computers. We decided to use Python3 and the Qiskit library. Qiskit is a framework for quantum computation. It can simulate quantum circuits, and run them on IBM quantum computers. We created the QUSD package. It implements several USD methods. They can be either simulated by Qiskit simulators or run on IBM quantum computers. Two general techniques (unitary decomposition, P O V M measurement realization) that are used in USD methods were implemented as part of the QUSD package. 1 i . INTRODUCTION No prior knowledge of quantum information processing is required for the comprehension of this thesis. We suppose the reader has good knowledge of linear algebra and its theorems. In Chapter 2, we introduce the framework for quantum information processing. In Chapter 3, we review unambiguous state discrimination techniques. In Chapter 4, we describe the Qiskit library. In Chapter 5, we describe how techniques from Chapter 3 can be realized on current quantum computers. In Chapter 6, we present the QUSD package, describe its API, and evaluate its performance. In Appendix A, we review notions and theorems from linear algebra that are used extensively in this thesis. 2 2 Quantum information processing In this chapter, we lay down foundations of quantum information processing. We present the most common notation used in quantum physics. We define what a qubit is, how to compose larger systems from qubits, how the state of a system can be changed, and how we can learn something about the state using a measurement. For more detailed explanations see [1, 2]. We advise the reader to familiarize themselves with the most heavily used terms from linear algebra in Appendix A . 2.1 Dirac notation Quantum mechanics uses the Dirac notation for vectors. It is also called the bra-ket notation. The vector v is denoted by \v). (v\ is the vector dual to \v). The inner product between \u) and \ v) is denoted by (u\v). In some cases, we denote the inner product by (\u),\v)), because it can make expressions easier to read. The outer product between \u) and \v) is denoted by \u) (v\. The application of a linear map A to \v) can be written without brackets as A\v). The tensor product between \u) and \v) is written as \u) ® \v). 2.2 Quantum system The state of a quantum system is described by a normalized vector from a Hilbert space. The state can be used for computations in the following way. The input is encoded as the initial state of the system. The state is then evolved and output is obtained by a measurement. The quantum system used most often in quantum computing is called a qubit. 2.2.1 Qubit A qubit is a quantum system with associated two-dimensional Hilbert space %. We work only with this mathematical abstraction, the physical qubit can then be realized in various ways. We define {|0), 11)} to 3 2. Q U A N T U M INFORMATION PROCESSING be an orthonormal basis of %. This basis is called the computational basis. The state of a qubit is a vector \v) E % \v) = fl|0) +b\l), (2.1) where \a\2 + \b\2 = 1. Vectors elX \v), where A G R, represent the same state as vector \v). They differ only in their global phase, which is physically insignificant. It means that vectors yield the same measurement statistics, and they cannot be distinguished. Two often used states with their own special label are states l+> = - U > + - U ) f f (2.2) States | + ), I — ) form an orthonormal basis. 2.2.2 Bloch sphere It is often useful to visualize the state of a qubit using the Bloch sphere. We can always rewrite the vector \v) up to the global phase as \v) = cos9 -\Q) + eicp sin9 -\l). (2.3) Angles 9, (p are shown in the figure 2.1. The term e1(p is called relative phase. In contrary to the global phase, the relative phase can be determined by measurements. The Bloch sphere representation does not have any extension to multi-qubit systems. 2.2.3 Multi-qubit systems The tensor product is used to combine vector spaces into a larger vector space. Suppose we have n qubits with their two-dimensional Hilbert spaces W. The vector space of the composite system is then u m = u® ...®n. 4 2. Q U A N T U M INFORMATION PROCESSING Figure 2.1: Visualization of a vector in the Bloch sphere The state of a 2-qubit system with both qubits in states |0) is |0) |0). To make the notation more compact, we write tensor products also as |0) |1) = |0)|1) = |01). (2.4) To make this notation even more succinct, we often write labels in decimal base, e.g. 1101) = |5). The computational basis of an n-qubit system can be written as e {0,...,2W -1}}. (2.5) States that can be written as tensor product of 1-qubit states are called product states. States that cannot be written this way are called entangled states. The state T 2 m + T 2 l n ] is an example of an entangled state. The state |0) $ is an example of a product state. 1 1 7!|0)+ 71|i: + (2.6) (2.7) 2. Q U A N T U M INFORMATION PROCESSING 2.3 Evolution of a quantum system A closed quantum system is a system that does not interact with its surroundings. If we assume that qubits form a closed quantum system, then the evolution of their state is described by a linear transformation. Since the resulting state must be normalized, this transformation must be unitary. If we start in a state \v), then after the state evolves according to unitary U, it will end up in the state U\v). Often we want to apply a unitary U only to one qubit, and leave other qubits unchanged. This can be achieved by applying the unitary I®*1 ® U ® I®12 to the state of the system, where i\ + z'2 + 1 is the number of qubits, and U is applied to (z'i + l)-th qubit. Unitary operators can be composed from simpler unitary operators. In quantum computing, we are interested in sets of unitary operators that can decompose arbitrary unitary operator. In chapter 5, we will show how any unitary operator can be decomposed into unitary operators that are supported by IBM quantum computers. 2.4 Measurement Measurements are used to obtain information about the system. The process of measurement is not linear, and therefore the evolution can be no longer described by a unitary operator. The measurement is inherently a random process. Results of measurements cannot be predicted, and only their probabilities are known. Measurements in quantum mechanics are destructive. They collapse the state of a quantum system into a discrete set of states. Repeating the same measurement on the collapsed state will always have the same outcome. 2.4.1 Measurement in the computational basis The measurement in the computational basis is the most basic type of measurement. It is the only type of measurement implemented in current IBM quantum computers. Suppose we perform the measurement 6 2. Q U A N T U M INFORMATION PROCESSING in the computational basis on the state \v) = X>|z>. (2.8) i=Q The measurement will return outcome i with probability \{i\v)\1 =\ai\1 , (2.9) and the system will end up in the state States are normalized vectors, therefore n-l £ K f = l , (2.10) 2=0 where 0 < |flz|2 < 1. The global phase does not change measurement statistics, because the probability of outcome i for the state el< ?\v) is \ei( Pai\2 = ei( f'me-**'a* = a{a* = \a{\2 . (2.11) 2.4.2 Measurement in an orthonormal basis There is nothing significantly different about the computational basis. The measurement can be defined using any orthonormal basis. Suppose { | bn)} is an orthonormal basis, and we measure the state \v) (2.8). Performing the measurement will return outcome i and collapse the state to \bi) with the probability | (b{\v) \2 . In later chapters, we will see how to perform this kind of measurement on a quantum computer that can measure only in the computational basis. 2.4.3 Projective measurement We can define the measurement using an observable. The observable is a Hermitian operator M . Because M is Hermitian, it is diagonalizable and all its eigenvalues are real numbers. We can write M as M = J2mPu (2.12) 7 2. Q U A N T U M INFORMATION PROCESSING where Pj are orthogonal projectors. The probality of outcome i is (v\Pt\v), (2.13) and the state after the measurement is Pi\v) y/(v\Pi\v) (2.14) If Pi are projectors with rank 1, then P,- = |&,-) (&,• | and the measurement corresponds to the measurement in an orthonormal basis, because (v\Pi\v) = (v\bi)(bi\v) = \{h\v)\2 . (2.15) The expected value of M for \v) can be computed as (M) = (v\M\v). (2.16) The expected value can be used to compute coordinates of a state in the Bloch sphere. Observables, which expected value are Bloch sphere coordinates, are called Pauli operators X = |1)(0| + |0)(1| Y = i\l)(0\ -z'|0)(l| (2.17) z = |0)(0| - |1)(1|. The Bloch sphere xyz-coordinates are then ((X), (Y), (Z)). 2.4.4 POVM A more general way of defining a measurement is the positive operator valued measure (POVM) measurement. It does not require orthogonality of its operators. The P O V M is a set of positive operators { E i , E n } , where it holds that E E * = L (2 -1 8 ) i=\ The probability of outcome i is (v\ E, | v). Restrictions on P O V M say that the probability must be non-negative, and that the probability must sum up to 1, because 8 2. Q U A N T U M INFORMATION PROCESSING £ > | E , » = (v\ f^E{\v) = (v\I\v) = (v\v) = 1. (2.19) i=l i=l POVMs can be physically realized, and we will see in later chapters how it can be done on current quantum computers. 2.5 Mixed states Suppose that a measurement in the computational basis is performed on the |+) state, but the outcome of the measurement is unknown. Although the system is either in state |0) or |1), we know only that the state is |0) with probability \ or |1) with probability \. This is one way how to obtain a mixed state. States, such as |+) or |0), are called pure states. Pure states can be seen as special cases of mixed states. Generally, a mixed state is a set {(pi, \ vi))}i, where pi is the probability corresponding to the state \VJ). The set representation is not computationally convenient, and a density operator p = ^pt\vt)(vi\ (2.20) i is used for computations with mixed states. For purposes of this thesis, we will define only the P O V M measurement of p. Suppose that {E\,En} is a P O V M measurement. The probability of outcome i, when performing the measurement on the state p, is Tr(pEf). (2.21) p is always a positive operator with trace 1. Therefore Tr(pEi) > 0 for each 1 < i < n, and £ TripE,) = Tr(p £ E{) = Tr(pl) = Tr(p) = 1. (2.22) i=\ i=\ The definition indeed gives a valid probability distribution. 9 3 Unambiguous state discrimination In this chapter, we review methods for the unambiguous discrimination of pure states. We will first show why these methods are necessary, then we will present methods for unambiguous discrimination of two states with equal prior probability. Finally, we will present a general method for arbitrary pure states with arbitrary prior probabilities. Let us consider the following scenario. Alice and Bob agree upon a pure ensemble. The pure ensemble is a set of pure states. Each state from the ensemble has a probability of being prepared. Alice prepares a state from the ensemble according to its probability. Alice gives the prepared state to Bob. Bob now has to say which state from the ensemble he was given. He is not allowed to make an error, but he can admit that he does not know. His task is to minimize the probability of the inconclusive answer. This is the problem of unambiguous state discrimination (USD). 3.1 Perfect discrimination We say that states can be discriminated perfectly iff the optimal probability of an inconclusive answer is 0. If states are orthogonal to each other, then they can be perfectly discriminated. They form an orthonormal set, and they can be extended into an orthonormal basis. We can perform a measurement in this basis to achieve the perfect discrimina- tion. However, non-orthogonal states cannot be perfectly discriminated. We will show this for states |+), |0). A more general proof can be found in the QCQI book [1, page 87]. Proof. Suppose there exists a P O V M {E\, E2} such that (3.1) Since probabilities sum up to 1, it holds that (0|Ei|0) = 0. (3.2) 11 3- UNAMBIGUOUS STATE DISCRIMINATION Because E\ is a positive operator, it has a unique square root y/E~i. \fE[ is also a positive operator. Notably, it is Hermitian. We can write the inner product as 0 = (0|Ei|0) = = (|0>,Ei|0» n / / , n (3-3) 0), v/Exv/Ex |0)) = V 1 Therefore y/E\\Q) = 0. We can write the probability of outcome 1 given that the state is |+) as (+|Ei|+) = ^«0|Ei|0) + (0|E!|1) + + (l|£i|l» = 1 1 ( 3 " 4 ) = -<1|E!|1> < - < 1, where we used the fact that \fE[\0) = 0, and that (l|Ei|l) is the probability of outcome 1 given that the state is |1). This contradicts our assumption that required (+1 E\ \ +) = 1. • 3.2 Orthogonal projector discrimination First methods proposed for USD worked with a pure ensemble of two states with equal prior probability We denote these states as \p), \ q). Ivanovic [3] proposed a straightforward method, that is not optimal. We define two orthogonal projector measurements P and Q Pi = \p){p\,P2 = I-Pi, Qi = \q)(q\,Q2 = I-Qi. K ' ^ The strategy is to randomly perform the P or Q measurement with some probability. Suppose we perform the measurement defined by P, and get outcome 2. The input state has to be \q), because (p\P2\p)=0. (3.6) 12 3. UNAMBIGUOUS STATE DISCRIMINATION The probability of the conclusive answer given that \q) was on the input is (q\P2\q) = 1 — \{p\q)|2 - Because both states have same prior probabilities, the probability of the conclusive answer is Pc = l(l-\(p\l)\2 ). (3.7) If we perform the measurement defined by Q , then the probability of the conclusive answer stays the same. Although not considered by Ivanovic, this method can be also used for the discrimination of two states with different prior probabilities. Let us denote the prior probabilities of \p), \q) as r,s respectively. The prepared state is a mixed state, and it can be represented as the density operator p = r\p){p\+s\q){q\. (3.8) Probabilities of conclusive outcomes are |2\ Tr(pP2 ) = r(p\P2\p) +s(q\P2\q) = s(l - \ {p\q) Tr(pQ2 ) = r(p\Q2\p) + s(q\Q2\q) = r ( l - \{p\q)2\ (3.9) We can see that Tr(|0Q2) > Tr(pP2) iff r > s. Let a be the probability of performing the measurement P, and 1 — a the probability of performing the measurement Q . Suppose r > s, then it holds that Pc(cc) = a Tr(pP2) + (1 - a) Tr(pQ2) < < a Tr(pQ2) + (1 - a) Tr(pQ2) = Tr(pQ2). { ' ] Therefore to maximize the conclusive probability, we have to set 0, if r > s [0,1] if r = s (3.H) 1, otherwise. The case, where r = s, is the case considered by Ivanovic, and changing oc does not change the probability of the conclusive answer. For other cases, this method completely ignores the less probable state, and always returns the inconclusive answer for it. 13 3. UNAMBIGUOUS STATE DISCRIMINATION 3.3 Optimal discrimination using a sequence of measurements This method was proposed by Ivanovic [3]. It optimally unambiguously discriminates between states \p), \q) with equal prior probabili- ties. The idea is to add a second quantum system that starts in the state s). We then apply a unitary U to the composed system. The action of U is U\p)\s) = a|pi)|si) +0|p2)|s2) , 3 1 2 , l%)|s) = 7| , where (pi\cji) = 0 and (si|s2) = 0. A measurement is performed on the second system. If the outcome is s\, then the measurement of the first system is performed. Because p\ and q\ are orthogonal, they can be perfectly discriminated. Otherwise the answer is inconclusive. Ivanovic considered the case of 1-qubit states. He provided a definition of the unitary U and states from equation 3.12. States \p), \q) are written in a basis {|b\), |fe2)} \p) = v^L&i) + Vl-a\b2) ^31^ \q) = y/a\bi) - Vl - a\b2), where a > \. The second qubit starts in the state \ b\). Although the original paper does not specify, how to find this basis, we propose the following approach. First we define a unitary R \p>) = R\p) = \0) 6 6 (3 14) \cf) =R\q) =cos-|0)+sin-|l). The unitary R is used, because it makes further computations with states easier. In chapter 5, we will show how R can be implemented. The basis {\bi), |fo2)} is then defined as 6 6 |&i) = cos-|0) +sin-|l) 6 6 ( 3 " 1 5 ) \h) = sin-|0) - c o s - | l ) . 14 3. UNAMBIGUOUS STATE DISCRIMINATION States \p'), \c\') written in this basis have the required form with a - cos2 |. The unitary U is defined by its action on \b\b\) and |&2&i) as LZ|&i&i) = v T — a\b\bi) — \fa\b2b2) U\b2b\) = v 7 ! — + \fa\b2b\). (3.16) The action of IT on states I&1&2) and I&2&2) follows from the unitarity of IL States are 1 1 Ipi) = —7=1^1) H—7=L^2> f f (3.17) States are orthogonal as was required in equation 3.12. The probability of conclusive answer is \ {1 — \ (p'\qr ) |2 ) = ^(1 — | {p\q) |2 ). It is obvious that unitary R did not change the probability of conclusive answer. States \p2) and ^2) are generally not the same, and the described procedure can be repeated with them on the input. It leads to a potentially infinite sequence of measurements with total conclusive probability 1 — \ {p\q)\. This probability is optimal, as was shown by Dieks [4]. In practice, the probability gets close to the optimal probability after 3-4 iterations. 3.4 Optimal discrimination optimized Peres [5] showed how the previous sequence of measurements can be replaced with single measurement. He achieved that just by changing the unitary U. The definition of states |&i), I&2)a n d unitary R is the same. The unitary U is defined by its action on \ bibi) and \b2b2) as U\hh) = \l-—-\hh) + J——-\b2b2) U\b2b2) = - A / ^ - V & I ) + y ^ p l W The final states of the system after applying U are (3.18) 15 3. UNAMBIGUOUS STATE DISCRIMINATION U\p')\h) = VT^(\h) + \b2))\h) + V2a-l\b2b2) U\q')\bi) = V l -«(|&i> - \b2))\bi) + V2a-l\b2b2). If the measurement on the second qubit yields result b\, then states of the first qubit are orthogonal to each other as required. The probability of conclusive answer is l - | V / 2 f l - l | 2 = 2 ( l - f l ) = l-\{p\q)\, (3.20) which is optimal. 3.5 2 states with different prior probabilities Jaeger and Shimony [6] examined the case of two states with different prior probabilities. Let us denote the probability of state \p) as r, and suppose W L O G r > \. The idea behind unambiguous discrimination is the same as in Ivanovic method. The input state is evolved according to the equation 3.12, only the states and unitary U have to be chosen differently. The probability of the conclusive answer PQ is maximal iff \P\2 = Tnax{\(p\q)\J?—-,\{p\q)\2 ). (3.21) The value of PQ is then P c = \(p\q)\ (3_22) r(l — |(p|^)|2 ) otherwise. Figure 3.1 shows conclusive probabilities for an ensemble of states 0) and |+), where r is the probability of state |0). The conclusive probability of state |0) is the probability of recognizing state |0), while performing the optimal USD for the whole ensemble. We can see that the state |0) is ignored for small r. The state |+) is ignored for high values of r. For such values of r, the orthogonal projector discrimination from section 3.2 is optimal. 16 3. UNAMBIGUOUS STATE DISCRIMINATION 0.0 0.2 0.4 0.6 0.G L0 Figure 3.1: Optimal conclusive probabilities for an ensemble of |0) and |+), where r is the probability of |0) on the input. Figure 3.2 shows conclusive probabilities for a fixed value of r and varying inner product between states. Although Jaeger and Shimony did not specify the unitary U, we can still use their results to check the correctness of our implementation of the general USD method. 3.6 Optimal discrimination of arbitrary ensembles A geometric method for three state ensembles was proposed by Peres and Terno [7]. It was shown by Chefles [8] that USD of a set of states is possible iff these states are linearly independent. Eldar [9] introduced an optimal method for arbitrary ensembles with linearly independent states. Let n be the number of states and {|i) is denoted by rjj. The measurement will be defined as a P O V M measurement with n + 1 elements. Each state \ defined by O = ^(O+O)-1 . (3.24) Positive operators n z can then be defined as Hi = pi\q>] (^-| for 1 o " (3.27) The condition Tlo > 0 is required, because P O V M elements must be positive operators. 19 4 Qiskit library Qiskit [10] is an open-source framework for quantum computation. It covers every stage of the quantum programming workflow. Its API provides methods for designing quantum circuits, optimizing them, and then simulating them. Qiskit simulators are capable of realistically simulating noisy quantum computers. It is also easy to switch from simulators to real IBM quantum computers by adding an IBMQ token. 4.1 Elements of Qiskit The Qiskit library consists of four parts (elements). The first element is Terra. It provides tools for the composition of quantum circuits. It implements transpilers that transform gates and optimize circuits. The second element is Aer. It provides simulators that run circuits compiled by Terra. These simulators can simulate noisy quantum computers if the noise model is specified. Simulators are a very useful debugging tool because computational time on IBMQ devices is limited. The last two elements of Qiskit are Ignis and Aqua. Ignis is a framework for suppressing errors in quantum circuits, and Aqua is a library with the most common quantum algorithms. 4.2 IBM Quantum IBM provides public access to a number of their quantum computers. If the IBMQ token is set up correctly, then using them is as simple as changing a few lines in the code. Current IBM quantum computers have several limitations. The only gates that can be performed on them are CNOT, U l , U2, U3. The only possible measurement is the measurement in the computational basis. C N O T can be performed only on some pairs of qubits. These pairs are specified by a coupling map of the device. 21 4- QlSKIT LIBRARY 4.3 Circuit model of computation Quantum programs in Qiskit are defined as circuits (4.1). Each single wire in a circuit represents a qubit. In Qiskit, states of all qubits start always in the state |0). Quantum gates represent unitary operators. There are several commonly used gates that have their special symbol. Time in the circuit flows from left to right. The circuit also contains classical bits. They are represented by double wires. Classical bits start in 0, and they are used to store results of measurements. The measurement is represented by a special symbol. Measurements in Qiskit are always performed in the computational basis. These essential parts of quantum circuits can be seen together in an example circuit (4.1). - H Aft /- H \ / _ v.V (4.1) 4.3.1 Common quantum gates Some gates are used so often that they have their unique symbols. They are shown in the table 4.1 together with the unitary operator they represent. CNOT gate applies X to the target qubit whenever the control qubit is in the state 11). Toffoli gate is a variant of the C N O T gate with two control qubits. The U3 gate is a universal 1-qubit gate. It can represent any 1-qubit gate. Gates U2 and U l can be seen as U3 gate with some parameters fixed. Their unitary representation is TTVfl A, x \ - I cos i - e z A s i n f \ U J W , A J - y ^ ^ e ei(— >|o> — •— >a - i n ) ( 11|) c?)I+ |11)<11| <8>X Because U3 gate is universal for 1-qubit gates, it can implement its own adjoint. The relation is U3+ (0,<£,A) = U 3 ( - 0 , - A , - 0 ) . (4.3) 4.4 Transpilers A transpiler is a source-to-source compiler. The functionality of a Qiskit transpiler can be divided into small tasks called passes. These passes can • remove redundant gates, and optimize the circuit, • unroll gates to gates implemented by the device, • swap qubits to match the coupling map of the device. It is important to optimize circuits, because quantum computers are noisy. Therefore longer circuits have worse results. The Qiskit transpilers can decompose 2-qubit unitaries into elementary gates. Unitaries on more qubits, that will be required for the implementation of USD techniques, cannot be decomposed by Qiskit transpilers. We 23 4- QlSKIT LIBRARY are required to write our own decomposition. The Toffoli gate is an exception, because Qiskit transpilers can decompose it into U3 and CNOT gates. 4.5 Providers and backends The Backend class [11] is an interface to a simulator or a quantum device. The Backend object contains parameters of the device such as coupling map and available gates. The Provider class manages backends from one provider. We use Aer provider for simulations and IBMQ provider for experiments on real quantum devices. Aer provides three backends: QasmSimulator simulates a real quantum device. It returns a dictionary of measurement results. StatevectorSimulator returns the final state of the circuit. This is typically used without measurements. UnitarySimulator computes the unitary operator represented by the circuit. The circuit must not contain measurements. StatevectorSimulator and UnitarySimulator can be used to check the correctness of circuits. 4.6 Special simulator functions Running the circuit with a simulator backend has another advantage. We can use initialize and unitary methods of the QuantumCircuit class. The initialize method prepares the starting state of the circuit. Normally all qubits start in state |0). Using this method, we can prepare any input state. This was useful in the process of implementing and testing USD methods, because we could use arbitrary input states, and did not have to come up with preparation circuits. The unitary method can simulate arbitrary unitary gate, which is useful if we do not know how to decompose some unitary. The limitation of these two methods is that they can be used only with simulator backends. 24 4- QlSKIT LIBRARY 4.7 Register endianity Qiskit uses little endian ordering for qubits and classical bits. Our theoretical computations use big endian ordering. It is necessary to change endianity of measurement results to get the expected results. This applies also to results from StatevectorSimulator and UnitarySim- ulator. 25 5 Implementation of unambiguous state dis- crimination In chapter 3, we theoretically described methods for USD. In this chapter, we will present techniques used for the implementation of USD methods on real quantum computers. Described techniques can be used in various areas of quantum information processing. 5.1 Measurement in an orthonormal basis In Qiskit, measurements can be performed only in the computational basis. A technique for performing measurements in any orthonormal basis is required, because this type of measurement is directly used in methods from sections 3.2, 3.3, 3.4. It is also used by the P O V M realization method that will be described in the section 5.4. Suppose we want to perform a measurement in an orthonormal basis {\bi),\bn)}, where n is a power of 2. This measurement can be realized by transforming to \i) using a unitary U U = £ \i)(bi+11 (5.1) i=0 The measurement in the computational basis is then performed. The outcome i corresponds to the state The post-measurement state is then transformed by U - 1 from \i) back to The transformation back to is not necessary if we are interested only in the outcome of the measurement. The operator U is unitary, therefore U - 1 = U + . The whole procedure is shown in the following circuit diagram, 0n Ut _ (5.2) where one wire represents n-qubits for better readability. 27 5. IMPLEMENTATION OF UNAMBIGUOUS STATE DISCRIMINATION 5.1.1 1-qubit orthonormal basis Methods from sections 3.2, 3.3, 3.4 all use measurements in 1-qubit orthonormal basis { I & 2 ) }• The unitary LI for basis transformation from equation 5.1 can be implemented with one U3 gate. Let = a\0) + b\l). Because (&1I&2) = 0, the state \b2) must be of the form \b2) = e'>(-&*|0) +fl*|l». (5.3) Because the global phase is insignificant, we can set

1, we always prepare the qubit with index i for measurement. If the qubit is in the state |0), then the measurement of the qubit with index 0 will yield the conclusive result, and the computation should be stopped. Because we cannot do this directly, all gates in iteration i will be controlled by qubits { 1 , i — 1}. Iterations with inconclusive result set their corresponding qubit to |1). This allows further iterations to continue. 5.4 Realization of POVM In section 3.6 we reviewed a general method for unambiguous discrimination of pure states with arbitrary prior probabilities. It used a P O V M measurement, but it did not specify how to physically realize this measurement. The P O V M had a rank 1 element for each state, and one element with unspecified rank for the inconclusive answer. The P O V M realization is a two step process. Firstly, the P O V M will be decomposed to a P O V M with rank 1 elements. Secondly, the POVM with rank 1 elements will be implemented using a measurement in specific orthonormal basis. 5.4.1 POVM to POVM with rank 1 elements Let us consider a P O V M with elements E\,En. Each E,- is a positive operator, and it has a diagonalization III' E,- = E A ; l A ; > < A ; i (5 -1 0 ) 30 5. IMPLEMENTATION OF UNAMBIGUOUS STATE DISCRIMINATION where m,- is the number of non-zero eigenvalues, Ay 7^ 0. Because Ay > 0, Ay J Ay) (Ay I is a positive operator. Let us denote Ay| Ay) (Ay| by En. Then the set is a valid P O V M measurement with rank 1 elements. If we associate measuring E,y with outcome i, we get the same measurement statistics as for the original POVM. 5.4.2 Neumark theorem construction The P O V M realization method is based on the constructive proof of Neumark theorem [12]. The Neumark theorem claims that P O V M measurements can be realized physically. It is done by extending the quantum system with additional qubits, and then performing a measurement in an orthonormal basis on the bigger system. Suppose we want to perform a P O V M measurement specified by rank 1 elements {E\,En}. Each element can be written as where vectors \ v{) do not have to be normalized. If we write vectors \v{) into rows of a matrix, then this matrix has mutually orthonormal columns. We can add columns to the matrix in such a way, that they will form an orthonormal basis. This extended matrix is unitary. Let us denote its rows as |w,-). Vectors |u;) form an orthonormal basis, and the outcome i of the measurement in this basis corresponds to the measurement of E,-. 5.5 Unitary decomposition All unitary operators from USD methods have to be decomposed into circuits formed by CNOT and U3 gates because these are the only gates supported by current IBM quantum computers. As the unitary decomposition problem has many applications in quantum information processing, many decomposition methods were developed. We chose to implement the method described in the QCQI book [1]. This method uses (9(n2 4w ) 1-qubit and CNOT gates for the decomposition {Ejj\l I |0)0 |0)i |0>2 |0>3 0)auxl 0)aux2 — I A i ( \— T T ° c U J ) 1 Cy- V (5.13) (5.14) - U3 Because auxiliary qubits are returned to the state |0), they can be used for the decomposition of more gates in a sequence. So far the unitary was applied whenever the state of the control qubit was 11). If we want to apply the unitary whenever the state of the control qubit is |0), then we apply N O T gate to the control qubit before and after the controlled gate. This is usually visualized as M A 1 A (5.15) - L I - LT 32 5. IMPLEMENTATION OF UNAMBIGUOUS STATE DISCRIMINATION 5.5.2 Two-level unitary A unitary that has non-trivial action on at most two states is called a two-level unitary. Such unitary was directly used in the USD method by Peres (3.4). A unitary composed from two two-level unitaries was used in the iterative USD method by Ivanovic (3.3). Suppose that the two-level unitary acts on n-qubit states \k) and \m), where 0 < k, m < 2n . The action of this unitary on \k) and \m) is specified by a 1-qubit unitary U. We can find the shortest sequence of binary numbers {a\,a\), where a\ — k,a\ — m, and each successive number differs in exactly one bit from the previous one. Let us denote by bi the position, where this bit is for numbers a, and flj+i. For each 1 < i < I — 2 we add a multicontrolled N O T to the circuit. It has n — 1 control qubits, and it applies NOT to the fy-th qubit. Bits (except bi-ih bit) of a,- set to 1 specify positions of qubits that control target iff they are in state 11). Bits set to 0 specify positions of qubits controlling iff they are in state |0). For i = I — 1 we replace N O T gate with IT. Changes to other states than \k) and \m) are reverted by applying multicontrolled NOT gates in the reverse order. 5.5.3 Decomposing unitary into two-level unitaries Two-level unitaries can be used to decompose an arbitrary unitary matrix. The decomposition proceeds by columns. Concrete steps are described in the QCQI book [1, page 189]. A n-qubit unitary is decomposed into 0(4") two-level unitaries. This decomposition is directly used in the implementation of the general USD method (3.6) for the measurement in an orthonormal basis from the Neumark theorem construction. 5.6 Mitigation of problems with floating-point arithmetic Computers represent real numbers as approximations using a finite number of bits. Therefore operations with real numbers are imprecise, mathematical identities do not have to hold, and algorithms do not have to work as expected. It is necessary to employ techniques that 33 5- IMPLEMENTATION OF UNAMBIGUOUS STATE DISCRIMINATION are robust to these imprecisions. We present mitigation techniques that were required for the robust implementation of USD methods. 5.6.1 Floating-point number comparison The most common operation used in the implementation is the comparison of floating-point numbers. It is used in unit and randomized tests to check correctness. It is used in functions that test properties of matrices and vectors. Direct comparison of two floating-point numbers, as can be done with integers, does not produce required results. Instead, the difference between numbers has to be checked. A n appropriate allowed difference (tolerance) must be chosen. It is not enough to compare only the absolute difference between numbers, because if numbers were small, then their absolute difference could be lower than the tolerance, and still they could be quite different. The solution is to define also relative tolerance. The comparison equation used by the NumPy library1 is where a, b are numbers being compared, e is the absolute tolerance, 5 is the relative tolerance. Our implementation and Qiskit library use NumPy isclose method for comparison of floating-point numbers. 5.6.2 Matrix properties Checks for matrix properties are used in many places. Functions for unitary decomposition require a unitary matrix on the input. The POVM measurement consists of positive operators. Properties of input matrices are checked to ensure correctness. These checks should be robust to imprecisions of floating-point arithmetic. Otherwise, there will be false positives, and valid inputs will be considered invalid. The check we found most susceptible to errors was the check for positivity. Qiskit and also our implementation test positivity by checking whether the matrix is Hermitian, and then checking that eigen- 1. https://numpy.org/doc/stable/reference/generated/numpy.isclose (5.16) 34 5- IMPLEMENTATION OF UNAMBIGUOUS STATE DISCRIMINATION values are nonnegative. However, the eigenvalue decomposition can return small negative eigenvalues even for positive matrices. Tolerance e > 0 is therefore chosen, and it is checked that for each eigenvalue A, it holds that Ať + e > 0. (5.17) Another problem was enco untered while using the Qiskit unitary method (4.6), and when testing unitarity of inputs to internal classes of our implementation. The unitarity check is done by checking that UUf « I. (5.18) Algorithms do ing P O V M realizatio n and unitary decomposition in our implementation, although correct in infinite precision setting, can return matrices that do not pass this check. Also it can happen that a matrix Li passes this unitarity test, but lf+ do es not pass it. One so lutio n is to set different to lerance or to avoid checking matrix properties, when passing them between internal functions. The problem with this solution is that we cannot change the tolerance used by Qiskit in its QuantumCircuit.unitary method. We need a way to change an almost unitary matrix A into a unitary matrix A such that it is as clo se as po ssible to A. This can be do ne2 by co mputing the singular value deco mpo sitio n A = ITLV^, and setting A = U V + . 5.6.3 Extending orthogonal states to orthonormal basis In the Neumark theorem co nstructio n (5.4.2), we extended a list o f mutually orthogonal states to an orthonormal basis. This can be do ne with the fo llo wing approach. Let {\v\),|i7fc)} be a set o f mutually orthogonal states from a ndimensional Hilbert space %. We iteratively add \ i) fo r 0 < i < n — 1 to the set iff the set extended with states fro m previo us iteratio ns combined with | i) forms a linearly independent set of states. We are left with a set {\v\),..., \vn)}, where |i7,- ) fori < i < k are the original states. This set fo rms a basis of %, but it is not o rtho no rmal. No w it should be enough to do the Gram-Schmidt process, but the traditional Gram- 2. https://people.eecs.berkeley.edu/~wkahan/Mathl28/NearestQ.pdf 35 5. IMPLEMENTATION OF UNAMBIGUOUS STATE DISCRIMINATION Schmidt process is not numerically stable. It is therefore necessary to do a modified Gram-Schmidt3 process that is numerically stable. In our experience, for some mutually orthogonal states even this modified process did not yield an orthonormal basis. The modified Gram-Schmidt process is therefore repeated for 100 iterations, where output of one iteration is passed as input to next iteration. It was confirmed by randomized testing, that this can produce an orthonormal basis with high precision. 3. https://www.math.uci.edu/~ttrogdon/105A/html/Lecture23.html 36 6 QUSD package We implemented unambiguous discrimination methods that were theoretically described in chapter 3. We used techniques from chapter 5 for the implementation. Implemented methods can be accessed through the API of QUSD (Qiskit unambiguous state discrimination) package. In this chapter, we describe the API of the package, we point to example Jupyter notebooks, we describe tests for the package. Finally we also evaluate the correctness of our implementation. 6.1 Used libraries The QUSD package was implemented in Python3, and it uses three libraries: NumPy is a package for scientific computing. Its linear algebra functions are used for most computations in QUSD package. Qiskit is the package described in chapter 4. It is used for creating circuits and simulating them. CVXPY is a package for convex optimization. It is used for the optimization of SDP 6.2 API QUSD package provides a united interface to all USD methods. Each USD class corresponds to one USD method: OrthogonalProjectorUSD (3.2), PeresUSD (3.4), IvanovicUSD (3.3), P O V M J J S D (3.6). Constructors of these classes take a PureEnsemble object. The PureEnsemble class represents the ensemble of pure states. IvanovicUSD class is the only exception, as the number of iterations must be also specified. The interface to these classes is specified by the USDBase class. The specifications of public methods are described in the documentation, here we only briefly comment on their usage. The get_required_registers method returns the number of quantum and classical bits that the circuit implementing given method will 37 6. QUSD PACKAGE use. The get_theoretical_probabilities method returns a dictionary that contains overall probabilities of answers for the ensemble, and also probabilities of answers given the prepared state is one of the states from the ensemble. The discriminate method runs the discrimination method for a specified number of samples, and returns results. The user can provide arbitrary backend, such as IBMQ backend. The discriminate_statevector method uses the StatevectorSimulator from the Qiskit library. Instead of sampling and returning counts as discriminate method does, it returns precise probabilities of results computed by the simulator. This is very useful for testing and debugging. Apart from USD methods, unitary decomposition is available from the UnitaryDecomposer class, and P O V M realization is available from the POVMRealization class. 6.3 Examples We provide 4 example Jupyter notebooks: 01_2state_usd.ipynb notebook shows how to use classes OrthogonalProjectorUSD, PeresUSD, and IvanovicUSD. It compares their conclusive answer probabilities for the state |0) and states cos^|0)+sin^|l), (6.1) where 0 < 9 < n. 02_Nstate_usd.ipynb notebook shows how to use the P O V M _ U S D class, and it shows that it does the optimal USD for the ensemble from Peres and Terno [7] paper. 03_unitary_decomposition.ipynb notebook shows how the methods for unitary decomposition can be used out of the USD context. 04_quantum_device_experiment.ipynb runs POVM_USD and PeresUSD on a real IBM quantum computer. Because current quantum computers are noisy, it is possible to get an incorrect answer when using them as a backend. 38 6. QUSD PACKAGE POVM USD randomized test precisions 7000 H le-3 le-4 le-5 le-6 Le-7 Le-S le-9 Le-10 precision Figure 6.1: This histogram shows precisions for randomized tests of POVM_USD class. Tests ran with 10000 random ensembles. 6.4 Tests and evaluation The package is tested extensively by unit tests. Unit tests have 100% code coverage. Tests for USD classes use the Qiskit StatevectorSimulator to get precise measurement statistics. They compare actual results to theoretically computed results to 10~8 precision. Tests for POVM_USD use the ensemble from Peres and Terno [7] paper, and theoretically computed results for 2 state ensembles with different prior probabilities using computations from section 3.5. Along with unit tests, we implemented randomized tests for all USD classes and unitary decomposition. Randomized tests for unitary decomposition decompose a random unitary, and compare results from Qiskit UnitarySimulator with the original unitary up to 10~8 precision elementwise. Tests ran for over 100000 random unitaries on different numbers of qubits. 39 6. QUSD PACKAGE Randomized tests for USD classes generate random ensembles. They use the discriminate_statevector method of USD classes, because it returns precise measurement statistics. They compare simulation results with probabilities computed by the get_theoretical_probabilities method. They check whether the absolute difference is below some threshold, get_theoreticalprobabilities returns analytically computed probabilities for classes OrthogonalProjectorUSD, PeresUSD and IvanovicUSD. For P O V M _ U S D class it returns probabilities computed using the semidefinite programming optimization. For classes OrthogonalProjectorUSD, PeresUSD and IvanovicUSD, we ran randomized tests with over 10000 random ensembles. Absolute differences between simulated and theoretical probabilities were lower than 1 0 - 8 for all random ensembles. Randomized tests for the P O V M _ U S D class tested random ensembles on 1, 2, 3 and 4 qubits with all possible numbers of states. Worst absolute differences between simulated and theoretical probabilities were lower than 10 ~4 . This precision seems worse than for other classes. In figure 6.1 is the histogram of precisions for 10000 random ensembles. Although the precision seems worse, it is actually worse for only a smaller number of cases. We believe that the reason for lower precision in some cases is the more complicated computation in P O V M _ U S D class, and the fact that absolute difference behaves badly when comparing numbers close to 0. Optimal USD often ignores less probable states, and states measured with zero probability are encountered often. 40 7 Conclusion We introduced the quantum information processing framework. We defined operations that can be done on quantum systems. Then we reviewed unambiguous state discrimination methods. The first few described methods discriminated ensembles of two pure states with equal prior probabilities. Lastly, we described a general method for optimal unambiguous discrimination of arbitrary pure ensembles. Theoretical descriptions of U S D methods did not specify how they should be implemented on real quantum devices. Therefore, we described the techniques required for the implementation of U S D methods. We showed how limitations posed by the Qiskit library and IBM quantum computers could be overcome. We showed how P O V M measurements can be realized, and how unitaries used by USD methods can be decomposed into circuits. Then we briefly described the Qiskit library. We focused mainly on features that helped us with writing implementations of USD methods, testing them, and debugging them. Then we described the API of the QUSD package. Example Jupyter notebooks show how the package can be used. In one notebook, we ran the USD methods on IBM quantum computers to show that it is really possible as it was claimed throughout this thesis. As part of the implementation, we wrote extensive unit tests. To ensure the robustness of the implemented methods, we also wrote randomized tests. These tests showed to be incredibly useful for finding problems with floating-point arithmetic. We believe that our implementation is robust and correct. 41 A Linear algebra for quantum information pro- cessing In this appendix, we present notions and theorems from linear algebra that are extensively used in the field of quantum information processing. A l l considered vector spaces in this thesis are finite dimensional vector spaces over complex numbers with inner product. They are often referred to as Hilbert spaces. We denote the set of all linear operators on a vector space % as C(H). Definition A . l . Lř G £{T~t) is called unitary iff LÍLÍ+ = I. Theorem A.2. Unitary operators preserve inner pro duct. Quantum states are normalized vectors, and the previous pro perty of unitary operators is necessary to keep states normalized after the unitary evolution. Definition A.3. B G C{U) is called adjo int o f A G C{U) iff fo r all \u),\v) G U it holds that (B\u),\v)) = (\u),A\v)). This o perato r always exists and is unique. We deno te the adjo int of A as A + . Theorem A.4. If Li G C(H) is a unitary operator, then Lř- 1 = Uf . This theorem is used a lot, because we often need to find the inverse of a unitary operator, and taking adjoint is simpler than co mputing the inverse. Definition A.5. H G C{H) is called Hermitian or self-adjoint iff H = H + . Theorem A.6. Hermitian operators are no rmal, and they have real eigenvalues. Definition A.7. A G is called positive iff for all \u) G H it holds that (K|A|K) > 0. 43 A. LINEAR ALGEBRA FOR QUANTUM INFORMATION PROCESSING Usually, in linear algebra, the operator A is called positive semidefinite, but in quantum computing literature, it is usually called a positive operator. Therefore, we call it positive in this thesis. The positivity of A is denoted by A > 0. Theorem A.8. Positive operators are Hermitian, and they have real nonnegative eigenvalues. 44 Bibliography 1. NIELSEN, Michael A.; C H U A N G , Isaac L. Quantum computation and quantum information. 10th anniversary ed. New York: Cambridge University Press, 2010. ISBN 978-1-107-00217-3. 2. K A Y E , Phillip; L A F L A M M E , Raymond; M O S C A , Michele. An Introduction to Quantum Computing. New York: Oxford University Press Inc., 2007. ISBN 978-0-19-857049-3. 3. IVANOVIC, Igor. How to differentiate between non-orthogonal states. Physics Letters A. 1987, vol. 123, no. 6, pp. 257-259. ISSN 0375-9601. Available from DOI: 10.1016/0375-9601 (87) 90222- 2. 4. DIEKS, Dennis. Overlap and distinguishability of quantum states. Physics Letters A. 1988, vol. 126, no. 5, pp. 303-306. ISSN 0375-9601. Available from DOI: 10.1016/0375-9601 (88) 90840-7. 5. PERES, Asher. H o w to differentiate between non-orthogonal states. Physics Letters A. 1988, vol. 128, no. 1, pp. 19. ISSN 0375- 9601. Available from DOI: 10.1016/0375-9601(88)91034-1. 6. JAEGER, Gregg; SHIMONY, Abner. Optimal distinction between two non-orthogonal quantum states. Physics Letters A. 1995, vol. 197, no. 2, pp. 83-87. ISSN 0375-9601. Available from DOI: 10.1016/ 0375-9601(94)00919-G. 7. PERES, Asher; TERNO, Daniel R. Optimal distinction between non-orthogonal quantum states. Journal of Physics A: Mathematical and General. 1998, vol. 31, no. 34, pp. 7105-7111. Available from DOI: 10.1088/0305-4470/31/34/013. 8. CHEFLES, Anthony. Unambiguous discrimination between linearly independent quantum states. Physics Letters A. 1998, vol. 239, no. 6, pp. 339-347. ISSN 0375-9601. Available from DOI: 10.1016/ S0375-9601(98)00064-4. 9. ELDAR, Yonina. A semidefinite programming approach to optimal unambiguous discrimination of quantum states. IEEE Transactions on Information Theory. 2003, vol. 49, pp. 446^156. Available from DOI: 10.1109/TIT. 2002.807291. 45 BIBLIOGRAPHY 10. A B R A H A M , Hector et al. Qiskit: An Open-source Frameworkfor Quantum Computing. 2019. Available from DOI: 10.5281/zenodo. 2562110. 11. M C K A Y , David C. et al. Qiskit Backend Specifications for OpenQASM and OpenPulse Experiments. 2018. Available from arXiv: 1809.03452 [quant-ph]. 12. BOUDA, Jan. Density Matrices And Superoperators [online]. 2001 [cit. 2020-05-01]. Available also from: https : / / i s .muni . cz/th/ h21v6. Master's thesis. 46