Open access peer-reviewed chapter - ONLINE FIRST

Joint EigenValue Decomposition for Quantum Information Theory and Processing

Written By

Gilles Burel, Hugo Pillin, Paul Baird, El-Houssaïn Baghious and Roland Gautier

Reviewed: January 27th, 2022Published: April 2nd, 2022

DOI: 10.5772/intechopen.102899

IntechOpen
Matrix Theory - Classics and AdvancesEdited by Mykhaylo Andriychuk

From the Edited Volume

Matrix Theory - Classics and Advances [Working Title]

Dr. Mykhaylo I. Andriychuk

Chapter metrics overview

13 Chapter Downloads

View Full Metrics

Abstract

The interest in quantum information processing has given rise to the development of programming languages and tools that facilitate the design and simulation of quantum circuits. However, since the quantum theory is fundamentally based on linear algebra, these high-level languages partially hide the underlying structure of quantum systems. We show that in certain cases of practical interest, keeping a handle on the matrix representation of the quantum systems is a fruitful approach because it allows the use of powerful tools of linear algebra to better understand their behavior and to better implement simulation programs. We especially focus on the Joint EigenValue Decomposition (JEVD). After giving a theoretical description of this method, which aims at finding a common basis of eigenvectors of a set of matrices, we show how it can easily be implemented on a Matrix-oriented programming language, such as Matlab (or, equivalently, Octave). Then, through two examples taken from the quantum information domain (quantum search based on a quantum walk and quantum coding), we show that JEVD is a powerful tool both for elaborating new theoretical developments and for simulation.

Keywords

  • quantum information
  • quantum coding
  • quantum walk
  • quantum search
  • joint eigenspaces
  • joint eigenvalues
  • joint eigenvectors

1. Introduction

The field of quantum information is experiencing a resurgence of interest due to the recent implementation of secure transmission systems [1] based on the teleportation of quantum states in metropolitan networks and in the context of satellite transmissions, further underscored by the development of quantum computers. A new path for intercontinental quantum communication opened up in 2017 when a source onboard a Chinese satellite made it possible to distribute entangled photons between two ground stations, separated by more than 1000 km [2, 3]. Experiments using optical fibers [4] and terrestrial free-space channels [5] have also proved that the use of quantum entanglement can be achieved over large distances.

Quantum programming languages, such as Q# [6] have been developed to facilitate the design and simulation of quantum circuits. The underlying quantum theory is quite complex and often counter-intuitive due to the fact that it relies on linear algebra and tensor products—for instance, the state of a set of three independent qubits (quantum bits) is not described by a 3-dimensional vector, as would be the case for classical bits, but by a 23-dimensional vector which lives in a Hilbert space constructed by tensor products of lower-dimensional spaces. Therefore, these programming languages are helpful for people who do not need to bother with the underlying theory.

However, since the quantum theory is fundamentally based on linear algebra, there are cases of practical interest for the researcher in which keeping a handle on the matrix representation of the quantum systems is a fruitful approach because it allows the use of powerful tools of linear algebra to better understand their behavior and to better implement simulation programs.

In this chapter, our objective is to illustrate how the concept of Joint EigenValue Decomposition (JEVD) can provide interesting results in the domain of quantum information. The chapter is organized as follows. In Section 2, we give some mathematical background and in Section 3, we provide basic elements to understand quantum information. Then, in Section 4, we show an example of the application of JEVD to quantum coding, more precisely we propose an algorithm, based on JEVD, to identify a quantum encoder matrix from a collection of given Pauli errors. Finally, in Section 5, we show that JEVD is a powerful tool for the analysis of a quantum walk search. More precisely, we prove that, while the quantum walk operates in a huge state space, there exists a small subspace that captures all the essential elements of the quantum walk, and this subspace can be determined thanks to JEVD.

Advertisement

2. Mathematical background

2.1 Matrices and notations

We note UTthe transpose of a matrix Uand Uthe transpose conjugate of U.

His the normalized Hadamard 2×2matrix and HNthe N×NHadamard matrix obtained by the Kronecker product (defined in the next subsection):

H=121111andHN=HnN=2nE1

INis the N×Nidentity matrix (which will sometimes be noted Iwhen its dimension is implicit).

In the domain of quantum information processing, we mainly have unitary matrices. A square matrix Uis unitary [7] if UU=UU=I. The columns of a unitary matrix are orthonormal and its eigenvalues are of norm 1. If the unitary matrix is real, its eigenvalues come by conjugate pairs.

