Quantum computing allows for undertaking certains problems in an efficient manner, although they may be considered intractable in classic computing. This is possible due to the specific features of quantum computing, such as superposition and entanglement. In this paper, a matrix representation of quantum addition using QFT has been described, focused on adding 2 -qubit strings and 3 -qubit strings. In each case, a schematic diagram is shown, along with two alternative implementations, followed by methods to find out QFT and IQFT matrices, and eventually, a step-by-step instance of an addition.
In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantum algorithms can be divided into two classes, QFT based algorithms and search based algorithms. The usual circuit for QFT (covered in almost every basic quantum algorithms course) needs
O(q2) gates (and
O(q) qubits) to perform the exact Fourier transform over
F2q. Cleve and Watrous (FOCS 2000) improved this gate count to
O(q(logq)2(loglogq)) using the integer multiplication algorithm in
O(n(logn)(loglogn)) time for two
n-bit integers (best known at that time). Our first main result shows that this gate count can be improved to
O(q(logq)). In fact, if there is a multiplication circuit, to multiply two
n-bit integers, with
O(n(logn)α) gates; we get a QFT circuit with
O(q(logq)α) gates (improving upon
O(q(logq)α+1)) gates from the construction of Cleve and Watrous). Given the recent claim by OpenAI about integer multiplication, this opens up the possibility of having a QFT circuit with
o(q(logq)) gates. On approximating the QFT over $\ZZ/(2^q \ZZ)$, the result of Ahokas, Cleve and Hales (ERATO 2003) showed that an approximating circuit can be built with
O(q(loglog(q/ε))α+1) gates, where
ε is the approximating parameter. Our second main result again improves this to
O(q(loglog(q/ε))α) gates.
Quantum Fourier transform (QFT) plays a key role in many quantum algorithms, but the existing circuits of QFT are incomplete and lacking the proof of correctness. Furthermore, it is difficult to apply QFT to the concrete field of information processing. Thus, this chapter firstly investigates quantum vision representation (QVR) and develops a model of QVR (MQVR). Then, four complete circuits of QFT and inverse QFT (IQFT) are designed. Meanwhile, this chapter proves the correctness of the four complete circuits using formula derivation. Next, 2D QFT and 3D QFT based on QVR are proposed. Experimental results with simulation show the proposed QFTs are valid and useful in processing quantum images and videos. In conclusion, this chapter develops a complete framework of QFT based on QVR and provides a feasible scheme for QFT to be applied in quantum vision information processing.
. We exhibit a quantum circuit that performs the Quantum Fourier Transform on n qubits in O(n) depth. Thus, a parallel quantum computer can carry out the QFT in linear time. Griffiths and Niu have already shown this, so this paper is little more than an exercise in quantum circuit design; but perhaps it illustrates a worthwhile idea. We also speculate as to whether the QFT might be in the class QNC 1 of problems solvable in logarithmic parallel time. Shor's factoring algorithm [6] suggests that quantum computers can do things in polynomial time that classical computers cannot. However, since decoherence due to storage errors is a function of time, we should also ask to what extent we can parallelize quantum algorithms; if we can do many quantum operations at once, rather than serially, we can solve larger problems before our computer decoheres. Consider a quantum circuit operating on a set of qubits, containing onequbit gates (2 \\Theta 2 unitary matrices) and the two-qubit controlled...
The Quantum Fourier Transformation (QFT) is a well-known subroutine for algorithms on qubit-based universal quantum computers. In this work, the known QFT circuit is used to derive an efficient circuit for the multidimensional QFT. The complexity of the algorithm is
O(log2(M)/d) for an array with
M=(2n)d elements
(n∈N) equally separated along
d dimensions. Relevant properties for application are discussed. An example on current hardware is depicted by a 6 qubit 2D-QFT with an IBM quantum computer.