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.
Quantum Fourier transformation is important in many quantum algorithms. In this paper, we generalize quantum Fourier transformation over the Abelian group
ZN 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.
In this chapter, we will study the quantum Fourier transform and its application in different quantum algorithms. Problems such as factoring an integer into prime numbers or period finding are computationally intractable problems for a classical computer because of the exponentially large number of operations involved. Integer factoring and period finding can be efficiently solved using the quantum phase estimation algorithm that is heavily based on the quantum Fourier transform. Alternately, since quantum phase estimation aims to find the eigenvalue corresponding to an eigenvector of a unitary operator, it is backbone of important algorithms in optimization such as the HHL algorithm (named for Hassim, Harrow, and Lloyd), which serves as the matrix inversion routine in quantum computing. We start this chapter by revising our concepts of the Fourier transform and its discrete counterpart, the discrete Fourier transform , and then move on to the exciting domain of the quantum Fourier transform and the quantum phase estimation algorithm. We follow this up with a discussion and implementation of the few quantum Fourier transform–related algorithms such as factoring a number and period finding. At the end of the chapter, we briefly introduce the basics of group theory with an attempt to explain the hidden subgroup problem and how it relates to several of the Fourier transform–based algorithms.