We call “shuffle matrix” the permutation matrix Pa,bwhich represents the permutation obtained when one writes elements row by row in an a×bmatrix and reads them column by column. For instance, set a=2and b=3. If one writes the elements 1,2,3,4,5,6row by row in a 2×3matrix and reads them column by column, the order becomes 1,4,2,5,3,6. Then the shuffle matrix is the permutation matrix such that 142536=123456P2,3. The inverse of Pa,bis Pb,a=Pa,bT.

Gnis the n×nGrover diffusion matrix defined by [8]:

Gn=In+2θnθnTE2

where θnthe n×1vector is defined by θn=111T/n. It is easy to see that Gnθn=θn. Therefore, θnis an eigenvector of Gnwith eigenvalue +1. We can also see that for any vector vorthogonal to θnwe have Gnv=v. It follows that Gnhas two eigenvalues, 1and +1, and the dimensions of the associated eigenspaces are n1and 1.

2.2 Kronecker product

The Kronecker product, denoted by , is a bilinear operation on two matrices. If Ais a k×lmatrix and Bis a m×nmatrix, then the Kronecker product is the km×lnblock matrix Cbelow:

C=AB=a11Ba1lBak1BaklBE3

Assuming the sizes are such that one can form the matrix products ACand BD, an interesting property, known as the mixed-product property, is:

ABCD=ACBDE4

The Kronecker product is associative, but not commutative. However, there exist permutation matrices (the shuffle matrices defined in the previous subsection) such that, if Ais an a×asquare matrix and Ba b×bsquare matrix, then [9]:

ABPa,b=BAPb,aE5

2.3 Singular value decomposition, image, and kernel

The Singular Value Decomposition (SVD) of an m×nmatrix Ais [7]:

A=USVE6

where Uand Vare unitary matrices, and Sis diagonal. The diagonal of Scontains the Singular Values, which are real nonnegative numbers, ranked by decreasing order. The sizes of the matrices are Um×m, Sm×nand Vn×n. The SVD is a very useful linear algebra tool because it reveals a great deal about the structure of a matrix.

The image and the kernel of Aare defined by:

ImA=yCm:y=Axfor somexCnE7
kerA=xCn:Ax=0E8

When used in an algorithm, the notation nullwill also be used for a procedure that computes a matrix whose columns are an orthonormal basis of the kernel of A.

The complement of a subspace Awithin a vector space His defined by:

Ac=yH:xy=0forallxAE9

In an algorithm, if the columns of Aare an orthonormal basis of Athen the columns of B=nullAprovide an orthonormal basis of Ac.

The rank of Ais its number of nonzero singular values. When programmed on a computer determination of the rank must take into account finite precision arithmetic, which means that “zero” is replaced by “extremely small” (less than a given tolerance value). Let us note r=rankA. We have

dimImA=rE10
dimkerA=nrE11

An orthonormal basis of kerAis obtained by taking the last nrcolumns of the matrix V.

2.4 Joint eigenspaces and joint eigenvalue decomposition (JEVD)

The eigenvalue decomposition of a unitary matrix Ais:

A=VDVE12

where Dis a diagonal matrix, the diagonal of which contains the eigenvalues, and Vis a unitary matrix whose columns are the eigenvectors.

Let us note EλAthe eigenspace of an operator Aassociated with an eigenvalue λ.The joint eigenspace Eλ,μA,Bis:

Eλ,μA,B=EλAEμBE13

A property of great interest in quantum information processing is that within Eλ,μA,B(and even within any union of joint eigenspaces) the operators Aand Bcommute.

Determination of the joint eigenspace on a computer may be determined through the complement, because:

EλAEμB=EλAcEμBccE14

Using Matrix-oriented programming languages, such as Matlab or Octave, this requires only a few lines. Let us note Aλand Bμmatrices whose columns are orthonormal bases of EλAand EμBand .the horizontal concatenation of matrices. The following computation procedure provides a matrix Cwhose columns are an orthonormal basis of Eλ,μA,B:

C=nullnullAλnullBμE15

However, it is not efficient in terms of complexity and in the next sections we will propose faster computational procedures, adapted to each context.

A lower bound on the dimension of a joint eigenspace can be obtained as follows. Let us note nthe dimension of the full space. We have, obviously:

dimEλAEμBnE16

and we know that:

dimEλAEμB=dimEλA+dimEμBdimEλAEμBE17

Combining both equations, we obtain:

dimEλ,μA,BdimEλA+dimEμBnE18
Advertisement

3. Quantum information principles

A quantum system is described by a state vector ψCN, where Nis the dimension of the system. Since in the quantum formalism states ψand γψare equivalent, for any nonzero complex number γ, the state is usually represented by a normed vector and the global phase is considered irrelevant.

