In the last article we looked at the quantum Fourier transform (QFT) and how its inverse was used in conjunction with measurement of the output register of entangled qubits to produce the eigenvalues of the applied unitary matrix with probability equal to
In the last article we looked at the quantum Fourier transform (QFT) and how its inverse was used in conjunction with measurement of the output register of entangled qubits to produce the eigenvalues of the applied unitary matrix with probability equal to the absolute value of the amplitude squared. Only a polynomial number of trials was needed to obtain any eigenvalue for which its amplitude was not exponentially small. If the initial guess was close to the desired state then even less trials were needed!
Moreover, once a measurement is made and an eigenvalue determined, the remaining qubits will inevitably collapse in to the state of the corresponding eigenvector. We will see below the intimate relationship with observing an eigenvalue and its corresponding eigenvector. Interestingly, for qubit registers greater than about 40 in size, the state of the corresponding eigenvector already exceeds the entire storage capacity of Google’s Cloud Cluster,.
What wasn’t really answered was: how does it know what the correct result is?
The short answer is because Abrams & Lloyd figured it out in 1998.
The longer answer is to first consider a much simpler problem:
The Much Simpler Problem to Consider
Let be a square matrix with the property that
where is the identity matrix and is the conjugate transpose of.
When a square matrix has this property then it is called a unitary matrix. A unitary matrix is always a very nice matrix to have. They have several nice properties, several equivalence conditions making them extremely useful for other science applications, plus they are simple enough to be able to model Nature.
So suppose we are given a unitary matrix and we also have a vector. What we would like to do is to find a number such that
In other words, the matrix multiplication of with the vector (which we know, because we have both of them) is exactly the same as the scalar multiplication of the same vector with this magical number. If we could find such a number then, since scalar multiplication of a vector and a number essentially just stretches or shrinks the vector, we can say that the unitary matrix only stretches or shrinks the vector – crucially: it does not rotate it!
This problem is known as the eigenvalue problem and it is a relatively simple problem with a relatively powerful solution. Because that single number has a lot of meaning, if you can find it (not all matrices have eigenvalues).
The way that the eigenvalue problem is posed makes it sound like rotation is bad. Why on Earth would you want to find something that only stretches or shrinks? Firstly, geometrically speaking, stretching and shrinking is equivalent to proportionality – and a lot of powerful physical statements are made on the proviso of proportionality being met (we will meet the proportionality statement that Schrodinger made with his famous equation below).
Also, think of the way you would go about writing down that unitary matrix. Such a matrix is just one way of writing down the components of a linear map in a particular basis (and don’t forget that quantum mechanics and computing is very basis-oriented!). So that matrix will change when you change the basis: a different basis means writing the basis coefficients differently. The eigenvalues do not change – they are invariant under a change of basis!
Eigenvalues do not change under a change of basis.
As a bit of an analogy: it is well-known that every integer can be written as a product of prime numbers – this is known as the fundamental theorem of arithmetic. It is also true that every square matrix can be written as a product of three square matrices,, and as:
where is the square matrix whose column is the eigenvector of, and is the diagonal matrix whose diagonal entries are the corresponding eigenvalues. This is known as the eigendecomposition of a matrix, and only diagonalisable matrices always have this property. Luckily for us, every unitary matrix is diagonalisable, and so, for us, the eigenvalues and eigenvectors are extremely important tool for manipulating our unitary matrix.
Unitary matrices have this powerful property that they are always diagonalisable and hence w