Quantum Fourier Transform

Osama M. Raisuddin, Suvranu De

青木, 隆;AOKI, Takashi, Yusuke Maesaka, Mikio Nakahara

The spectral decomposition of an n-qubit quantum Fourier transform (QFT_n) is derived exactly. It is then applied to find the logarithm of a QFT_n gate. Hamiltonian which generates QFT_n in a single step is suggested.

Hayato Goto

We investigate resource requirements for a fault-tolerant quantum Fourier transform. The quantum Fourier transform is a basic subroutine for quantum algorithms which provide an exponential speedup over known classical ones, such as Shor's algorithm for factoring. To implement single-qubit rotations required for a quantum Fourier transform in a fault-tolerant manner, we consider two types of approaches: gate synthesis and state distillation. While the gate synthesis approximates single-qubit rotations with basic quantum operations, the state distillation allows one to perform single-qubit rotations for a quantum Fourier transform exactly. It is unknown, however, which approach is better for a quantum Fourier transform. Here we develop a state-distillation method optimized for a quantum Fourier transform and compare this performance with those of state-of-the-art techniques for gate synthesis without and with ancillary states (ancillas). The performance is evaluated with the resource requirement for a quantum Fourier transform. The resource is measured by the total number of $\ensuremath{\pi}/8$ gates denoted by $T$, which is called the $T$ count. Contrary to the expectation, the $T$ count for the state distillation is considerably larger than those for the ancilla-free and ancilla-assisted gate synthesis. Thus, we conclude that the ancilla-assisted gate synthesis is a better approach to a fault-tolerant quantum Fourier transform.

François Chapeau‐Blondeau

Marco O. Lanzagorta, Jeffrey K. Uhlmann

Changpeng Shao

Quantum Fourier transformation is important in many quantum algorithms. In this paper, we generalize quantum Fourier transformation over the Abelian group $\mathbb{Z}_N$ from two different points to get more efficient unitary transformations. The obtained unitary transformations are given in concise and explicit formula which can be used directly. A relationship between the generalized quantum Fourier transformation and the dihedral hidden subgroup problem are discussed in this paper. This may lead a way to solve the dihedral hidden subgroup problem. The second goal of this paper is to give an explicit formula of quantum Haar transformation.