As long as it remains isolated, the evolution of a quantum system is driven by the Schrödinger equation. The latter is a first-order differential equation operating on the quantum state. Its integration shows that the quantum states at times t1and t2are linked by a unitary matrix Usuch that ψ2=Uψ1. The norm is preserved because Uis unitary.

The second kind of evolution, called “measurement,” may occur if the system interacts with its environment. A measurement consists of the projection of the state onto a subspace of CN. When the measurement is controlled, it consists in defining a prioria decomposition of the state space into a direct sum of orthogonal subspaces iHi. The measurement randomly selects one subspace. The result of the measurement is an identifier of the selected subspace (for instance, its index i). After measurement, the state is projected onto Hi. If Piis the projection matrix onto Hi, then the state becomes Piψ(which is then renormalized because the projection does not preserve the norm). The probability of Hibeing selected is the square norm of Piψ.

It is worth noting that a measurement may destroy a part of quantum information (because usually, a projection is an irreversible process), while the unitary evolution is reversible, and as such, preserves quantum information. Consequently, measurements must be used with extreme caution—how to design the system and the measurement device to measure only what is strictly required and not more is one of the difficult problems encountered in quantum information processing.

Quantum systems of special interest for quantum information processing are qubits (quantum bits) and qubit registers. A qubit belongs to a 2D quantum system with state a normed vector of C2. To highlight links with classical digital computation, it is convenient to note 0and 1for the orthonormal basis of C2. Physically any 2D quantum system can carry a quantum bit. For instance, the spin of an electron is a 2D quantum system, and the spins up and down can be associated with the basic states 0and 1. A general qubit has an expression:

ψ=α00+α11E19

where α0and α1are complex numbers subject to α02+α12=1.

A qubit register is a 2n-D quantum system which, for convenience, is usually referred to as a standard orthonormal basis noted 0…000…010…101…11and then, by analogy with classical digital processing, nis the number of qubits. For instance, for n=2the basis is 00011011, where ab=ab, and the quantum state of the register is:

ψ=ab012γababE20

Note that, contrary to classical digital registers, the qubits are usually not separable, hence the register must be considered as a whole. We say that the qubits are entangled. However in the special case where the coefficients γabcan be decomposed in the form γab=αaβbthe state can be written as a tensor product of the states of two qubits, which can be considered separately. Then, we have:

ψ=α00+α11β00+β11E21
Advertisement

4. Application of JEVD to quantum coding

4.1 Principle of quantum coding

The objective of quantum coding is to protect quantum information [10]. In the classical domain, the information can be protected using redundancy—for instance, if we want to transmit bit 0 on a noisy communication channel, we can instead transmit 000 (and, similarly, transmit 111 instead of 1). On the receiver side, if one error has occurred on the channel, for instance, if the second bit is false, we receive 010 instead of 000, from which we can still guess that the most probable hypothesis is that the transmitted word was 000. Of course, if there were two errors the transmitted word could have been 111, but it is assumed that the probability of error is low, hence two errors are less likely than one error. More elaborated channel codes have been proposed, but fundamentally they are all based on the idea of adding redundancy and assuming that the probability of channel error is low.

In the quantum domain, it is impossible to use redundancy because it is impossible to copy a quantum state (this is due to the “no-cloning theorem” [11]). However, we can use entanglement to produce the quantum equivalent of classical redundancy. The principle of quantum coding is shown in Figure 1. Assume we want to protect the quantum state ψof a k-qubit register. We add rancillary qubits initialized to 0to form an n-qubit register (n=k+r). The encoder is represented by a unitary 2n×2nmatrix U. Then, errors may occur on the encoded state: they are represented by a unitary matrix E. The decoder is represented by another unitary matrix Uwhich is the transpose conjugate of the encoding matrix. Finally, we measure the last rqubits of the decoded state, and, depending on the result of the measurement, we apply the appropriate restoration matrix Uc(which is a unitary matrix of size 2k×2k) to the k-qubit register composed of the first kqubits of the decoded state.

Figure 1.

Principle of quantum coding.

As an illustration, let us consider n=2, k=1and the very simple quantum encoder shown in Figure 2. It is a basic quantum circuit known as the CNOT quantum gate, and it is represented by the unitary matrix below:

Figure 2.

CNOT quantum gate.

U=1000010000010010E22

A quantum error on a qubit is described by a 2×2unitary matrix. It is convenient to decompose the error as a linear sum of the identity and the Pauli matrices below [12]:

