You are most welcome to read another article about quantum computing.
Quantum circuit design is the analysis methodology, and a synthesis of quantum circuits that implement some or other algorithms (not only quantum ones). In a generalized sense, any computational process is represented in the form of a three (the input, the process of transformation, the output). Taking into account this consideration, the goals of quantum circuit design are:
-
Forward analysis. Determine the output state, provided that there is an input state and the definition of a computational process.
- Backward analysis. Determine the input state, provided that there is an output state and the definition of a computational process.
- Synthesis. Build the definition of a computational process, provided that there are input and output states.
Unfortunately, these questions are not really reflected in the literature about quantum computations. But they are extremely important. That's why I am going to disclose all the three aspects of quantum circuit design.
Forward Analysis
From a mathematical standpoint, we can solve this task quite easily. An input circuit is a definition of a set of possible values that can be input to the process of quantum computations. Since a quantum register, i.e. a set of qubits, can be represented in the form of a vector, forward analysis comes to consequent multiplication of matrices by the vector. We can also multiply all matrices in the correct order, and then multiply the resulting matrix by the input vector.
Having executed this procedure at all possible input values (or after applying other analysis techniques), we can get all output values, and then merge them into a circuit. This type of analysis is complicated by the fact that when the number of qubits rises, dimensions of vectors and matrices increase exponentially. Even if we can run this procedure for quantum registers consisting of 1-3 qubits, it will be quite complicated to make a manual analysis for 4 qubits. For 10 qubits and more, it’s even hard to run matrix multiplications on a computer.
Backward Analysis
Within the limits of the model of quantum computations, the task of backward analysis trivially comes to the forward analysis. Since calculations are reversible, and matrices of all gates are unitary, to execute the backward analysis of the given quantum circuit, it’s enough to reverse it, i.e. rewire gates in reverse order by making an input become an output and vice versa, and transform the gates themselves into Hermitian adjoint ones. After that, the previously described forward analysis procedure is performed.
It goes without saying, that all the mentioned above is applicable only to quantum circuits having no measurement operation, that is irreversible. On the other hand, we usually apply measurement at the end of quantum computations, when it is necessary to get a classical result. Therefore, we can convert the circuit by rejecting the operation of measurement. There are few quantum algorithms with measurement being executed at the middle of the computational process (for example, quantum teleportation). The backward analysis method is not applicable to such algorithms and their quantum circuits. Thus, we would have to use other methods. (if they exist at all — in general, the inverse problem is unsolvable).
Synthesis
The problem of constructing quantum circuits on a given input and output increases in contrast to the classical case, and the necessity to ensure the reversibility of computation. In the general case, we can describe an arbitrary computational process as a binary function that accepts n bits on the input and returns m bits. In the classical variant, we can build such function with the help of a basis (universal) set of logical elements.
The availability of the classical circuit from the universal set of building blocks for the given function transfers the synthesis task into the task of building a quantum oracle. We can build a quantum oracle from a classical expression of the function the following way:
- The quantum oracle will have (n + m) inputs and outputs. The first n inputs accept the input parameters of a function. The next m inputs are initialized in |0>. Thus, the first n outputs will return the input data. The next m outputs will get the addition modulo 2 (Exclusive OR operation) function values at the given input with m input data.
- All classical circuit elements are converted into appropriate quantum gates (for instance, we can utilize either a universal set from H and CNOT gates, or the quantum analogy of Toffoli gate). This can lead to a great number of the so-called garbage qubits.
- The built circuit of universal quantum elements is affected by the process of optimization. It’s quite a nontrivial process. We should apply different methods and techniques for each case. The goal of this process is to minimize the number of garbage qubits, or even exclude them at all.
- If we failed to get rid of the garbage qubits (let there be l of them), we will add all of them to the input and output ones (thus, there will be (n + m + l) inputs and outputs). But first, we should initialize these qubits in |0>. After the computations, we have to set them in |0> as well. It’s the consequence of the laws of quantum mechanics.
Hence, we will build a quantum circuit of a classical function. However, this is not the only way to do it. Another option is to build a unitary matrix to represent the complete classical function. This task could be successfully solved by solving the system of equations, acquired from the product of a matrix by a vector. The only problem is that the number of equations and unknowns grows exponentially with the number of qubits. If the number of inputs and outputs is (n + m), the number of equations and unknowns will be 22(n + m). It’s quite simple to solve such system for small numbers, but way much more complicated to do the same for big numbers.
As an example, we can take a look at the process of building a quantum analogy of the classical logic AND operation. The function implementing this operation has 2 inputs and 1 output. Hence, the quantum oracle will have 3 inputs and outputs. The following table shows 8 possible behavior variants of the quantum oracle.
| X1 | X2 | Y | X1 & X2 | (X1 & X2) ⊕ Y |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
Thus, the simultaneous equations to solve look like this:
Its solution is quite trivial. The following matrix will be the result of it:
This matrix is the quantum oracle in the matrix representation. Now, let’s make sure that it is unitary. Multiply it by the Hermitean adjoint one. Since this matrix is self-conjugated, we will just square it. It’s quite obvious that an identity matrix will be the result of it. Thus, the found matrix is unitary.
Short explanations. The identity matrix in the original equation is obtained from the above table of eight rows, where the 1st, 2nd and 3rd columns are picked out. Each of these eight rows converts into a column-vector (to save time, row-vectors are shown here, but we should keep in mind that they are column-vectors). «0 0 0» row represents vector (1 0 0 0 0 0 0 0), and «0 0 1» row represents vector (0 1 0 0 0 0 0 0), and so on up to «1 1 1» row, which is vector (0 0 0 0 0 0 0 1). The resulting matrix is constructed on the same principle, but now we will use rows with 1st, 2nd and 5th columns. As you can see, 5th column differs from the 3rd one in the 7th and 8th rows only, which will result in the change of the 7th and the 8th columns in the resulting matrix.
In other words, to obtain a resulting matrix of the quantum oracle, it’s enough to order column-vectors in the way described above. It takes 2n rows for n input qubits. Each row has (n + 1) columns. The first n columns accept all possible values of input qubits. The last column accepts y ⊕f(x) value. Column vector in the computational basis is associated for each row, and then all the columns are combined into a matrix.
The task is solved. A good exercise for the interested reader would be building the same matrices for other fifteen binary functions from two variables.
Summary
We should understand that the synthesis of quantum circuit is not building of a quantum algorithm. The provided technique allows solving a random computational task on a quantum computer. As for the quantum algorithm development, this task is so nontrivial and unusual, that inspiration will help you more, than scrupulous step-by-step building. Up to the present day, all the developed quantum algorithms are based on several basis ones that have been invented thanks to inspiration.
You are most welcome to read my previous articles: