Naixu Guo¹, Kosuke Mitarai^1,2,3, and Keisuke Fujii^1,2,4

1. Graduate School of Engineering Science, Osaka University

2. Center for Quantum Information and Quantum Biology, Institute for Open and Transdisciplinary Research Initiatives, Osaka University

3. JST PRESTO, Japan

4. Center for Emergent Matter Science, RIKEN, Wako Saitama 351-0198, Japan

Abstract

Due to the linearity of quantum operation, it is not straightforward to implement the nonlinear transformation on a quantum computer, making some practical tasks like a neural network hard to be achieved. In this work, we define a task called the \textit{nonlinear transformation of complex amplitudes} and provide an algorithm based on quantum singular value transformation. We also provide a thorough discussion about how to implement practical tasks such as a neural network using complex amplitudes with this procedure.

Presentation video

Slides

Hello everyone, my name is naixu guo, now a master student at osaka university. today i am going to introduce my joint work with kokuke mitarai and keisuke fujii. The title of our work is Nonlinear transformation of complex amplitudes via quantum singular value transformation. This video is for the 20th AQIS.

The outline of this talk is shown in this page. First, i am going to give a background introduction, about the fundamental linearity of quantum mechanics, and what is the neural network. Then, I will introduce the main ideas of our work. After introducing a previous technique called quantum singular value transformation, I will describe the construction of our methods. Finally, I will show how our methods can be used for the quantum neural network task.

For people who are familiar with quantum mechanics, it is common knowledge that the quantum operation is linear map defined on hilbert spaces. What may happen if someone allows some nonlinear operations? It has been shown that with these operations, quantum computers can solve NP-complete problems in polynomial time. Since Np-complete problems are really hard, we do not believe that nature can have such big power, and this implies the fundamental linearity of quantum mechanics. The only achievable nonlinearity is measurement and projection, and it is highly nontrivial to perform the nonlinearity with these two actions. As a fundamental interest, we wonder how much can we implement the nonlinearity with quantum computers. For example, can we perform a nonlinear function on the amplitudes of quantum states? At last we find the answer is yes, if we confine the functions to satisfy some conditions.

To formalize our consideration, first we want to introduce a problem, which we call the Nonlinear transformation of complex amplitudes. The problem is defined like this

Assume we are given an oracle which can prepare a quantum state, and nonlinear functions P and Q.

Aim is to construct a quantum circuit which finally outputs a state that is an epsilon approximation of the state, whose real and imaginary part of previous amplitudes are performed with functions P and Q separately.

Here, I want to explain the reason why we divide the amplitudes into real and imaginary parts. To perform the function on the amplitudes, first we have to extract the amplitudes information to something easier to deal with. The straight strategy is to encode these into the eigenvalues of quantum gates. As quantum gates are unitaries, we cannot encode the complex numbers, and we need to achieve this task part and part. Also, here we also consider the functions P and Q as complex functions, and this problem can be more general if we define it in this way.

We find that this problem is not only fundamental interested, it also has practical applications, such as to perform the neural network task on the quantum computer.

The neural network is the most widely used method in machine learning field. This method uses a mathematical model for information processing based on a connection approach to computation, and the image is shown here. Here each node denotes two arithmetics: linear transformation and nonlinear transformation. It has been shown that every continuous function that maps intervals of real numbers to some output interval of real numbers can be approximated arbitrarily closely by a multi-layer perceptron with just one hidden layer. This theorem promises the effectiveness of neural networks.

Here, I want to explain the computing process of neural network in details. For example, consider the l -th layer of neural network. Its computing processing can be written in this matrix form.

The matrix W in the equation is the weight matrix, which aim is to redistribute the sample data. P denotes the nonlinear function, and mostly people use tanh and relu function to implement the nonlinearity.

Neural network can be used for the task like regression or classification, which has many applications to modern society. From the quantum computing aspect, it is also very interesting to consider how to perform this method in quantum.

To implement the neural network on the quantum computer, there are some previous works and here we list them together.

Because of the linearity of QM, all the works consider performing the linear transformation with quantum, where it can provide a speedup compared with the classical case.

However, each work considers the different methods to perform the nonlinearity.

The first paper uses the circuit, called repeat until success, which is composed of many controlled rotations.

It is easy to implement, but they confine the data as binary.

The second work performs the nonlinear transformation with classical computation. After the linear transformation, they read out the data from quantum and implement the nonlinearity. After that, they encode the data back to the quantum. The problem is that read in/read out may cost much in practice.

The third work uses phase estimation and quantum arithmetics to perform the nonlinearity. It is suitable for any function, yet they need many ancilla qubits.

Our work is actually based on the hint from the third one and a previous work called qsvt or qubitization.