Z=1001X=0110Y=0ii0E23

Let us consider that an error may appear on the first encoded qubit and that this error, if present, is represented by the unitary Pauli matrix X. Then, the error matrix which acts on the encoded state is:

E=XI=0100100000010010E24

It is easy to check that:

F=UEU=0001001001001000=XXE25

The state at the input of the encoder is α0α1T10T=α00α10T. The state at the output of the decoder is, therefore, 0α10α0T.

Measuring the second qubit on the output of the decoder consists in decomposing the state space into a direct sum H0H1of two subspaces spanned by 0010and 0111. The result of the measurement will be either 0 or 1 (index of the selected subspace), and by analogy with classical decoding, this result will be called the “syndrome.” The projections on these subspaces are 00Tand α1α0T. Then the probability to obtain syndrome 1is 1.

The measurement then projects the state onto H1. Note that in this particular case, the information is preserved by the projection. Then, applying the operator Uc=Xto the projected state restores the initial state.

Similarly, if there is no error, we can see that Fis the identity matrix, then the projections on the subspaces are α0α1Tand 00T. In that case, the syndrome is 0 and the state is projected onto H0. Correction is done by applying the operator Ito the projected state, which is equivalent to doing nothing.

The very simple code used above, as an illustration, cannot correct more complex errors (for instance, an error Zon the first qubit). However, there exist efficient quantum codes, such as the Steane code [13], and the Shor code [14]. A remarkable result of quantum coding theory is that a linear combination of correctable errors is correctable [15].

Figure 3 shows the Steane Encoder, which is a n=7k=1t=1quantum encoder. This means that it encodes k=1qubits on n=7qubits and it is able to correct any error occurring on t=1encoded qubits. It is built with Hadamard (Eq. (1)) and CNOT (Eq. (22)) quantum gates. From this circuit description, it is possible to obtain the coding matrix U.

Figure 3.

Steane encoder.

4.2 Determination of encoder matrix using JEVD

The problem we address can be stated as follows (see Figure 1 for the notations)—given a list of nindependent Pauli errors Eiwith corresponding diagonal outer errors Fi, determine the unitary operator U(quantum encoder) such that:

UEiU=Fii1nE26

This equation shows that the columns of Uare the eigenvectors of Ei. Specification of the code by a small set of Pauli errors is very convenient and the interest of automatic determination of matrix Uis to allow further simulations of the behavior of the quantum code in various configurations.

To illustrate and validate the approach that will be developed below, let us consider the collection of n=7Pauli errors shown in Table 1. Here, to be able to check the results, this collection has been chosen to correspond to the Steane encoder (Figure 3), while in a standard application of the method, it would be given a priori. The interest is that here we can compute the encoder matrix from the circuit and this will allow us to check that our method produces the correct encoder matrix.

EiFi
ZZZZZZZZIIIIII
XXIIIXXIZIIIII
XIXIXIXIIZIIII
XIIXXXIIIIZIII
ZZIIIZZIIIIZII
ZIZIZIZIIIIIZI
ZIIZZZIIIIIIIZ

Table 1.

Collection of Pauli errors.

We use nindependent equations in which each Fiis a tensor product of Iand Zonly (including only one Z). Therefore, matrices Fiare diagonal, and their diagonal elements are +1and 1in equal numbers.

Figure 4 shows the diagonals of the matrices Fi(each row corresponding to one diagonal). Values 1and +1are represented, respectively, by black and white dots.

Figure 4.

Diagonals of matricesFi.

Since matrix Udoes not depend on iin Eq. (26) its columns are joint eigenvectors of the Ei. For instance, in the example above, the 20thcolumn of Uis a joint eigenvector of E1, E2, …, E7associated to eigenvalues +1,+1,1,+1,+1,1,1(see Figure 4). In the general case, the set of neigenvalues corresponding to the column cof Uis easily obtained by taking the binary representation of c1with the mapping 0+1and 11.

Now, let us consider the determination of column cof U. We know that it is a vector spanning a joint eigenspace of the Eicorresponding to a given set of eigenvalues λii=1n. For each Eilet Aidenote the 2n×2n1matrix whose orthonormal columns span the eigenspace associated to λiand Bithe 2n×2n1matrix whose orthonormal columns span the kernel of Ai(which corresponds to the eigenspace associated to λi).

Let Ykdenote the joint eigenspace corresponding to eigenvalues λjj=1kwith k1n. We propose Algorithm 1 to efficiently compute the column of U. It computes a series of matrices Ykwhose columns are an orthonormal basis of Yk. Obviously, the searched column of Uis Yn. For the moment, let us consider that Kc=1 (the optimal value will be discussed later).

