Quantum Fourier Transform and Quantum Phase Estimation¶
Introduction to QFT¶
The Quantum Fourier Transform (QFT) is a quantum analogue of the classical discrete Fourier transform (DFT). It is a linear transformation on quantum bits and is widely used in quantum algorithms, such as Shor's algorithm for factoring large numbers.
Mathematical Formulation of QFT¶
The QFT on an $n$-qubit quantum state $\psi\rangle$ is defined as follows:
Given an $n$-qubit quantum state: $$ |\psi\rangle = \sum_{k=0}^{2^n-1} x_k |k\rangle $$
The QFT transforms this state into: $$ \text{QFT}|\psi\rangle = \frac{1}{\sqrt{2^n}} \sum_{j=0}^{2^n-1} \left( \sum_{k=0}^{2^n-1} x_k e^{2\pi i jk / 2^n} \right) |j\rangle $$
where $x_k$ are the amplitudes of the quantum state $|\psi\rangle$, and $e^{2\pi i jk / 2^n}$ are the complex exponential factors.
QFT Matrix Representation¶
The QFT can also be represented as a unitary matrix $\mathbf{QFT}$. For an $n$-qubit system, the QFT matrix is a $2^n \times 2^n$ matrix with elements: $$ \mathbf{QFT}_{j,k} = \frac{1}{\sqrt{2^n}} e^{2\pi i jk / 2^n} $$
Example: QFT for 2 Qubits¶
For a 2-qubit system, the QFT matrix is: $$ \mathbf{QFT} = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & e^{2\pi i / 4} & e^{4\pi i / 4} & e^{6\pi i / 4} \\ 1 & e^{4\pi i / 4} & e^{8\pi i / 4} & e^{12\pi i / 4} \\ 1 & e^{6\pi i / 4} & e^{12\pi i / 4} & e^{18\pi i / 4} \end{pmatrix} $$
Simplifying the complex exponentials, we get: $$ \mathbf{QFT} = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix} $$
Implementation of QFT using Qiskit¶
Here is an example implementation of the QFT using Qiskit:
from qiskit import QuantumCircuit
import numpy as np
# Define the number of qubits
n = 3
# Define a function to create a QFT circuit
def create_qft_circuit(n):
qc = QuantumCircuit(n)
for j in range(n):
for k in range(j):
qc.cp(np.pi/2**(j-k), k, j)
qc.h(j)
return qc
# Create a QFT circuit for 3 qubits
qft_circuit = create_qft_circuit(n)
qft_circuit.draw('mpl')
from IPython.display import display, Math
# Define a function to display the matrix in LaTeX format
def display_matrix_latex(matrix):
latex_str = r"\mathbf{QFT} = \begin{pmatrix}"
for row in matrix:
latex_str += " & ".join([f"{val.real:.2f} + {val.imag:.2f}i" for val in row]) + r" \\ "
latex_str = latex_str[:-3] + r"\end{pmatrix}"
display(Math(latex_str))
from qiskit.quantum_info import Operator
# Define the QFT matrix for 3 qubits
qft_mat = Operator(qft_circuit).data
# Display the QFT matrix for 3 qubits
display_matrix_latex(qft_mat)
from qiskit.quantum_info import Statevector
# Get the statevector after applying the QFT circuit
initial_state = Statevector.from_label('000')
statevector_after_qft = initial_state.evolve(qft_circuit)
# Calculate the expected statevector after QFT
expected_statevector = np.fft.ifft(initial_state.data) * np.sqrt(len(initial_state.data))
# Display the statevector in LaTeX format
latex_str = r"\mathbf{QFT} = \begin{pmatrix}"
latex_str += " \\\\ ".join([f"{val.real:.2f} + {val.imag:.2f}i" for val in statevector_after_qft.data])
latex_str += r"\end{pmatrix}"
display(Math(latex_str))
print("Statevector matches expected result:", np.allclose(statevector_after_qft.data, expected_statevector))
Statevector matches expected result: True
from qiskit import ClassicalRegister, transpile
from qiskit.visualization import plot_histogram
from qiskit_aer import AerSimulator
# Plot the histogram of the measurement results
simulator = AerSimulator()
qft_circuit_with_measurement = qft_circuit.copy()
n = qft_circuit.num_qubits
qft_circuit_with_measurement.add_register(ClassicalRegister(n))
qft_circuit_with_measurement.measure_all()
compiled_circuit = transpile(qft_circuit_with_measurement, simulator)
result = simulator.run(compiled_circuit).result()
counts = result.get_counts()
# Plot the histogram
plot_histogram(counts)
Introduction to Quantum Phase Estimation¶
Quantum Phase Estimation (QPE) is a fundamental quantum algorithm used to estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. It is a key component in many quantum algorithms, including Shor's algorithm and quantum simulations.
Mathematical Formulation of Quantum Phase Estimation (QPE)¶
Quantum Phase Estimation is used to estimate the phase $\phi$ in the eigenvalue equation:
$$ U|\psi\rangle = e^{2\pi i \phi}|\psi\rangle $$
where $U$ is a unitary operator, $|\psi\rangle$ is an eigenvector of $U$, and $e^{2\pi i \phi}$ is the corresponding eigenvalue.
The QPE algorithm involves the following steps:
- Initialization: Prepare two registers: The first register with $t$ qubits initialized to $|0\rangle^{\otimes t}$. The second register with $n$ qubits initialized to the eigenvector $|\psi\rangle$.
- Hadamard Transform: Apply the Hadamard gate to each qubit in the first register to create a superposition:
$$ \frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t-1} |k\rangle \otimes |\psi\rangle $$
- Controlled Unitary Operations: Apply controlled-$U^{2^j}$ operations to the second register, where $j$ ranges from $0$ to $t-1$. This step entangles the phase information with the first register:
$$ \frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t-1} |k\rangle \otimes U^k|\psi\rangle = \frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t-1} e^{2\pi i k \phi} |k\rangle \otimes |\psi\rangle $$
- Inverse Quantum Fourier Transform (QFT): Apply the inverse QFT to the first register to transform the phase information into a measurable form:
$$ \frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t-1} e^{2\pi i k \phi} |k\rangle \rightarrow |2^t \phi\rangle $$
- Measurement: Measure the first register. The measurement result will be an approximation of $2^t \phi$, from which $\phi$ can be estimated.
Example Implementation of QPE using Qiskit¶
# Define a function to create a QFT circuit
def create_qft_circuit(n):
qc = QuantumCircuit(n)
for qubit in range(n):
qc.h(qubit)
for other_qubit in range(qubit + 1, n):
qc.cp(np.pi / 2**(other_qubit - qubit), qubit, other_qubit)
for qubit in range(n // 2):
qc.swap(qubit, n - qubit - 1)
return qc
# Define a function to create a QPE circuit
def create_qpe_circuit(unitary, t, n):
qc = QuantumCircuit(t + n, t)
# Apply Hadamard gates to the first t qubits
for qubit in range(t):
qc.h(qubit)
# Apply controlled unitary operations
for qubit in range(t):
qc.append(unitary.control(), [qubit] + list(range(t, t + n)))
# Apply inverse QFT to the first t qubits
qc.append(create_qft_circuit(t).inverse(), range(t))
# Measure the first t qubits
qc.measure(range(t), range(t))
return qc
# Example: QPE circuit for a 3-qubit unitary and 2-qubit eigenstate
t = 2
n = 3
qft_circuit = create_qft_circuit(n)
unitary = qft_circuit.to_gate(label="QFT")
qpe_circuit = create_qpe_circuit(unitary, t, n)
qpe_circuit.draw('mpl')
# Simulate the QPE circuit using Qiskit
simulator = AerSimulator()
compiled_circuit = transpile(qpe_circuit, simulator)
result = simulator.run(compiled_circuit).result()
counts = result.get_counts()
# Plot the histogram of the measurement results
plot_histogram(counts)
Relationship between QFT and Quantum Phase Estimation¶
Quantum Phase Estimation (QPE) leverages the Quantum Fourier Transform (QFT) to estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. The QFT is a crucial component in the QPE algorithm, transforming the phase information into a measurable form.
Similarities¶
- Mathematical Foundation: Both QFT and QPE rely on the principles of quantum mechanics and linear algebra. QFT is a linear transformation that maps quantum states to their frequency domain, while QPE uses this transformation to extract phase information.
- Quantum Gates: Both algorithms use quantum gates such as Hadamard gates and controlled phase gates. QFT uses these gates to create superpositions and entangle qubits, while QPE uses them to apply controlled unitary operations.
- Unitary Operations: Both QFT and QPE involve unitary operations. QFT itself is a unitary transformation, and QPE uses unitary operators to encode the phase information.
Differences¶
- Purpose: The primary purpose of QFT is to transform a quantum state into its frequency domain representation. In contrast, QPE aims to estimate the phase (eigenvalue) of an eigenvector of a unitary operator.
- Application: QFT is used in various quantum algorithms, such as Shor's algorithm for factoring large numbers. QPE is specifically used to estimate phases and is a key component in algorithms like Shor's algorithm and quantum simulations.
- Algorithm Structure: QFT is a standalone transformation, while QPE is an algorithm that incorporates QFT as a subroutine. QPE involves additional steps such as preparing the initial state, applying controlled unitary operations, and measuring the qubits.
Applications of QFT and Quantum Phase Estimation¶
Quantum Fourier Transform (QFT) and Quantum Phase Estimation (QPE) have several important applications in quantum computing. Below are some of the key applications:
Shor's Algorithm for Factoring Large Numbers¶
Shor's algorithm uses QFT to find the period of a function, which is a crucial step in factoring large numbers efficiently. This has significant implications for cryptography.
Quantum Simulations¶
QPE is used in quantum simulations to estimate the eigenvalues of a unitary operator, which is essential for simulating quantum systems and solving problems in quantum chemistry and material science.
Solving Linear Systems of Equations¶
The Harrow-Hassidim-Lloyd (HHL) algorithm uses QPE to solve linear systems of equations exponentially faster than classical algorithms.
Finding Eigenvalues and Eigenvectors¶
QPE can be used to find the eigenvalues and eigenvectors of a unitary operator, which has applications in various quantum algorithms and quantum machine learning.
Quantum Cryptography¶
QFT and QPE can be used in quantum cryptographic protocols to enhance security and develop new cryptographic schemes.
Conclusion¶
The Quantum Fourier Transform (QFT) and Quantum Phase Estimation (QPE) are closely related, with QFT being a critical component of the QPE algorithm. QFT transforms quantum states into their frequency domain representations, while QPE uses this transformation to estimate the phase of an eigenvalue of a unitary operator. Understanding the relationship between QFT and QPE is essential for developing advanced quantum algorithms and systems.