15. Proving Universality #
¿Qué puede hacer un ordenador? ¿Cuáles son los límites de lo que se considera computable, en general? Alan Turing se planteó estas preguntas antes de que supiéramos qué era un ordenador o cómo construirlo.
Para plantear esta pregunta a nuestros ordenadores clásicos, y en concreto a nuestros ordenadores digitales estándar, tenemos que despojarnos de todas las pantallas, altavoces y dispositivos de entrada extravagantes. Lo que nos queda es simplemente una máquina que convierte cadenas de bits de entrada en cadenas de bits de salida. Si un dispositivo puede realizar cualquier conversión, tomando cualquier conjunto arbitrario de entradas y convirtiéndolas en un conjunto arbitrario de salidas correspondientes, lo llamamos universal.
Del mismo modo, los ordenadores cuánticos toman estados de entrada y los convierten en estados de salida. Por tanto, podremos definir la universalidad de forma similar. Para ser más precisos, y poder demostrar cuándo se puede y cuándo no se puede alcanzar la universalidad, es útil utilizar la representación matricial de nuestras puertas cuánticas. Pero antes tendremos que repasar algunas técnicas.
15.1. Operaciones con matrices #
15.1.1. Matrices como outer products #
En secciones anteriores hemos calculado muchos productos internos, como \(\langle0|0\rangle =1\). Estos combinan un bra y un ket para darnos un solo número. También podemos combinarlos de forma que nos den una matriz, simplemente poniéndolos en el orden inverso. Esto se llama un producto externo, y funciona por multiplicación matricial estándar. Por ejemplo
Esto también significa que podemos escribir cualquier matriz puramente en términos de productos externos. En los ejemplos anteriores, construimos las cuatro matrices que cubren cada uno de los elementos individuales de una matriz de un solo qubit, por lo que podemos escribir cualquier otra matriz de un solo qubit en términos de ellas.
Esta propiedad también se extiende a las matrices para cualquier número de qubits, \(n\). Simplemente utilizamos los productos externos de las correspondientes cadenas de \(n\) bits.
15.1.2. Matrices Unitarias y Hermitianas. #
El conjugado hermitiano \(M^\dagger\) de una matriz \(M\) es la combinación de la transposición \ (sustituir el elemento inferior izquierdo por el superior derecho, y así sucesivamente) y el conjugado complejo de cada elemento. Dos familias de matrices muy importantes para la computación cuántica se definen por su relación con el conjugado hermitiano. Una es la familia de matrices unitarias, para las que
Esto significa que el conjugado hermitiano de un unitario es su inverso: otro unitario \(U^\dagger\) con el poder de deshacer los efectos de \(U\). Todas las puertas de la computación cuántica, a excepción de las operaciones de medida y reinicio, pueden representarse mediante matrices unitarias.
Otra consecuencia de la unitariedad es que preserva el producto interior entre dos estados arbitrarios. En concreto, tomemos dos estados \(\left| \psi_0 \right\rangle\) y \(\left| \psi_1 \right\rangle\). El producto interior de estos es \(\left\langle \psi_0 | \psi_1 \right\rangle\). Si aplicamos el mismo unitario \(U\) a ambos, el producto interior de los estados resultantes es exactamente el mismo,
Esta propiedad nos proporciona una forma útil de pensar acerca de estas puertas. Significa que para cualquier conjunto de estados \(\{ \left| \psi_j \right\rangle \}\) que proporcionan una base ortonormal para nuestro sistema, el conjunto de estados \(\{ \left| \phi_j \right\rangle = U \left| \psi_j \right\rangle \}\) también será una base ortonormal. El unitario puede considerarse entonces como una rotación entre estas bases, y puede escribirse en consecuencia como
Se trata esencialmente de la versión cuántica de las “tablas de verdad” que describen la acción de las puertas booleanas clásicas.
La otra familia importante de matrices son las matrices hermitianas. Son aquellas a las que no afecta el conjugado hermitiano
Las matrices \(X\), \(Y\), \(Z\) y \(H\) son ejemplos de matrices hermitianas que ya has visto \ (casualmente, también son todas unitarias ya que son sus propias inversas).
Todas las matrices unitarias y las matrices hermitianas tienen la propiedad de ser diagonalizables. Esto significa que pueden escribirse de la forma
donde \(\lambda_j\) son los valores propios de la matriz y \(|h_j\rangle\) son los estados propios correspondientes.
Para los unitarios, aplicar la condición \(U U^\dagger=I\) en esta forma diagonal implica que \(\lambda_j \lambda_j^* = 1\). Por tanto, los valores propios son siempre números complejos de magnitud 1, por lo que pueden expresarse \(e^{ih_j}\) para algún valor real \(h_j\). Para matrices hermitianas la condición \(H = H^\dagger\) implica \(\lambda_j = \lambda_j^*\), y por tanto que todos los valores propios son reales.
Por tanto, estos dos tipos de matrices sólo se diferencian en que una debe tener números reales para los valores propios y la otra debe tener exponenciales complejos de números reales. Esto significa que, para cada unitario, podemos definir una matriz hermitiana correspondiente. Para ello simplemente reutilizamos los mismos eigenvalores, y utilizamos el \(h_j\) de cada \(e^{ih_j}\) como el eigenvalor correspondiente.
Del mismo modo, para cada matriz hermitiana existe un unitario. Simplemente reutilizamos los mismos estados propios, y exponenciamos los \(h_j\) para crear los valores propios \(e^{ih_j}\). Esto se puede expresar como
Aquí hemos utilizado la definición estándar de cómo exponenciar una matriz, que tiene exactamente las propiedades que requerimos: preservar los estados propios y exponenciar los valores propios.
15.1.3. 2.3 Pauli decomposition #
As we saw above, it is possible to write matrices entirely in terms of outer products.
Now we will see that it is also possible to write them completely in terms of Pauli operators. For this, the key thing to note is that
This shows that \(|0\rangle\langle0|\) and \(|1\rangle\langle1|\) can be expressed using the identity matrix and \(Z\). Now, using the property that \(X|0\rangle = |1\rangle\), we can also produce
Since we have all the outer products, we can now use this to write the matrix in terms of Pauli matrices:
This example was for a general single-qubit matrix, but the corresponding result is true also for matrices for any number of qubits. We simply start from the observation that
and can then proceed in the same manner as above. In the end it can be shown that any matrix can be expressed in terms of tensor products of Pauli matrices:
For Hermitian matrices, note that the coefficients \(C_{P_{n-1}\ldots,P_0}\) here will all be real.
15.2. 3. Defining Universality #
Just as each quantum gate can be represented by a unitary, so too can we describe an entire quantum computation by a (very large) unitary operation. The effect of this is to rotate the input state to the output state.
One possible special case of this is that the input and output states describe bit strings expressed in quantum form. The mapping of each input \(x\) to its output \(f(x)\) could be described by some (reversible) classical computation. Any such computation could therefore be expressed as a unitary.
If we were able to implement any possible unitary, it would therefore mean we could achieve universality in the sense of standard digital computers.
Another special case is that the input and output states could describe a physical system, and the computation we perform is to simulate the dynamics of that system. This is an important problem that is impractical for classical computers, but is a natural application of quantum computers. The time evolution of the system in this case corresponds to the unitary that we apply, and the associated Hermitian matrix is the Hamiltonian of the system. Achieving any unitary would therefore correspond to simulating any time evolution, and engineering the effects of any Hamiltonian.
Combining these insights we can define what it means for quantum computers to be universal. It is simply the ability to achieve any desired unitary on any arbitrary number of qubits. If we have this, we know that we can reproduce anything a digital computer can do, simulate any quantum system, and do everything else that is possible for a quantum computer.
15.3. 4. Basic Gate Sets #
Whether or not we can build any unitary from a set of basic gates depends greatly on what basic gates we have access to. For every possible realization of fault-tolerant quantum computing, there is a set of quantum operations that are most straightforward to realize. Often these consist of single- and two-qubit gates, most of which correspond to the set of so-called Clifford gates. This is a very important set of operations, which do a lot of the heavy-lifting in any quantum algorithm.
15.3.1. 4.1 Clifford Gates #
To understand Clifford gates, let’s start with an example that you have already seen many times: the Hadamard.
This gate is expressed above using outer products, as described above. When expressed in this form, its famous effect becomes obvious: it takes \(|0\rangle\), and rotates it to \(|+\rangle\). More generally, we can say it rotates the basis states of the z measurement, \(\{ |0\rangle,|1\rangle \}\), to the basis states of the x measurement, \(\{ |+\rangle,|-\rangle \}\), and vice versa.
In this way, the effect of the Hadamard is to move information around a qubit. It swaps any information that would previously be accessed by an x measurement with that accessed by a z measurement.
The Hadamard can be combined with other gates to perform different operations, for example:
By doing a Hadamard before and after an \(X\), we cause the action it previously applied to the z basis states to be transferred to the x basis states instead. The combined effect is then identical to that of a \(Z\). Similarly, we can create an \(X\) from Hadamards and a \(Z\).
Similar behavior can be seen for the \(S\) gate and its Hermitian conjugate,
This has a similar effect to the Hadamard, except that it swaps \(X\) and \(Y\) instead of \(X\) and \(Z\). In combination with the Hadamard, we could then make a composite gate that shifts information between y and z.
This property of transforming Paulis into other Paulis is the defining feature of Clifford gates. Stated explicitly for the single-qubit case: if \(U\) is a Clifford and \(P\) is a Pauli, \(U P U^{\dagger}\) will also be a Pauli. For Hermitian gates, like the Hadamard, we can simply use \(U P U\).
Further examples of single-qubit Clifford gates are the Paulis themselves. These do not transform the Pauli they act on. Instead, they simply assign a phase of \(-1\) to the two that they anticommute with. For example,
You may have noticed that a similar phase also arose in the effect of the \(S\) gate. By combining this with a Pauli, we could make a composite gate that would cancel this phase, and swap \(X\) and \(Y\) in a way more similar to the Hadamard’s swap of \(X\) and \(Z\).
For multiple-qubit Clifford gates, the defining property is that they transform tensor products of Paulis to other tensor products of Paulis. For example, the most prominent two-qubit Clifford gate is the CNOT. The property of this that we will make use of in this chapter is
This effectively ‘copies’ an \(X\) from the control qubit over to the target.
The process of sandwiching a matrix between a unitary and its Hermitian conjugate is known as conjugation by that unitary. This process transforms the eigenstates of the matrix, but leaves the eigenvalues unchanged. The reason why conjugation by Cliffords can transform between Paulis is because all Paulis share the same set of eigenvalues.
15.3.2. 4.2 Non-Clifford Gates #
The Clifford gates are very important, but they are not powerful on their own. In order to do any quantum computation, we need gates that are not Cliffords. Three important examples are arbitrary rotations around the three axes of the qubit, \(R_x(\theta)\), \(R_y(\theta)\) and \(R_z(\theta)\).
Let’s focus on \(R_x(\theta)\). As we saw above, any unitary can be expressed in an exponential form using a Hermitian matrix. For this gate, we find
The last section also showed us that the unitary and its corresponding Hermitian matrix have the same eigenstates. In this section, we’ve seen that conjugation by a unitary transforms eigenstates and leaves eigenvalues unchanged. With this in mind, it can be shown that
By conjugating this rotation by a Clifford, we can therefore transform it to the same rotation around another axis. So even if we didn’t have a direct way to perform \(R_y(\theta)\) and \(R_z(\theta)\), we could do it with \(R_x(\theta)\) combined with Clifford gates. This technique of boosting the power of non-Clifford gates by combining them with Clifford gates is one that we make great use of in quantum computing.
15.3.3. 4.3 Expanding the Gate Set #
As another example of combining \(R_x(\theta)\) with Cliffords, let’s conjugate it with a CNOT.
This transforms our simple, single-qubit rotation into a much more powerful two-qubit gate. This is not just equivalent to performing the same rotation independently on both qubits. Instead, it is a gate capable of generating and manipulating entangled states.
We needn’t stop there. We can use the same trick to extend the operation to any number of qubits. All that’s needed is more conjugates by the CNOT to keep copying the \(X\) over to new qubits.
Furthermore, we can use single-qubit Cliffords to transform the Pauli on different qubits. For example, in our two-qubit example we could conjugate by \(S\) on the qubit on the right to turn the \(X\) there into a \(Y\):
With these techniques, we can make complex entangling operations that act on any arbitrary number of qubits, of the form
This all goes to show that combining the single and two-qubit Clifford gates with rotations around the x axis gives us a powerful set of possibilities. What’s left to demonstrate is that we can use them to do anything.
15.4. 5. Proving Universality #
As for classical computers, we will need to split this big job up into manageable chunks. We’ll need to find a basic set of gates that will allow us to achieve this. As we’ll see, the single- and two-qubit gates of the last section are sufficient for the task.
Suppose we wish to implement the unitary
but the only gates we have are \(R_x(\theta) = e^{i \frac{\theta}{2} X}\) and \(R_z(\theta) = e^{i \frac{\theta}{2} Z}\). The best way to solve this problem would be to use Euler angles. But let’s instead consider a different method.
The Hermitian matrix in the exponential for \(U\) is simply the sum of those for the \(R_x(\theta)\) and \(R_z(\theta)\) rotations. This suggests a naive approach to solving our problem: we could apply \(R_z(2b) = e^{i bZ}\) followed by \(R_x(2a) = e^{i a X}\). Unfortunately, because we are exponentiating matrices that do not commute, this approach will not work.
However, we could use the following modified version:
Here we split \(U\) up into \(n\) small slices. For each slice, it is a good approximation to say that
The error in this approximation scales as \(1/n^2\). When we combine the \(n\) slices, we get an approximation of our target unitary whose error scales as \(1/n\). So by simply increasing the number of slices, we can get as close to \(U\) as we need. Other methods of creating the sequence are also possible to get even more accurate versions of our target unitary.
The power of this method is that it can be used in complex cases than just a single qubit. For example, consider the unitary
We know how to create the unitary \(e^{i\frac{\theta}{2} X\otimes X\otimes X}\) from a single qubit \(R_x(\theta)\) and two controlled-NOTs.
qc.cx(0,2)
qc.cx(0,1)
qc.rx(theta,0)
qc.cx(0,1)
qc.cx(0,2)
With a few Hadamards, we can do the same for \(e^{i\frac{\theta}{2} Z\otimes Z\otimes Z}\).
qc.h(0)
qc.h(1)
qc.h(2)
qc.cx(0,2)
qc.cx(0,1)
qc.rx(theta,0)
qc.cx(0,1)
qc.cx(0,2)
qc.h(2)
qc.h(1)
qc.h(0)
This gives us the ability to reproduce a small slice of our new, three-qubit \(U\):
As before, we can then combine the slices together to get an arbitrarily accurate approximation of \(U\).
This method continues to work as we increase the number of qubits, and also the number of terms that need simulating. Care must be taken to ensure that the approximation remains accurate, but this can be done in ways that require reasonable resources. Adding extra terms to simulate, or increasing the desired accuracy, only require the complexity of the method to increase polynomially.
Methods of this form can reproduce any unitary \(U = e^{iH}\) for which \(H\) can be expressed as a sum of tensor products of Paulis. Since we have shown previously that all matrices can be expressed in this way, this is sufficient to show that we can reproduce all unitaries. Though other methods may be better in practice, the main concept to take away from this chapter is that there is certainly a way to reproduce all multi-qubit unitaries using only the basic operations found in Qiskit. Quantum universality can be achieved!
This gate set is not the only one that can achieve universality. For example it can be shown that just the Hadamard and Toffoli are sufficient for universality. Multiple other gates sets have also been considered and been proven universal, each motivated by different routes toward achieving the gates fault-tolerantly.
Everything we have discussed in this book follows the circuit model of computation. However, the circuit model is not the only universal model of quantum computation. Other forms of quantum computation such as adiabatic quantum computing or measurement based quantum computing exist. The fact that they are universal means that it has been proven that there is a mapping in polynomial time and resources from the circuit model to these other models of computation. These other models often leverage other quantum mechanical properties in order to perform their computation. While these other forms of quantum computation exist, it is important to note that the benefits of each concern only physical and hardware problems. Since a universal model of quantum computation can perform any quantum algorithm, we need only stick with the circuit model and can ignore other universal models for our discussion.
There are other forms of quantum computation that are not universal, but are applicable to specific applications. For example quantum annealing may be useful for optimization and sampling problems. Annealing is the process of heating a metal to a high temperature and then allowing it to cool down slowly. This process causes molten metal to flow over the surface of the metal piece and redistribute itself; changing many properties of the metal in question. Quantum annealing is analogous to the physical process of annealing in some sense. It involves encoding problems into an energy landscape of sorts and then letting a quantum state explore the landscape. While normal waves may get trapped in troughs which are lower than their surroundings (local minima), quantum effects increase the speed at which the quantum states find the true lowest point on the landscape (global minima).
import qiskit.tools.jupyter
%qiskit_version_table
Version Information
| Software | Version |
|---|---|
qiskit | 0.44.2 |
qiskit-terra | 0.25.2 |
| System information | |
| Python version | 3.11.4 |
| Python compiler | MSC v.1916 64 bit (AMD64) |
| Python build | main, Jul 5 2023 13:38:37 |
| OS | Windows |
| CPUs | 4 |
| Memory (Gb) | 11.799663543701172 |
| Tue Oct 24 10:15:52 2023 Hora de verano romance | |