ifKc=1thenY1=A1endfork=Kc+1tondoCk=BkYk1Zk=nullCkYk=Yk1Zk

Algorithm 1:Algorithm for determination of a joint eigenspace.

The sizes of the matrices are decreasing with k:

Ck: 2n1×2nk+1Zk: 2nk+1×2nkYk: 2n×2nk.

The intuitive ideas under the algorithm are the following:

  • Ck=BkYk1: The orthonormal basis of Yk1is projected on the kernel of Ak. The components of the projected vectors are expressed in the orthonormal basis Bkof that kernel. Consequently, ImCkis the projection of Yk1on the kernel of Ak, expressed in that kernel.

  • A matrix Zkwhose columns are an orthonormal basis of the complement of this projection is determined.

  • Finally, the components of the basis vectors are restored to the original space by Yk=Yk1Zk

Let us prove that the matrices Ykhave orthonormal columns. This is obviously the case for k=1. Then, by recursion, we have:

YkYk=ZkYk1Yk1Zk=IE27

Now, let us prove, by recurrence, that ImYk=Yk.

Obviously, this is the case for k=1. Assume this is the case for k1. We have:

ImYkImYk1=Yk1E28

We have also:

BkYk=BkYk1Zk=BkYk1Zk=CkZk=0E29

Then

ImYkkerBk=ImAkE30

From ImYkYk1and ImYkImAkwe deduce ImYkYk.

Conversely, assume that a vector xbelongs to Yk. Because YkYk1there exists a vector bsuch that x=Yk1band because xImAkwe have also Bkx=0

Then

BkYk1b=0Ckb=0a:b=Zka

Therefore x=Yk1b=Yk1Zka=YkaxImYkYkImYk.

After execution of the algorithm to determine each column of U, there remains an indetermination because the joint eigenvectors (i.e., the columns of U) are determined up to a phase factor. This has no consequence on the performance of the quantum code. However, if we want to fix this residual indetermination, we proposed a fast and simple procedure in ref. [16]. The procedure requires an additional set of nPauli errors in which each additional Fiis a tensor product of Iand Xonly. As an example, for the Steane code, we use Table 2.

EiFi
XXXXXXXXIIIIII
ZIZZZZZIXIIIII
ZZIZZZZIIXIIII
ZZZIZZZIIIXIII
XIIIXIIIIIIXII
XIIIIXIIIIIIXI
XIIIIIXIIIIIIX

Table 2.

Additional Collection of Pauli errors.

After these remaining differences have been removed, we obtain an estimated matrix Uthat is equal to the true matrix, up to a global phase (Figure 5). However, this remaining indetermination does not matter because, as said before, the global phase has no significance in quantum physics. Here we have chosen the global phase so that the encoder matrix is real.

Figure 5.

Estimated MatrixUfor the Steane encoder.

Figure 5 shows the matrix computed by our method. We have checked that it is equal to the matrix directly computed from the circuit description.

The programmer may speed up the computation by taking into account the fact that when computing columns cof U, some matrices Ykhave already been computed for other columns and can be reused. For instance, in Figure 4, we see that the joint eigenvalues corresponding to columns 19 and 20 are the same, except the last one. Then, when computing column 20, we can set K20=nin Algorithm 1 instead of the default value K20=1, because the Yn1for column 20 is the same as for column 19. More generally, Algorithm 2 written in pseudo-Octave code computes the optimal values of the Kc.

K=11fork=2tondo|K=reshapeKkones12k112kend

Algorithm 2:Algorithm for computation of the optimal values Kc.

For instance, for n=3the algorithm produces K=13231323.

Advertisement

5. Application of JEVD to quantum walk search

5.1 Principle of quantum walk search

Let us consider a particle that can move on a graph. In the classical world, at the time tthis particle is localized at a node of the graph. It can then randomly choose one of the edges linked to this node to reach one of the adjacent nodes at a time t+1. The repeated iteration of this process is the concept of classical random walk.

A quantum walk [17] relies also on a graph, but contrary to the classical walk, here the particle may be located at many nodes at the same time and can choose many edges simultaneously. At the time t, the state of the particle is then described by a state vector ψtand the evolution between times tand t+1is given by a unitary matrix U=SCsuch that ψt+1=Uψt. The unitary matrices Cand Srepresent, respectively, the choice of the edges and the movement to the adjacent nodes.

