Lecture Notes on Quantum Algorithms and Fourier Transform

Author

Your Name

Published

February 5, 2025

Introduction

This lecture revisits a quantum algorithm, emphasizing the principle of phase kick-back. We will explore its application in determining function properties, specifically distinguishing between constant and balanced functions, as exemplified by Deutsch’s algorithm. Furthermore, we will introduce the Discrete Fourier Transform (DFT) and its relevance in quantum computing. This will serve as a foundation for understanding the Quantum Fourier Transform and its applications in operator estimation and more advanced quantum algorithms.

Quantum Algorithm and Phase Kick-back

We now detail a quantum algorithm that prominently features phase kick-back. As previously mentioned, phase kick-back is a crucial effect where a control qubit acquires a phase shift due to operations on a controlled qubit. This algorithm is designed to leverage this effect.

Consider a quantum circuit operating on $n+1$ qubits. The initial $n$ qubits serve as input and workspace, while the $(n+1)^{th}$ qubit is used to observe the output influenced by phase kick-back. The algorithm proceeds as follows:

Initialization: The first $n$ qubits are initialized to $\left|{0}\right\rangle$, and the $(n+1)^{th}$ qubit is initialized to $\left|{1}\right\rangle$. This specific initialization is critical for observing phase kick-back.
Hadamard Gates: Apply Hadamard gates to each of the first $n$ qubits. This transforms the initial state of these qubits into a superposition of all possible $n$-bit strings.
Oracle Application: Apply the unitary operator $U_F$, which is a quantum implementation of a classical function $F: \{0, 1\}^n \rightarrow \{0, 1\}$. The operator $U_F$ acts as $U_F \left|{x}\right\rangle\left|{y}\right\rangle = \left|{x}\right\rangle\left|{y \oplus F(x)}\right\rangle$, where $\oplus$ is addition modulo 2. This operation is applied to the state prepared in the previous step, utilizing the $(n+1)^{th}$ qubit as the target.
Hadamard Gates (again): Apply Hadamard gates again to the first $n$ qubits. This step is crucial for extracting information about the function $F$.
Measurement: Measure the first $n$ qubits in the computational basis. The measurement outcomes provide information about the property of the function $F$.

Circuit Components and Function $U_F$

The core component of this circuit is the unitary operator $U_F$, which embodies the function $F$. When $U_F$ acts on a state $\left|{x}\right\rangle\left|{y}\right\rangle$, it computes $F(x)$ and XORs the result with $y$ in the second register, leaving the first register $\left|{x}\right\rangle$ unchanged. In this algorithm, we exploit $U_F$ to deduce global properties of $F$, such as whether it is constant or balanced, rather than computing $F(x)$ for a specific $x$.

Initialization for Phase Kick-back Effect

The initialization step is not arbitrary; setting the $(n+1)^{th}$ qubit to $\left|{1}\right\rangle$ is essential for the phase kick-back mechanism to manifest effectively. If we were to initialize it to $\left|{0}\right\rangle$, the phase kick-back effect, which is central to this algorithm, would not be directly observable in the same manner.

Creating Superposition with Hadamard Gates

Applying Hadamard gates to the first $n$ qubits, initially in the state $\left|{0}\right\rangle^{\otimes n}$, generates a uniform superposition over all $n$-bit strings. Mathematically, this transformation is represented as: \[H^{\otimes n} \left|{0}\right\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0, 1\}^n} \left|{x}\right\rangle = \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} \left|{i}\right\rangle\] For the $(n+1)^{th}$ qubit, initialized to $\left|{1}\right\rangle$, applying a Hadamard gate results in: \[H\left|{1}\right\rangle = \frac{1}{\sqrt{2}} (\left|{0}\right\rangle - \left|{1}\right\rangle)\] Combining these, the state after applying Hadamard gates to all $n+1$ qubits is: \[\frac{1}{\sqrt{2^{n+1}}} \left( \sum_{x \in \{0, 1\}^n} \left|{x}\right\rangle \right) (\left|{0}\right\rangle - \left|{1}\right\rangle)\] This state serves as the input to the $U_F$ operation, setting the stage for the phase kick-back effect in the subsequent steps of the algorithm.

Deutsch’s Algorithm: Determining Constant vs. Balanced Functions

Deutsch’s algorithm addresses the problem of distinguishing whether a Boolean function $F: \{0, 1\}^n \rightarrow \{0, 1\}$ is constant or balanced.

Problem Definition

Given a function $F: \{0, 1\}^n \rightarrow \{0, 1\}$, we want to determine if $F$ is one of the following:

Constant: $F(x) = c$ for all $x \in \{0, 1\}^n$, where $c \in \{0, 1\}$ is a fixed value.
Balanced: $F(x) = 0$ for exactly half of the inputs $x \in \{0, 1\}^n$ and $F(x) = 1$ for the other half.

Classically, determining this property requires evaluating $F$ for at least $2^{n-1} + 1$ inputs in the worst case. Deutsch’s algorithm achieves this with a single query to a quantum oracle implementing $F$.

Quantum Circuit and Phase Kick-back Mechanism

The algorithm utilizes the phase kick-back effect. Starting with the state prepared after applying Hadamard gates as described in [sec:quantum-algorithm-and-phase-kick-back], we apply the oracle $U_F$. Consider the action of $U_F$ on a basis state $\left|{i}\right\rangle$ of the input register and the state $\frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle)$ of the output qubit: \[U_F \left[ \left|{i}\right\rangle \otimes \frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle) \right] = \frac{1}{\sqrt{2}} \left( U_F \left|{i}\right\rangle\left|{0}\right\rangle - U_F \left|{i}\right\rangle\left|{1}\right\rangle \right)\] Using the definition of $U_F \left|{x}\right\rangle\left|{y}\right\rangle = \left|{x}\right\rangle\left|{y \oplus F(x)}\right\rangle$: \[= \frac{1}{\sqrt{2}} \left( \left|{i}\right\rangle\left|{0 \oplus F(i)}\right\rangle - \left|{i}\right\rangle\left|{1 \oplus F(i)}\right\rangle \right) = \frac{1}{\sqrt{2}} \left( \left|{i}\right\rangle\left|{F(i)}\right\rangle - \left|{i}\right\rangle\left|{1 \oplus F(i)}\right\rangle \right)\] We analyze two cases based on the value of $F(i)$:

If $F(i) = 0$: \[\frac{1}{\sqrt{2}} \left( \left|{i}\right\rangle\left|{0}\right\rangle - \left|{i}\right\rangle\left|{1}\right\rangle \right) = (-1)^{0} \left|{i}\right\rangle \left( \frac{\left|{0}\right\rangle - \left|{1}\right\rangle}{\sqrt{2}} \right) = (-1)^{F(i)} \left|{i}\right\rangle \left( \frac{\left|{0}\right\rangle - \left|{1}\right\rangle}{\sqrt{2}} \right)\]
If $F(i) = 1$: \[\frac{1}{\sqrt{2}} \left( \left|{i}\right\rangle\left|{1}\right\rangle - \left|{i}\right\rangle\left|{0}\right\rangle \right) = - \frac{1}{\sqrt{2}} \left( \left|{i}\right\rangle\left|{0}\right\rangle - \left|{i}\right\rangle\left|{1}\right\rangle \right) = (-1)^{1} \left|{i}\right\rangle \left( \frac{\left|{0}\right\rangle - \left|{1}\right\rangle}{\sqrt{2}} \right) = (-1)^{F(i)} \left|{i}\right\rangle \left( \frac{\left|{0}\right\rangle - \left|{1}\right\rangle}{\sqrt{2}} \right)\]

In both cases, a phase factor $(-1)^{F(i)}$ is kicked back to the input register: \[U_F \left[ \left|{i}\right\rangle \otimes \frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle) \right] = (-1)^{F(i)} \left|{i}\right\rangle \otimes \frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle)\] Applying $U_F$ to the superposition state $\frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} \left|{i}\right\rangle \otimes \frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle)$ yields: \[U_F \left[ \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} \left|{i}\right\rangle \otimes \frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle) \right] = \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} (-1)^{F(i)} \left|{i}\right\rangle \otimes \frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle)\] The state of the first register after applying $U_F$ is thus: \[\left|{\psi_1}\right\rangle = \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} (-1)^{F(i)} \left|{i}\right\rangle\] The output qubit remains in the state $\frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle)$ and is henceforth disregarded as we focus on measurements of the first $n$ qubits.

Final Hadamard Gates and Measurement

To extract the global property of $F$, we apply Hadamard gates to the first $n$ qubits again. Applying $H^{\otimes n}$ to $\left|{\psi_1}\right\rangle$: \[H^{\otimes n} \left|{\psi_1}\right\rangle = H^{\otimes n} \left( \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} (-1)^{F(i)} \left|{i}\right\rangle \right) = \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} (-1)^{F(i)} H^{\otimes n} \left|{i}\right\rangle\] Using the transformation of Hadamard gates on basis states $H^{\otimes n} \left|{i}\right\rangle = \frac{1}{\sqrt{2^n}} \sum_{j=0}^{2^n-1} (-1)^{i \cdot j} \left|{j}\right\rangle$, where $i \cdot j$ is the bitwise dot product of $i$ and $j$: \[H^{\otimes n} \left|{\psi_1}\right\rangle = \frac{1}{2^n} \sum_{i=0}^{2^n-1} (-1)^{F(i)} \sum_{j=0}^{2^n-1} (-1)^{i \cdot j} \left|{j}\right\rangle = \frac{1}{2^n} \sum_{j=0}^{2^n-1} \left( \sum_{i=0}^{2^n-1} (-1)^{F(i) + i \cdot j} \right) \left|{j}\right\rangle\] We are interested in the probability of measuring $\left|{0}\right\rangle^{\otimes n}$, which corresponds to the coefficient of $\left|{j=0}\right\rangle$. For $j=0$, $i \cdot j = 0$, and $(-1)^{i \cdot j} = 1$. Thus, the coefficient of $\left|{0}\right\rangle^{\otimes n}$ is: \[C_0 = \frac{1}{2^n} \sum_{i=0}^{2^n-1} (-1)^{F(i)}\] Analyzing $C_0$ for constant and balanced functions:

Constant Function:
- If $F(i) = 0$ for all $i$: $C_0 = \frac{1}{2^n} \sum_{i=0}^{2^n-1} (-1)^{0} = \frac{1}{2^n} \sum_{i=0}^{2^n-1} 1 = \frac{2^n}{2^n} = 1$.
- If $F(i) = 1$ for all $i$: $C_0 = \frac{1}{2^n} \sum_{i=0}^{2^n-1} (-1)^{1} = \frac{1}{2^n} \sum_{i=0}^{2^n-1} -1 = \frac{-2^n}{2^n} = -1$.
In both constant cases, $|C_0|^2 = 1$.
Balanced Function: For a balanced function, exactly half of the $F(i)$ values are 0 and half are 1. Therefore, the sum contains $2^{n-1}$ terms of $+1$ and $2^{n-1}$ terms of $-1$. \[C_0 = \frac{1}{2^n} (2^{n-1} \cdot (+1) + 2^{n-1} \cdot (-1)) = \frac{1}{2^n} (2^{n-1} - 2^{n-1}) = 0\] Thus, $|C_0|^2 = 0$.

