PublicationsJij Inc.
PublicationsJij Inc.

Quantum Fourier Transformation by Tensor Network

 
In this article, we follow the outline of the paper [1] that shows the quantum Fourier transform gives small entanglement and performs the quantum Fourier transform calculation on a tensor network simulator.
This article is organized as follows:
  1. An overview of the paper [1] that shows that entanglement can be suppressed to a small degree in the quantum Fourier transform
  1. Experiments with the Tensor Network Simulator
 

Quantum Fourier Transform

In algorithms using quantum computers, Grover's search algorithm and the quantum Fourier transform are the two most commonly used subroutine algorithms. In particular, the quantum Fourier transform is well-known because it is used for phase estimation, which is used in Shor's algorithm [2,3] to perform prime factorization.
 
The quantum Fourier transform is the algorithm to convert the quantum state as follows:
where
Here, and are written by omitting the quantum state corresponding to the binary representation of integers. For example, in the case of 4qubits ((), 、, = .
In particular, the inverse transformation of quantum Fourier transform
shows that the information corresponding to the phase that exists in , the coefficients of the wave function, can be transferred to the qubit which is often used to read the phase information generated during a quantum calculation through observation.
 
To create a quantum circuit that performs a quantum Fourier transform, We can see that we can create a quantum circuit that performs operations such as
The quantum circuit that achieves this, for example, with 4 qubits, would be the following, using a Hadamard gate and a control phase gate. [4]
 
If we rewrite in binary notation () and follow the quantum state change for each quantum gate, we obtain
where denotes binary decimals.
Extending this to the general case of qubits, the final result is
and rearranging the last qubit in reverse order using the SWAP gate creates the same circuit as the quantum Fourier transform.
 

Operator Schmidt Decomposition of a quantum circuit

When dealing with quantum circuits, the distribution of quantities obtained using the Operator Schmidt Decomposition is an indicator of whether or not calculations can be performed efficiently in a tensor network form.
 
Suppose we have a certain quantum circuit as shown in the figure below,
Consider splitting this into two operators with separate quantum bits as shown in the figure below.
 
This can be expressed in the following equation We call this decomposition Operator Schmidt Decomposition.
where and are normalized as
The distribution of plays an important role in this context. If takes almost the same value for all , the coupling at the point corresponding to the vertical double line in the middle of the above figure cannot be ignored, leading to increased computational cost when treated in tensor network form.
On the other hand. If decreases quickly (e.g. exponentially) with respect to , then we can prepare quantities such as to introduce the following approximation.
The above approximation gives a relatively small calculation error because takes a value close to zero at large , leading to efficient computation in the tensor network form. [5]
 

“The Quantum Fourier Transform Has Small Entanglement”

 
Now that we have sorted out the quantum Fourier transform and the Operator Schmidt Decomposition, we follow the claim of the main paper [1].
Recall that the procedure of quantum Fourier transform is
  1. compute the following quantum circuit
 
 
2. the operation of reordering the qubits in reverse order using the SWAP gate
 
Previous studies [6,7] show the Operator Schmidt Decomposition of the entire quantum Fourier transform circuit combining the first and second steps shows that is uniform with respect to , i.e., it cannot be handled efficiently in the tensor network format. However, only the first of these operations is significant for the quantum Fourier transform, and numerical calculations have suggested that decreases exponentially with respect to only for this operation, which means that it may be handled efficiently in tensor network form [8]. In this paper [1], the authors show that has an upper bound which decays exponentially with respect to :
The proof is summarized as follows.
 
  • The first of the two steps of the quantum Fourier transform is , and it is proved that can be partitioned into the following elements
    • Quantum Fourier transform using qubits
    • A collection of control phase gates
    • Quantum Fourier transform using qubits
  • Using the above, we can split the circuit as [9]
 
Cit from Fig. 2 of Ref [1]
Cit from Fig. 2 of Ref [1]
  • Since is the most effective part for the Operator Schmidt Decomposition, we only need to focus on .
  • Decompose into its spectrum representation and calculate the distribution of by applying the following formula for the Operator Schmidt Decomposition
 
  • Since computing the singular values of corresponds to computing the eigenvalues of , the following eigenequations with as eigenvalues appears as follows.
  • This eigenequation belongs to a class called periodic discrete prolate spheroidal sequences, in particular by taking the limit of for , the qubit number Since the equation belongs to a class called spheroidal sequences, we can use the existing results for this class to obtain the result that the upper bound of decreases exponentially with respect to , and by using this we can obtain the following result that we finally wanted to find The following result can be obtained.
      • This result shows that the singular value in the Operator Schmidt Decomposition decreases exponentially.

Calculation using the Tensor Network Simulator

Now that we have seen the claims and proofs of the paper [1], we will perform the quantum Fourier transform using a tensor network simulator to see how fast it performs for a given number of qubits.
In performing this calculation, We use the tensor network simulator. The calculation principle is almost the same as in my previous article here (note that this article is written in Japanese).
This tensor network simulator is made by an internship project at Jij, Inc.
https://github.com/OpenJij/TensorNetworkQCircuit
You can install the package by following the INSTALL guide here.
The sample code in python is below:
 
Now let us try to do a quantum Fourier transform of the superposition of 100 qubits. The code is as follows. If the quantum Fourier transform is working as intended, it should output . [10]
 
The result is as follows, which shows that is indeed computed. On the author’s environment (Intel Core i7-8565U @ 8x 4.6GHz), it took about 20 seconds.
In this algorithm, only the cutoff of the singular value decomposition is set, so if the singular values take uniform values, the truncation will not work well, leading to exponential calculation time. Since we did not observe sudden decrease of the calculation speed in the middle of the computation, it seems that the entanglement has been kept at a small level.
Also, if we try to change the circuit a little and comment out some of the SWAP gates and configure it as follows
We observe a significant decrease of the calculation speed in the middle of the process. This suggests that if we perform appropriate operations different from the quantum Fourier transform, the entanglement increases and the truncation of the singular value decomposition to achieve the error of 1e-5 specified by cutoff does not work well, resulting in a large computation time.
 
We demonstrate a benchmark of the quantum Fourier transform starting with a non-trivial state with H-gates and CNOT gates as initial conditions to measure the computational time with respect to the system size. The code is as follows:
 
The plot shows that there is no dependence of computation time, but an dependence.

Summary

In this article, we have shown that
  • An overview of the paper [1] that shows that entanglement can be suppressed to a small degree in the quantum Fourier transform
  • Experiments with the Tensor Network Simulator
The fact that the quantum Fourier transform can be simulated on a classical computer raises the question, "Can Shor's prime factorization algorithm be done in the same way? In fact, Shor's prime factorization algorithm requires an order-finding process, i.e. the phase estimation of the unitary matrix ,
which in general results in increasing entanglement. In addition, although this tensor network simulator is in a different form than the situation set in the paper [1], as mentioned in the note [10], we can confirm that the computation time can be suppressed in polynomial form. If we experiment with a properly constructed Matrix Product Operator as in the paper [1], the performance can be even better.
 
Author: Kohji Nishimura (Jij Inc. CTO)
[1] J. Chen, E. M. Stoudenmire, and S. R. White, (2022).
[2] P. W. Shor, Proceedings 35th Annual Symposium on Foundations of Computer Science (1994).
[3] P. W. Shor, SIAM Journal on Computing 26, 1484 (1997).
[4] This circuit is taken from the article [1], but actually has slightly different from the circuit in Nielsen & Chuang, as shown in the article. We can easily confirm that those circuits are essentially the same by using the property that the control qubit and target qubit are the same even if they are swapped in the control phase gate.
[5] Note that this method does not make sense unless you go through a process called truncation, which ignores small singular values in the process of singular value decomposition in tensor network form, i.e., replacing with a smaller value of .
[6] M. A. Nielsen et al., Physical Review A 67, (2003).
[7] J. Tyson, Journal of Physics A: Mathematical and General 36, 6813 (2003).
[8] K. Woolfe, C. Hill, and L. Hollenberg, Quantum Information and Computation 17 (2014)
[9] The details of the general proof are summarized in Appendix A of the paper [1], but can be shown intuitively by reordering the Hadamard and control phase gates.
[10] In this simulator, the SWAP gate is used in conjunction with the control phase gate to move the qubits when the control phase gate is applied, but the paper [1] proposes a method where the control phase gate is converted directly into a Matrix Product Operator before acting on the quantum state so that the computational complexity between the two might be different.
Xでポスト