In the following, we will consider graphs associated with hypercubes [18]. We will note nthe dimension of the hypercube and N=2nthe number of nodes. Figure 6 shows the graph corresponding to a hypercube of dimension n=3. It is convenient to label the nodes by binary words. In quantum language, these binary words κare also used to label the basis vectors of the so-called position space HS.

Figure 6.

Hypercube forn=3.

The quantum state lives in a Hilbert space built by the tensor product of the position space HS(corresponding to the nodes) and the coin space HC(corresponding to the possible movements along the edges) H=HSHC. The dimensions of these state spaces are Ne=nN, Nand n.

It is usual to define Cas [19]:

C=INGnE31

where Gnis the n×nGrover diffusion matrix defined in Section 2. Matrix Cobtained for n=3is shown on Figure 7.

Figure 7.

MatricesC(left) andO(right) forn=3.

The structure of Sis more complex. It is convenient to first define it in HCHSand then to transpose it to Husing the shuffle matrix P=Pn,N(defined in subsection 2.2). Then:

S=PŜPTE32

where

Ŝ=diagŜ1ŜnandŜd=IndXId1E33

The last equation just means that, because a movement along direction dcorresponds to an inversion of the dthbit in κ, the shift operator permutes the values associated to nodes that are adjacent along that dimension.

A quantum walk search can be described by repeated application of a unitary evolution operator Q, which can be written:

Q=UOE34

Here Ois the oracle, which aims at marking the solutions. An example of oracle structure is shown in Figure 7. It is a block-diagonal matrix, whose blocks are Gnwhen they correspond to a solution and Inotherwise. Denote Mthe number of solutions and assume that MN(otherwise the quantum walk search would serve no purpose because the probability of rapidly finding a solution with a classical search would be high). In the example shown in the figure, there are M=2solutions (located at positions 1 and 4 on Figure 6).

Let tdenote the number of iterations until a measurement is performed. Starting from an initial state ψ0, repeated iterations lead to the state ψt=Qtψ0which is then measured. The theory of quantum walk search [19] shows that the probability of success (that is the probability of obtaining a solution by measurement) oscillates as a function of t. This means that theoretical tools which help to understand and simulate quantum walk search lead to the development of methods to determine the optimal time of measurement.

In the sequel, we will show that JEVD is a fruitful tool in this context. Indeed, set Eto be the union of the joint eigenspaces of Uand O, and E¯its complement. Inside E, the operators commute. So, if we note with index Ethe restrictions of the operators to E, we have:

QE2=UEOEUEOE=UEOE2UE=UE2E35

Then, inside E, there is no significant difference between the effective quantum walk Qand the uniform quantum walk U, because, after each pair of successive iterations, the evolution is identical. Since the uniform quantum walk has no reason to converge to a solution, we deduce that the interesting part of the process lives in the complement of E, that is in E¯.

After establishing results about the dimensions of the eigenspaces of Uand O, we will show that the concept of joint eigenspaces allows us to establish an upper bound on the dimension of the complement, with the remarkable result that this dimension grows only linearly with n. Then, we propose an algorithm for efficient computation of the joint eigenspaces and, finally, use it to check our theoretical upper bound.

5.2 Eigenspaces of Uand O

Set

F=HNInE36

Then matrix Fdiagonalizes S:

FSF=HNInPN,nŜPn,NHNInE37
=Pn,NInHNŜInHNPN,nE38
=PTdiagHNŜdHNPE39

The latter term is diagonal because the mixed product property, H2=Iand HXH=Z, shows that:

HNŜdHN=IndZId1E40

Once more, using the mixed product property, we can also prove that Fkeeps Cunchanged, that is:

FCF=CE41

The diagonal of FSFis the concatenation of the binary representation of the numbers 0 to N1with the mapping 0+1and 11. That is:

FSF=diagS0SκSN1E42

Note that the diagonal of Sκcontains ktimes 1and nktimes +1(where kis the Hamming weight of κ).

Then, because F2=I, FUFis a block diagonal matrix:

FUF=FSFFCFE43
=diagSκCE44

Block κis then

Uκ=SκGnE45

We have:

dimEUκdimE+,Sκ,GnE46
dimE+Sκ+dimEGnnE47
nk+n1nE48
nk1E49

and

dimE+UκdimE,Sκ,GnE50
dimESκ+dimEGnnE51
k+n1nE52
k1E53

Then, there is only room left for at most 2 eigenvalues, specifically, at most a pair of conjugate ones.

Assume that this pair of eigenvalues exists. Since the diagonal of Gncontains 1+2n, the trace of Uκis:

traceUκ=nk+1+k11+2nE54
=n+2k+212knE55