Measurement Outcome and Function Type

Definition 1 (Measurement Outcome and Function Type in Deutsch’s Algorithm). The probability of measuring $\left|{0}\right\rangle^{\otimes n}$ is $P(\left|{0}\right\rangle^{\otimes n}) = |C_0|^2$.

If $P(\left|{0}\right\rangle^{\otimes n}) = 1$, the function $F$ is constant.
If $P(\left|{0}\right\rangle^{\otimes n}) = 0$, the function $F$ is balanced.

By performing a single measurement of the first $n$ qubits, we can determine whether $F$ is constant or balanced with certainty.

Complexity Analysis

Remark. Remark 1 (Complexity Analysis of Deutsch’s Algorithm).

Query Complexity: Deutsch’s algorithm requires only one query to the oracle $U_F$.
Classical Complexity: Classically, in the worst case, determining if $F$ is constant or balanced requires evaluating $F$ for up to $2^{n-1} + 1$ inputs.

Deutsch’s algorithm demonstrates a quantum advantage by solving the problem with a significantly reduced number of queries compared to classical methods. This highlights the power of quantum computation in reducing query complexity for specific computational tasks.

Utilizes phase kick-back to extract global function properties.
Distinguishes between constant and balanced functions with a single query.
Demonstrates a quantum advantage in query complexity over classical algorithms for this problem.
Relies on superposition and interference to achieve its result.

Discrete Fourier Transform (DFT)

The Discrete Fourier Transform (DFT) is a fundamental mathematical tool with applications across various fields, including signal processing and quantum computing. It decomposes a discrete-time signal into its constituent frequencies, analogous to how a prism decomposes white light into its colors. In quantum algorithms, the DFT, particularly in its quantum form (QFT), plays a crucial role in algorithms like Shor’s algorithm and quantum phase estimation.

Definition of Discrete Fourier Transform

Definition 2 (Discrete Fourier Transform (DFT)). The DFT transforms a sequence of $N$ complex numbers $\{x_0, x_1, \ldots, x_{N-1}\}$ into another sequence of $N$ complex numbers $\{y_0, y_1, \ldots, y_{N-1}\}$ using the formula: \[y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2\pi i j k / N} \label{eq:dft_definition}\] for $k = 0, 1, \ldots, N-1$. Here, $N$ is the size of the input sequence, and the factor $\frac{1}{\sqrt{N}}$ ensures that the transform is unitary, preserving the norm of the vector space.

Application: Polynomial Multiplication

One notable application of the DFT lies in efficient polynomial multiplication. Consider two polynomials $P(x) = \sum_{i=0}^{n} a_i x^i$ and $Q(x) = \sum_{j=0}^{m} b_j x^j$. Their product $R(x) = P(x)Q(x) = \sum_{k=0}^{n+m} c_k x^k$, where the coefficients $c_k$ are given by the convolution of the coefficients of $P(x)$ and $Q(x)$: $c_k = \sum_{i+j=k} a_i b_j$.

Direct convolution calculation requires $O(nm)$ operations. However, by using the DFT, we can reduce the complexity to $O(N \log N)$, where $N \approx n+m$. The process involves these steps:

Transform to Point-Value Representation: Evaluate $P(x)$ and $Q(x)$ at $N \ge n+m+1$ points using the DFT. This converts the coefficient representation to a point-value representation.
Point-wise Multiplication: Multiply the point-values of $P(x)$ and $Q(x)$ at each of the $N$ points to obtain the point-values of the product $R(x)$.
Inverse Transform to Coefficient Representation: Use the inverse DFT to interpolate the point-value representation of $R(x)$ back to its coefficient representation.

The efficiency is achieved by using the Fast Fourier Transform (FFT), an algorithm that computes the DFT in $O(N \log N)$ time.

DFT in Quantum Computing and Operator Estimation

In quantum computing, the Quantum Fourier Transform (QFT) is the quantum analogue of the DFT, operating on quantum states. It is a crucial subroutine in various quantum algorithms, including:

Shor’s Algorithm: For integer factorization, where QFT is used to find the period of a function.
Quantum Phase Estimation: For estimating the eigenvalues (phases) of unitary operators, a fundamental task in quantum simulation and algorithm design.

The QFT allows for efficient manipulation of amplitudes in the frequency domain, enabling quantum algorithms to solve problems intractable for classical computers.

DFT of Computational Basis States

Definition 3 (DFT of Computational Basis States). Consider the action of the DFT on computational basis states $\left|{j}\right\rangle$ in an $n$-qubit system, where $j \in \{0, 1, \ldots, N-1\}$ and $N = 2^n$. Applying the DFT to a basis state $\left|{j}\right\rangle$ yields: \[DFT \left|{j}\right\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i j k / N} \left|{k}\right\rangle \label{eq:dft_basis_state}\] This transformation creates a superposition of all basis states $\left|{k}\right\rangle$, with coefficients determined by the complex exponential term.

Examples of DFT for Small N

DFT for N=4 (Two Qubits)

Let $N=4$ (two qubits). We examine the DFT of basis states $\left|{00}\right\rangle = \left|{0}\right\rangle$ and $\left|{01}\right\rangle = \left|{1}\right\rangle$.

DFT of $\left|{00}\right\rangle$

