qbraid_algorithms.qft

Quantum Fourier Transform (QFT)

This module provides an implementation of the Quantum Fourier Transform (QFT), a fundamental quantum algorithm that performs the discrete Fourier transform on quantum states. The QFT is a cornerstone of quantum computing, serving as a key component in Shor’s algorithm, quantum phase estimation, and many other quantum algorithms requiring frequency domain analysis. The QFT enables efficient transformation between computational and Fourier bases, providing exponential speedup over classical FFT for certain quantum applications.

FORMULATION

Transformation: The QFT maps an \(n\)-qubit computational basis state to a superposition in the Fourier basis:

\(\text{QFT}|j\rangle = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \omega_n^{jk} |k\rangle\)

where \(\omega_n = e^{2\pi i/2^n}\) is the primitive \(2^n\)-th root of unity.

Circuit Implementation: The QFT circuit consists of:

Hadamard Gates: Apply \(H\) to each qubit for uniform superposition

Controlled Phase Rotations: Apply \(R_k\) gates where:

\(R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i/2^k} \end{pmatrix}\)

Swap Operations: Reverse qubit order for correct output

Recursive Structure: For qubit \(j\), the QFT can be written as:

\(\text{QFT}|j\rangle = \frac{1}{\sqrt{2}} \left(|0\rangle + e^{2\pi i \cdot 0.j_n}|1\rangle\right) \otimes \frac{1}{\sqrt{2}} \left(|0\rangle + e^{2\pi i \cdot 0.j_{n-1}j_n}|1\rangle\right) \otimes \ldots\)

Matrix Form: The QFT matrix for \(n\) qubits is:

\(\text{QFT} = \frac{1}{\sqrt{2^n}} \begin{pmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega_n & \omega_n^2 & \cdots & \omega_n^{2^n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega_n^{2^n-1} & \omega_n^{2(2^n-1)} & \cdots & \omega_n^{(2^n-1)^2} \end{pmatrix}\)

Complexity: Requires \(O(n^2)\) gates compared to \(O(n \log n)\) classical complexity, but enables quantum parallelism for quantum states.

Classes

QFTLibrary(*args, **kwargs)

QFTLibrary provides methods to construct and manage Quantum Fourier Transform (QFT) gates, extending GateLibrary for use in quantum algorithms.

Functions

generate_program(num_qubits)

Load the Quantum Fourier Transform circuit as a pyqasm module.

save_to_qasm(num_qubits[, quiet, path])

Creates a QFT subroutine module with user-defined number of qubits.