The sum of the eigenvalues is equal to the trace and we already have eigenvalue 1with multiplicity nk1and eigenvalue +1with multiplicity k1. The sum of these n2eigenvalues is n+2k. Then the sum of the two missing eigenvalues must be 212kn. Let us denote them by λkand λk. We must have Reλk=12kn. Then, since λk=1we have

λk=12kn+i2nknkE56

Considering the eigenvalues of Gnand Init is trivial to show that the dimensions of the eigenspaces of the oracle are:

dimEO=ManddimE+O=NeME57

5.3 Upper bound on the dimension of the complement

The eigenvalues of Ubelong to 1+1λkλkwhere k1n1. Then, there are 2+2n1=2neigenspaces of U.

For j12nlet αjbe the dimensions of these eigenspaces and βjthe dimensions of their intersections with E+O. An eigenvector of Uis in an intersection if and only if it is orthogonal to EO. Then, because the dimension of EOis M, we have βjαjM. Consequently

j=12nβjj=12nαj2nME58

Obviously, we have j=12nαj=Ne, so that

j=12nβjNe2nME59

It follows that the dimension of the complement has an upper bound:

dimEc2nME60

This is a remarkable result—despite the fact that the dimension of the Hilbert space grows exponentially (Ne=n2n), the dimension of the complement grows only linearly with n.

5.4 Fast computation of the joint eigenspaces

5.4.1 Introduction

To check our theoretical upper bound, we propose an efficient algorithm for fast computation of the joint eigenspaces.

We have to compute orthonormal bases of joint eigenspaces of Uand O. The dimension of EOis small, hence, it makes sense to define it by an orthonormal basis generating the eigenspace. However, the dimension of E+Ois large (greater than Ne/2). Hence, it is computationally more efficient to define it by an orthonormal basis of its complement (which is EO). Indeed dimEOdimE+O. We then have to design an algorithm adapted to each case.

5.4.2 Intersection of two eigenspaces defined by orthonormal bases

Let us consider a matrix Awhose columns are an orthonormal basis of an eigenspace of U, and a matrix Bwhose columns are an orthonormal basis of EO. Set pand qto be the number of columns of these matrices (their number of rows being Ne). We want to compute an Ne×rmatrix Jwhose columns are an orthonormal basis of the joint eigenspace (whose dimension we have set to be r). We propose the algorithm below, which is a straightforward adaptation of Theorem 1 in ref. [20].

First, we compute the p×qmatrix Cbelow:

C=ABE61

Then, we compute the SVD of C:

C=UcScVcE62

Denote by skthe singular values (the diagonal elements of Sc) and determine rsuch that sk1εfor k=1,,r, and sk<1εfor k>r. Here ε1is a very small positive value introduced to take into account the presence of small errors due to computer finite precision arithmetic. Finally:

J=AUc:1:rE63

Or, equivalently, J=BVc:1:r.

5.4.3 Intersection of two eigenspaces, one of them being defined by an orthonormal basis of its complement

Let us consider a matrix Awhose columns are an orthonormal basis of an eigenspace of U, and a matrix Bwhose columns are an orthonormal basis of the complement of E+O(that is EO). First, we compute the p×qmatrix C(Eq. (61)). Then, we compute the p×rmatrix (rp) Zbelow:

Z=nullCE64

and we obtain an Ne×rmatrix Jwhose columns are an orthonormal basis of Eλ,+U,Ofrom:

J=AZE65

The justification of the algorithm is as follows. The qcolumns of Care a basis of the projection of ImBinto ImA, the components being expressed in the basis of ImAThe complement of ImCin ImAis the desired intersection (expressed in ImA). The columns of Zare an orthonormal basis of this intersection. Finally, Eq. (65) restores the components in the original space.

5.5 Simulation results

Consider a hypercube of dimension n=7with M=3solutions located at nodes 2,8,9. The dimension of the state space is then Ne=n2n=896. From the discussion above, we know that the dimension of the complement is upper bounded by 2nM=42.

The algorithm gives us the dimensions of the joint eigenspaces of Uand O(Table 3). The sum of the dimensions of the joint eigenspaces is then j=12nβj=858, from which we obtain the dimension of the complement:

λOλUdimEλO,λUO,U
1any λkor λk0
+1λ0=+1321
+1λ1or λ14
+1λ2or λ218
+1λ3or λ332
+1λ4or λ432
+1λ5or λ518
+1λ6or λ64
+1λ7=1321

Table 3.

Joint eigenspaces of Oand Ufor n=7and M=3solutions located at nodes 2,8,9.

dimEc=Nej=12nβj=38E66

We can see that, as expected, this dimension (dimEc=38) is much smaller than the dimension of the original state space (Ne=896). We can also check that it is less than the theoretical upper bound (2nM=42), as expected.

Advertisement

6. Conclusions

The recent growth of research on quantum communications and quantum information processing opens new challenges. In this chapter, we have shown that matrix theory concepts, such as JEVD, are powerful tools to propose new theoretical results as well as efficient simulation algorithms.

In the domain of quantum coding, we have shown how to determine the encoding matrix of a quantum code from a collection of Pauli errors. On a more speculative note to be part of future work concerning interception of quantum channels, it might also be useful to identify the quantum coder used by a noncooperative transmitter.

In the domain of quantum walk search, thanks to JEVD we have proved that there exists a small subspace of the whole Hilbert space which captures the essence of the search process, and we have given an algorithm that allows us to check this result by simulation.

Advertisement

Acknowledgments

The authors thank the IBNM (Institut Brestois du Numérique et des Mathématiques), CyberIoT Chair of Excellence, for its support.

Advertisement

Abbreviations

[qubit]Quantum bit
[JEVD]Joint EigenValue Decomposition
[SVD]Singular Value Decomposition

References

  1. 1.Humble TS. Quantum security for the physical layer. IEEE Communications Magazine. 2013;51(8):56-62
  2. 2.Liao SK et al. Satellite-to-ground quantum key distribution. Nature. 2017;549:43-47
  3. 3.Ren JG et al. Ground-to-satellite quantum teleportation. Nature. 2017;549:70-73
  4. 4.Valivarthi R et al. Quantum teleportation across a metropolitan fibre network. Nature Photonics. 2016;10:676-680
  5. 5.Yin J et al. Quantum teleportation and entanglement distribution over 100-kilometre freespace channels. Nature. 2012;488:185-188
  6. 6.Microsoft. The Q# programming language user guide [Internet] 2022 Available from:https://docs.microsoft.com/en-us/azure/quantum/user-guide/?view=qsharp-preview[Accessed: January 11, 2022]
  7. 7.Golub GH, Van Loan CF. Matrix Computations. 3rd ed. Baltimore and London: The John Hopkins University Press; 1996
  8. 8.Grover LK. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters. 1997;79(2):325
  9. 9.D’Angeli D, Donno A. Shuffling Matrices, Kronecker Product and Discrete Fourier Transform. Discrete Applied Mathematics. 2017;233:1-18
  10. 10.Raussendorf R. Key ideas in quantum error correction. Philosophical Transactions of the Royal Society A. 2012;370:4541-4565
  11. 11.Wootters W, Zurek W. A single quantum cannot be cloned. Nature. 1982;299(5886):802-803. DOI: 10.1038/299802a0
  12. 12.Nielsen MA, Chuang IL. Quantum Computation and Quantum Information. Cambridge, UK: Cambridge University Press; 2010
  13. 13.Steane A. Multiple-particle interference and quantum error correction. Proceeding of the Royal Society of London. 1996;452(1954):2551-2577. DOI: 10.1098/rspa.1996.0136
  14. 14.Shor PW. Scheme for reducing decoherence in quantum computer memory. Physical Review A. 1995;52(4):R2493-R2496. DOI: 10.1103/PhysRevA.52.R2493
  15. 15.Calderbank AR, Shor PW. Good quantum error-correcting codes exist. Physical Review A. 1996;54(2):1098-1105. DOI: 10.1103/physreva.54.1098
  16. 16.Burel G, Pillin H, Baghious EH, Baird P, Gautier R. Identification Of Quantum Encoder Matrix From A Collection Of Pauli Errors. Ho Chi Minh city, Vietnam: Asia-Pacific Conference on Communications; 2019
  17. 17.Kempe J. Quantum random walks – An introductory overview. Contemporary Physics. 2003;44(4):307-327. DOI: 10.1080/00107151031000110776
  18. 18.Moore C, Russell A. Quantum Walks on the Hypercube. Lecture Notes in Computer Science. Vol. 2483. New York: Springer. DOI: 10.1007/3-540-45726-7_14
  19. 19.Shenvi N, Kempe J, Whaley KB. Quantum random-walk search algorithm. Physical Review A. 2003;67:052307
  20. 20.Bjorck A, GolubG. Numerical methods for computing angles between linear subspaces. Mathematics of Computation. 1973;27:123. DOI: 10.2307/2005662

Written By

Gilles Burel, Hugo Pillin, Paul Baird, El-Houssaïn Baghious and Roland Gautier

Reviewed: January 27th, 2022Published: April 2nd, 2022