Example 1 (DFT of $\left|{00}\right\rangle$ for N=4). \[\begin{aligned} DFT \left|{00}\right\rangle &= \frac{1}{\sqrt{4}} \sum_{k=0}^{3} e^{2\pi i \cdot 0 \cdot k / 4} \left|{k}\right\rangle \\ &= \frac{1}{2} \sum_{k=0}^{3} e^{0} \left|{k}\right\rangle \\ &= \frac{1}{2} (\left|{00}\right\rangle + \left|{01}\right\rangle + \left|{10}\right\rangle + \left|{11}\right\rangle)\end{aligned}\] The DFT of $\left|{00}\right\rangle$ results in an equal superposition of all two-qubit basis states.

DFT of $\left|{01}\right\rangle$

Example 2 (DFT of $\left|{01}\right\rangle$ for N=4). \[\begin{aligned} DFT \left|{01}\right\rangle &= \frac{1}{2} \sum_{k=0}^{3} e^{2\pi i \cdot 1 \cdot k / 4} \left|{k}\right\rangle \\ &= \frac{1}{2} \left( e^{2\pi i \cdot 1 \cdot 0 / 4} \left|{00}\right\rangle + e^{2\pi i \cdot 1 \cdot 1 / 4} \left|{01}\right\rangle + e^{2\pi i \cdot 1 \cdot 2 / 4} \left|{10}\right\rangle + e^{2\pi i \cdot 1 \cdot 3 / 4} \left|{11}\right\rangle \right) \\ &= \frac{1}{2} \left( e^{0} \left|{00}\right\rangle + e^{i\pi/2} \left|{01}\right\rangle + e^{i\pi} \left|{10}\right\rangle + e^{3i\pi/2} \left|{11}\right\rangle \right) \\ &= \frac{1}{2} \left( \left|{00}\right\rangle + i \left|{01}\right\rangle - \left|{10}\right\rangle - i \left|{11}\right\rangle \right) \\ &= \frac{1}{2} (\left|{0}\right\rangle - \left|{1}\right\rangle) \otimes (\left|{0}\right\rangle + i\left|{1}\right\rangle)\end{aligned}\]

DFT for N=2 (One Qubit) and Hadamard Equivalence

For $N=2$ (one qubit), we examine the DFT of basis states $\left|{0}\right\rangle$ and $\left|{1}\right\rangle$.

DFT of $\left|{0}\right\rangle$

Example 3 (DFT of $\left|{0}\right\rangle$ for N=2). \[\begin{aligned} DFT \left|{0}\right\rangle &= \frac{1}{\sqrt{2}} \sum_{k=0}^{1} e^{2\pi i \cdot 0 \cdot k / 2} \left|{k}\right\rangle \\ &= \frac{1}{\sqrt{2}} (e^{0} \left|{0}\right\rangle + e^{0} \left|{1}\right\rangle) \\ &= \frac{1}{\sqrt{2}} (\left|{0}\right\rangle + \left|{1}\right\rangle) = H\left|{0}\right\rangle\end{aligned}\]

DFT of $\left|{1}\right\rangle$

Example 4 (DFT of $\left|{1}\right\rangle$ for N=2). \[\begin{aligned} DFT \left|{1}\right\rangle &= \frac{1}{\sqrt{2}} \sum_{k=0}^{1} e^{2\pi i \cdot 1 \cdot k / 2} \left|{k}\right\rangle \\ &= \frac{1}{\sqrt{2}} (e^{0} \left|{0}\right\rangle + e^{2\pi i / 2} \left|{1}\right\rangle) \\ &= \frac{1}{\sqrt{2}} (\left|{0}\right\rangle + e^{i\pi} \left|{1}\right\rangle) \\ &= \frac{1}{\sqrt{2}} (\left|{0}\right\rangle - \left|{1}\right\rangle) = H\left|{1}\right\rangle\end{aligned}\]

Remark. Remark 2 (Hadamard Equivalence to DFT for N=2). For a single qubit ($N=2$), the DFT is mathematically equivalent to the Hadamard transform $H$. This establishes the Hadamard gate as a specific instance of the DFT in a two-dimensional Hilbert space.

Transforms Time Domain to Frequency Domain: Decomposes a signal into its frequency components.
Unitary Transformation: Preserves the norm in vector spaces, crucial for quantum mechanics.
Efficient Polynomial Multiplication: Reduces complexity from $O(n^2)$ to $O(n \log n)$ using FFT.
Foundation for QFT: Classical DFT is the basis for the Quantum Fourier Transform, essential in quantum algorithms.
Hadamard as a Special Case: For a single qubit, DFT is equivalent to the Hadamard transform.

Conclusion

In this lecture, we investigated a quantum algorithm that effectively utilizes phase kick-back, focusing on Deutsch’s algorithm as a prime example for differentiating between constant and balanced functions. We demonstrated the quantum advantage in query complexity offered by such algorithms for specific problems. Subsequently, we introduced the Discrete Fourier Transform (DFT), elucidating its definition, its application in efficient polynomial multiplication, and its critical role in quantum computing, particularly as the classical counterpart to the Quantum Fourier Transform. We also highlighted the significant observation that the Hadamard transform is a specific instance of the DFT in the single-qubit scenario.

Looking ahead, future lectures will delve deeper into the Quantum Fourier Transform algorithm, including its circuit implementation and its pivotal applications in quantum phase estimation and Shor’s algorithm. Further exploration into the entanglement characteristics of these quantum circuits and the analysis of function properties beyond the constant versus balanced dichotomy will also be considered, providing a more comprehensive understanding of quantum algorithms and their capabilities.

--- title: "Lecture Notes on Quantum Algorithms and Fourier Transform" author: "Your Name" date: "2025-02-05" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This lecture revisits a quantum algorithm, emphasizing the principle of phase kick-back. We will explore its application in determining function properties, specifically distinguishing between constant and balanced functions, as exemplified by Deutsch's algorithm. Furthermore, we will introduce the Discrete Fourier Transform (DFT) and its relevance in quantum computing. This will serve as a foundation for understanding the Quantum Fourier Transform and its applications in operator estimation and more advanced quantum algorithms. ## Quantum Algorithm and Phase Kick-back We now detail a quantum algorithm that prominently features **phase kick-back**. As previously mentioned, phase kick-back is a crucial effect where a control qubit acquires a phase shift due to operations on a controlled qubit. This algorithm is designed to leverage this effect. Consider a quantum circuit operating on $n+1$ qubits. The initial $n$ qubits serve as input and workspace, while the $(n+1)^{th}$ qubit is used to observe the output influenced by phase kick-back. The algorithm proceeds as follows: 1. **Initialization**: The first $n$ qubits are initialized to $\left|{0}\right\rangle$, and the $(n+1)^{th}$ qubit is initialized to $\left|{1}\right\rangle$. This specific initialization is critical for observing phase kick-back. 2. **Hadamard Gates**: Apply Hadamard gates to each of the first $n$ qubits. This transforms the initial state of these qubits into a superposition of all possible $n$-bit strings. 3. **Oracle Application**: Apply the unitary operator $U_F$, which is a quantum implementation of a classical function $F: \{0, 1\}^n \rightarrow \{0, 1\}$. The operator $U_F$ acts as $U_F \left|{x}\right\rangle\left|{y}\right\rangle = \left|{x}\right\rangle\left|{y \oplus F(x)}\right\rangle$, where $\oplus$ is addition modulo 2. This operation is applied to the state prepared in the previous step, utilizing the $(n+1)^{th}$ qubit as the target. 4. **Hadamard Gates (again)**: Apply Hadamard gates again to the first $n$ qubits. This step is crucial for extracting information about the function $F$. 5. **Measurement**: Measure the first $n$ qubits in the computational basis. The measurement outcomes provide information about the property of the function $F$. ## Circuit Components and Function $U_F$ The core component of this circuit is the unitary operator $U_F$, which embodies the function $F$. When $U_F$ acts on a state $\left|{x}\right\rangle\left|{y}\right\rangle$, it computes $F(x)$ and XORs the result with $y$ in the second register, leaving the first register $\left|{x}\right\rangle$ unchanged. In this algorithm, we exploit $U_F$ to deduce global properties of $F$, such as whether it is constant or balanced, rather than computing $F(x)$ for a specific $x$. ## Initialization for Phase Kick-back Effect The initialization step is not arbitrary; setting the $(n+1)^{th}$ qubit to $\left|{1}\right\rangle$ is essential for the phase kick-back mechanism to manifest effectively. If we were to initialize it to $\left|{0}\right\rangle$, the phase kick-back effect, which is central to this algorithm, would not be directly observable in the same manner. ## Creating Superposition with Hadamard Gates Applying Hadamard gates to the first $n$ qubits, initially in the state $\left|{0}\right\rangle^{\otimes n}$, generates a uniform superposition over all $n$-bit strings. Mathematically, this transformation is represented as: $$H^{\otimes n} \left|{0}\right\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0, 1\}^n} \left|{x}\right\rangle = \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} \left|{i}\right\rangle$$ For the $(n+1)^{th}$ qubit, initialized to $\left|{1}\right\rangle$, applying a Hadamard gate results in: $$H\left|{1}\right\rangle = \frac{1}{\sqrt{2}} (\left|{0}\right\rangle - \left|{1}\right\rangle)$$ Combining these, the state after applying Hadamard gates to all $n+1$ qubits is: $$\frac{1}{\sqrt{2^{n+1}}} \left( \sum_{x \in \{0, 1\}^n} \left|{x}\right\rangle \right) (\left|{0}\right\rangle - \left|{1}\right\rangle)$$ This state serves as the input to the $U_F$ operation, setting the stage for the phase kick-back effect in the subsequent steps of the algorithm. # Deutsch's Algorithm: Determining Constant vs. Balanced Functions Deutsch's algorithm addresses the problem of distinguishing whether a Boolean function $F: \{0, 1\}^n \rightarrow \{0, 1\}$ is constant or balanced. ## Problem Definition Given a function $F: \{0, 1\}^n \rightarrow \{0, 1\}$, we want to determine if $F$ is one of the following: - **Constant**: $F(x) = c$ for all $x \in \{0, 1\}^n$, where $c \in \{0, 1\}$ is a fixed value. - **Balanced**: $F(x) = 0$ for exactly half of the inputs $x \in \{0, 1\}^n$ and $F(x) = 1$ for the other half. Classically, determining this property requires evaluating $F$ for at least $2^{n-1} + 1$ inputs in the worst case. Deutsch's algorithm achieves this with a single query to a quantum oracle implementing $F$. ## Quantum Circuit and Phase Kick-back Mechanism The algorithm utilizes the phase kick-back effect. Starting with the state prepared after applying Hadamard gates as described in [\[sec:quantum-algorithm-and-phase-kick-back\]](#sec:quantum-algorithm-and-phase-kick-back){reference-type="ref+label" reference="sec:quantum-algorithm-and-phase-kick-back"}, we apply the oracle $U_F$. Consider the action of $U_F$ on a basis state $\left|{i}\right\rangle$ of the input register and the state $\frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle)$ of the output qubit: $$U_F \left[ \left|{i}\right\rangle \otimes \frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle) \right] = \frac{1}{\sqrt{2}} \left( U_F \left|{i}\right\rangle\left|{0}\right\rangle - U_F \left|{i}\right\rangle\left|{1}\right\rangle \right)$$ Using the definition of $U_F \left|{x}\right\rangle\left|{y}\right\rangle = \left|{x}\right\rangle\left|{y \oplus F(x)}\right\rangle$: $$= \frac{1}{\sqrt{2}} \left( \left|{i}\right\rangle\left|{0 \oplus F(i)}\right\rangle - \left|{i}\right\rangle\left|{1 \oplus F(i)}\right\rangle \right) = \frac{1}{\sqrt{2}} \left( \left|{i}\right\rangle\left|{F(i)}\right\rangle - \left|{i}\right\rangle\left|{1 \oplus F(i)}\right\rangle \right)$$ We analyze two cases based on the value of $F(i)$: - If $F(i) = 0$: $$\frac{1}{\sqrt{2}} \left( \left|{i}\right\rangle\left|{0}\right\rangle - \left|{i}\right\rangle\left|{1}\right\rangle \right) = (-1)^{0} \left|{i}\right\rangle \left( \frac{\left|{0}\right\rangle - \left|{1}\right\rangle}{\sqrt{2}} \right) = (-1)^{F(i)} \left|{i}\right\rangle \left( \frac{\left|{0}\right\rangle - \left|{1}\right\rangle}{\sqrt{2}} \right)$$ - If $F(i) = 1$: $$\frac{1}{\sqrt{2}} \left( \left|{i}\right\rangle\left|{1}\right\rangle - \left|{i}\right\rangle\left|{0}\right\rangle \right) = - \frac{1}{\sqrt{2}} \left( \left|{i}\right\rangle\left|{0}\right\rangle - \left|{i}\right\rangle\left|{1}\right\rangle \right) = (-1)^{1} \left|{i}\right\rangle \left( \frac{\left|{0}\right\rangle - \left|{1}\right\rangle}{\sqrt{2}} \right) = (-1)^{F(i)} \left|{i}\right\rangle \left( \frac{\left|{0}\right\rangle - \left|{1}\right\rangle}{\sqrt{2}} \right)$$ In both cases, a phase factor $(-1)^{F(i)}$ is kicked back to the input register: $$U_F \left[ \left|{i}\right\rangle \otimes \frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle) \right] = (-1)^{F(i)} \left|{i}\right\rangle \otimes \frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle)$$ Applying $U_F$ to the superposition state $\frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} \left|{i}\right\rangle \otimes \frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle)$ yields: $$U_F \left[ \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} \left|{i}\right\rangle \otimes \frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle) \right] = \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} (-1)^{F(i)} \left|{i}\right\rangle \otimes \frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle)$$ The state of the first register after applying $U_F$ is thus: $$\left|{\psi_1}\right\rangle = \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} (-1)^{F(i)} \left|{i}\right\rangle$$ The output qubit remains in the state $\frac{1}{\sqrt{2}}(\left|{0}\right\rangle - \left|{1}\right\rangle)$ and is henceforth disregarded as we focus on measurements of the first $n$ qubits. ## Final Hadamard Gates and Measurement To extract the global property of $F$, we apply Hadamard gates to the first $n$ qubits again. Applying $H^{\otimes n}$ to $\left|{\psi_1}\right\rangle$: $$H^{\otimes n} \left|{\psi_1}\right\rangle = H^{\otimes n} \left( \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} (-1)^{F(i)} \left|{i}\right\rangle \right) = \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} (-1)^{F(i)} H^{\otimes n} \left|{i}\right\rangle$$ Using the transformation of Hadamard gates on basis states $H^{\otimes n} \left|{i}\right\rangle = \frac{1}{\sqrt{2^n}} \sum_{j=0}^{2^n-1} (-1)^{i \cdot j} \left|{j}\right\rangle$, where $i \cdot j$ is the bitwise dot product of $i$ and $j$: $$H^{\otimes n} \left|{\psi_1}\right\rangle = \frac{1}{2^n} \sum_{i=0}^{2^n-1} (-1)^{F(i)} \sum_{j=0}^{2^n-1} (-1)^{i \cdot j} \left|{j}\right\rangle = \frac{1}{2^n} \sum_{j=0}^{2^n-1} \left( \sum_{i=0}^{2^n-1} (-1)^{F(i) + i \cdot j} \right) \left|{j}\right\rangle$$ We are interested in the probability of measuring $\left|{0}\right\rangle^{\otimes n}$, which corresponds to the coefficient of $\left|{j=0}\right\rangle$. For $j=0$, $i \cdot j = 0$, and $(-1)^{i \cdot j} = 1$. Thus, the coefficient of $\left|{0}\right\rangle^{\otimes n}$ is: $$C_0 = \frac{1}{2^n} \sum_{i=0}^{2^n-1} (-1)^{F(i)}$$ Analyzing $C_0$ for constant and balanced functions: - **Constant Function**: - If $F(i) = 0$ for all $i$: $C_0 = \frac{1}{2^n} \sum_{i=0}^{2^n-1} (-1)^{0} = \frac{1}{2^n} \sum_{i=0}^{2^n-1} 1 = \frac{2^n}{2^n} = 1$. - If $F(i) = 1$ for all $i$: $C_0 = \frac{1}{2^n} \sum_{i=0}^{2^n-1} (-1)^{1} = \frac{1}{2^n} \sum_{i=0}^{2^n-1} -1 = \frac{-2^n}{2^n} = -1$. In both constant cases, $|C_0|^2 = 1$. - **Balanced Function**: For a balanced function, exactly half of the $F(i)$ values are 0 and half are 1. Therefore, the sum contains $2^{n-1}$ terms of $+1$ and $2^{n-1}$ terms of $-1$. $$C_0 = \frac{1}{2^n} (2^{n-1} \cdot (+1) + 2^{n-1} \cdot (-1)) = \frac{1}{2^n} (2^{n-1} - 2^{n-1}) = 0$$ Thus, $|C_0|^2 = 0$. ## Measurement Outcome and Function Type ::: definition **Definition 1** (Measurement Outcome and Function Type in Deutsch's Algorithm). *The probability of measuring $\left|{0}\right\rangle^{\otimes n}$ is $P(\left|{0}\right\rangle^{\otimes n}) = |C_0|^2$.* - *If $P(\left|{0}\right\rangle^{\otimes n}) = 1$, the function $F$ is constant.* - *If $P(\left|{0}\right\rangle^{\otimes n}) = 0$, the function $F$ is balanced.* *By performing a single measurement of the first $n$ qubits, we can determine whether $F$ is constant or balanced with certainty.* ::: ## Complexity Analysis ::: remark **Remark 1** (Complexity Analysis of Deutsch's Algorithm). - ***Query Complexity**: Deutsch's algorithm requires only **one query** to the oracle $U_F$.* - ***Classical Complexity**: Classically, in the worst case, determining if $F$ is constant or balanced requires evaluating $F$ for up to $2^{n-1} + 1$ inputs.* *Deutsch's algorithm demonstrates a quantum advantage by solving the problem with a significantly reduced number of queries compared to classical methods. This highlights the power of quantum computation in reducing query complexity for specific computational tasks.* ::: ::: tcolorbox - Utilizes phase kick-back to extract global function properties. - Distinguishes between constant and balanced functions with a single query. - Demonstrates a quantum advantage in query complexity over classical algorithms for this problem. - Relies on superposition and interference to achieve its result. ::: # Discrete Fourier Transform (DFT) The Discrete Fourier Transform (DFT) is a fundamental mathematical tool with applications across various fields, including signal processing and quantum computing. It decomposes a discrete-time signal into its constituent frequencies, analogous to how a prism decomposes white light into its colors. In quantum algorithms, the DFT, particularly in its quantum form (QFT), plays a crucial role in algorithms like Shor's algorithm and quantum phase estimation. ## Definition of Discrete Fourier Transform ::: definition **Definition 2** (Discrete Fourier Transform (DFT)). *The DFT transforms a sequence of $N$ complex numbers $\{x_0, x_1, \ldots, x_{N-1}\}$ into another sequence of $N$ complex numbers $\{y_0, y_1, \ldots, y_{N-1}\}$ using the formula: $$y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2\pi i j k / N} \label{eq:dft_definition}$$ for $k = 0, 1, \ldots, N-1$. Here, $N$ is the size of the input sequence, and the factor $\frac{1}{\sqrt{N}}$ ensures that the transform is unitary, preserving the norm of the vector space.* ::: ## Application: Polynomial Multiplication One notable application of the DFT lies in efficient polynomial multiplication. Consider two polynomials $P(x) = \sum_{i=0}^{n} a_i x^i$ and $Q(x) = \sum_{j=0}^{m} b_j x^j$. Their product $R(x) = P(x)Q(x) = \sum_{k=0}^{n+m} c_k x^k$, where the coefficients $c_k$ are given by the convolution of the coefficients of $P(x)$ and $Q(x)$: $c_k = \sum_{i+j=k} a_i b_j$. Direct convolution calculation requires $O(nm)$ operations. However, by using the DFT, we can reduce the complexity to $O(N \log N)$, where $N \approx n+m$. The process involves these steps: 1. **Transform to Point-Value Representation**: Evaluate $P(x)$ and $Q(x)$ at $N \ge n+m+1$ points using the DFT. This converts the coefficient representation to a point-value representation. 2. **Point-wise Multiplication**: Multiply the point-values of $P(x)$ and $Q(x)$ at each of the $N$ points to obtain the point-values of the product $R(x)$. 3. **Inverse Transform to Coefficient Representation**: Use the inverse DFT to interpolate the point-value representation of $R(x)$ back to its coefficient representation. The efficiency is achieved by using the Fast Fourier Transform (FFT), an algorithm that computes the DFT in $O(N \log N)$ time. ## DFT in Quantum Computing and Operator Estimation In quantum computing, the Quantum Fourier Transform (QFT) is the quantum analogue of the DFT, operating on quantum states. It is a crucial subroutine in various quantum algorithms, including: - **Shor's Algorithm**: For integer factorization, where QFT is used to find the period of a function. - **Quantum Phase Estimation**: For estimating the eigenvalues (phases) of unitary operators, a fundamental task in quantum simulation and algorithm design. The QFT allows for efficient manipulation of amplitudes in the frequency domain, enabling quantum algorithms to solve problems intractable for classical computers. ## DFT of Computational Basis States ::: definition **Definition 3** (DFT of Computational Basis States). *Consider the action of the DFT on computational basis states $\left|{j}\right\rangle$ in an $n$-qubit system, where $j \in \{0, 1, \ldots, N-1\}$ and $N = 2^n$. Applying the DFT to a basis state $\left|{j}\right\rangle$ yields: $$DFT \left|{j}\right\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i j k / N} \left|{k}\right\rangle \label{eq:dft_basis_state}$$ This transformation creates a superposition of all basis states $\left|{k}\right\rangle$, with coefficients determined by the complex exponential term.* ::: ## Examples of DFT for Small N ### DFT for N=4 (Two Qubits) Let $N=4$ (two qubits). We examine the DFT of basis states $\left|{00}\right\rangle = \left|{0}\right\rangle$ and $\left|{01}\right\rangle = \left|{1}\right\rangle$. #### DFT of $\left|{00}\right\rangle$ ::: example **Example 1** (DFT of $\left|{00}\right\rangle$ for N=4). *$$\begin{aligned} DFT \left|{00}\right\rangle &= \frac{1}{\sqrt{4}} \sum_{k=0}^{3} e^{2\pi i \cdot 0 \cdot k / 4} \left|{k}\right\rangle \\ &= \frac{1}{2} \sum_{k=0}^{3} e^{0} \left|{k}\right\rangle \\ &= \frac{1}{2} (\left|{00}\right\rangle + \left|{01}\right\rangle + \left|{10}\right\rangle + \left|{11}\right\rangle)\end{aligned}$$ The DFT of $\left|{00}\right\rangle$ results in an equal superposition of all two-qubit basis states.* ::: #### DFT of $\left|{01}\right\rangle$ ::: example **Example 2** (DFT of $\left|{01}\right\rangle$ for N=4). *$$\begin{aligned} DFT \left|{01}\right\rangle &= \frac{1}{2} \sum_{k=0}^{3} e^{2\pi i \cdot 1 \cdot k / 4} \left|{k}\right\rangle \\ &= \frac{1}{2} \left( e^{2\pi i \cdot 1 \cdot 0 / 4} \left|{00}\right\rangle + e^{2\pi i \cdot 1 \cdot 1 / 4} \left|{01}\right\rangle + e^{2\pi i \cdot 1 \cdot 2 / 4} \left|{10}\right\rangle + e^{2\pi i \cdot 1 \cdot 3 / 4} \left|{11}\right\rangle \right) \\ &= \frac{1}{2} \left( e^{0} \left|{00}\right\rangle + e^{i\pi/2} \left|{01}\right\rangle + e^{i\pi} \left|{10}\right\rangle + e^{3i\pi/2} \left|{11}\right\rangle \right) \\ &= \frac{1}{2} \left( \left|{00}\right\rangle + i \left|{01}\right\rangle - \left|{10}\right\rangle - i \left|{11}\right\rangle \right) \\ &= \frac{1}{2} (\left|{0}\right\rangle - \left|{1}\right\rangle) \otimes (\left|{0}\right\rangle + i\left|{1}\right\rangle)\end{aligned}$$* ::: ### DFT for N=2 (One Qubit) and Hadamard Equivalence For $N=2$ (one qubit), we examine the DFT of basis states $\left|{0}\right\rangle$ and $\left|{1}\right\rangle$. #### DFT of $\left|{0}\right\rangle$ ::: example **Example 3** (DFT of $\left|{0}\right\rangle$ for N=2). *$$\begin{aligned} DFT \left|{0}\right\rangle &= \frac{1}{\sqrt{2}} \sum_{k=0}^{1} e^{2\pi i \cdot 0 \cdot k / 2} \left|{k}\right\rangle \\ &= \frac{1}{\sqrt{2}} (e^{0} \left|{0}\right\rangle + e^{0} \left|{1}\right\rangle) \\ &= \frac{1}{\sqrt{2}} (\left|{0}\right\rangle + \left|{1}\right\rangle) = H\left|{0}\right\rangle\end{aligned}$$* ::: #### DFT of $\left|{1}\right\rangle$ ::: example **Example 4** (DFT of $\left|{1}\right\rangle$ for N=2). *$$\begin{aligned} DFT \left|{1}\right\rangle &= \frac{1}{\sqrt{2}} \sum_{k=0}^{1} e^{2\pi i \cdot 1 \cdot k / 2} \left|{k}\right\rangle \\ &= \frac{1}{\sqrt{2}} (e^{0} \left|{0}\right\rangle + e^{2\pi i / 2} \left|{1}\right\rangle) \\ &= \frac{1}{\sqrt{2}} (\left|{0}\right\rangle + e^{i\pi} \left|{1}\right\rangle) \\ &= \frac{1}{\sqrt{2}} (\left|{0}\right\rangle - \left|{1}\right\rangle) = H\left|{1}\right\rangle\end{aligned}$$* ::: ::: remark **Remark 2** (Hadamard Equivalence to DFT for N=2). *For a single qubit ($N=2$), the DFT is mathematically equivalent to the Hadamard transform $H$. This establishes the Hadamard gate as a specific instance of the DFT in a two-dimensional Hilbert space.* ::: ::: tcolorbox - **Transforms Time Domain to Frequency Domain**: Decomposes a signal into its frequency components. - **Unitary Transformation**: Preserves the norm in vector spaces, crucial for quantum mechanics. - **Efficient Polynomial Multiplication**: Reduces complexity from $O(n^2)$ to $O(n \log n)$ using FFT. - **Foundation for QFT**: Classical DFT is the basis for the Quantum Fourier Transform, essential in quantum algorithms. - **Hadamard as a Special Case**: For a single qubit, DFT is equivalent to the Hadamard transform. ::: # Conclusion In this lecture, we investigated a quantum algorithm that effectively utilizes phase kick-back, focusing on Deutsch's algorithm as a prime example for differentiating between constant and balanced functions. We demonstrated the quantum advantage in query complexity offered by such algorithms for specific problems. Subsequently, we introduced the Discrete Fourier Transform (DFT), elucidating its definition, its application in efficient polynomial multiplication, and its critical role in quantum computing, particularly as the classical counterpart to the Quantum Fourier Transform. We also highlighted the significant observation that the Hadamard transform is a specific instance of the DFT in the single-qubit scenario. Looking ahead, future lectures will delve deeper into the Quantum Fourier Transform algorithm, including its circuit implementation and its pivotal applications in quantum phase estimation and Shor's algorithm. Further exploration into the entanglement characteristics of these quantum circuits and the analysis of function properties beyond the constant versus balanced dichotomy will also be considered, providing a more comprehensive understanding of quantum algorithms and their capabilities. []{#sec:quantum-algorithm-and-phase-kick-back label="sec:quantum-algorithm-and-phase-kick-back"}