We can use less ancilla qubits and oracle complexity has better dependence on error. The problem is that this method is not suitable for all functions.

After introducing the background of our work, now I am going to describe the main ideas. It is divided into two parts: First, I will explain the idea of previous work qsvt and then show how we can use this subroutine to achieve the nonlinear transformation of complex amplitudes task.

Here, I want to introduce the definition of block encoding.

A unitary U is a block encoding of a matrix A if A is kind of encoded into this unitary, like the matrix form on the right side.

Let us consider the singular value decomposition of the matrix A. They have shown in the paper that for some d-degree nonlinear functions P which satisfy the conditions of quantum signal processing, one can construct a circuit that can perform function P on the singular values of matrix A. The circuit is described in the following.

Here one can see that the circuit uses U and U dagger repeatedly. The reason to perform the circuit in this way is to keep operations acting in the desired subspaces. Between these two gates, there are also controlled-gates and phase rotation adding on the ancilla qubit, here phases are chosen to perform the desired function P.

Our idea is to perform the nonlinear transformation on the amplitudes by qsvt, so our aim is to construct a unitary that is a block encoding of the matrix, part of whose singular values are the real or imaginary part of the previous amplitudes. For simplicity, we will consider the real part in the following.

In the next page I will introduce the exact construction. However, it is very complex and I want to summarize the conclusion first. After constructing the desired unitary, we will use it to perform qsvt and amplitude amplification, here amplitude amplification is to make the algorithm deterministic. To achieve the task of nonlinear transformation of complex amplitudes, the oracle complexity is in this value.

First, it depends on the degree of nonlinear function P. Also, it depends on the dimension of the states and amplitudes after transformation. These two values play a key role when we consider the quantum neural network task. In the worst case, the computation speed is not better than the classical case. Finally, one should notice that our dependence on error is polylog, which is exponentially better than the previous works.

Now I will introduce the construction of our methods. This is the circuit of qsvt, where the tilde G is constructed with the following.

The construction is kind of complex, and I am not going to explain details here. The bottom circuit is used for state shifting, where U is the state preparation oracle. This circuit can shift the previous state prepared by the oracle to some states easier to be handled. The middle figure shows the construction of a unitary G.

Assume we have the access to the controlled version of G and G dagger, then combined with two hadmard gates, tilde G can be constructed. It is easy to see that tilde G is a block encoding of one half G plus G dagger.

Here is the most important part and I want to stress the properties of one half G plus G dagger. First, it is a hermitian matrix. Second, if someone considers the singular value decomposition of this matrix, one can find that the previous amplitudes are exactly the singular values of this matrix, corresponding to some the states which can be prepared by the bottom circuit.

As a summary, based on this complex circuit design, we can use qsvt to achieve the nonlinear transformation of complex amplitudes task.

Finnaly, I am going to introduce how to use this method to implement the neural network task.

Here I am going to introduce how to use our methods to the 1-layer and multi-layer neural network task. First, we need to consider how to perform the state preparation oracle. Based on the previous work, we know that the oracle can be efficiently achieved with a quantum data structure called QRAM. Linear transformation is considered to be implemented with parameterized unitary, and nonlinear transformation is achieved with our construction. One should notice that the linear unitary and state preparation oracle can be considered as one operation and it will be the oracle in our construction, shown in the previous part. The mostly used nonlinear functions in the neural network, tanh and relu, can also be well approximated with our method. After the computing process, we consider the optimization is achieved classically.

For practical uses, It is very important to consider how to implement the multi-layer neural network task. We find that in our construction, the circuit for the second layer is almost the same except for the oracle gate. Since previous construction can be considered as the oracle for the next layer, by denoting the previous construction as the new oracle, task of multi-layer neural network is also achievable.

Based on these considerations, we find that if the data is nearly uniform, 1-layer neural network can be computed in time square root N, where N is the data vector dimension. This is a polynomial speedup compared with the classical cases. Also, the quadratic speedup can maintain for the two layer neural network. However, for deep layer neural network, our circuit will become very complex and finally inefficient, since we repeatedly use the previous layer construction as the new oracle. So the disadvantage is that it is not suitable for deep neural network tasks and stays as an open problem.

This is the summary of our talk today. First we define the problem called the nonlinear transformation of complex amplitudes to explore the implementable nonlinearity of quantum computers. Then we provide a concrete algorithm to solve the problem based on quantum singular value transformation. Because of using this technique, we confine the nonlinear functions to satisfy the conditions of quantum signal processing. It is an open problem to consider how to generalize this condition or can this condition be generalized. Finally we show how to use our method to achieve the quantum neural network task and compare it with the previous works.

Thank you for your listening!