Quantum Fourier Transform (QFT)¶
The quantum Fourier transform is a core component of many quantum algorithms — such as phase estimation and Shor’s factoring — provided ready-made in the algorithm library.
Overview¶
Operator |
Operation |
Unitarity class |
|---|---|---|
|
Quantum Fourier transform |
BaseOperator |
|
Inverse quantum Fourier transform |
BaseOperator |
Mathematical Definition¶
The quantum Fourier transform is defined as:
The inverse quantum Fourier transform:
—
QFT¶
- class pysparq.QFT¶
Quantum Fourier Transform on a register.
Applies the QFT to transform between computational and Fourier bases. Commonly used in phase estimation and Shor’s algorithm.
- Parameters:
reg_name – Name of the register to transform (str) or register ID (int).
Example
QFT(“data”)(state) # Apply QFT # … computation … InverseQFT(“data”)(state) # Apply inverse QFT
- clear_control_all_ones(self: pysparq._core.QFT) None¶
Clear all control conditions of the specified type.
- clear_control_by_bit(self: pysparq._core.QFT) None¶
Clear all control conditions of the specified type.
- clear_control_by_value(self: pysparq._core.QFT) None¶
Clear all control conditions of the specified type.
- clear_control_nonzeros(self: pysparq._core.QFT) None¶
Clear all control conditions of the specified type.
- property condition_variable_all_ones¶
- property condition_variable_by_bit¶
- property condition_variable_by_value¶
- property condition_variable_nonzeros¶
- conditioned_by_all_ones(*args, **kwargs)¶
Overloaded function.
conditioned_by_all_ones(self: pysparq._core.QFT, cond: str) -> pysparq._core.QFT
Condition this operation on registers where all bits are 1.
Calling this method replaces prior all-ones conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
conditioned_by_all_ones(self: pysparq._core.QFT, conds: collections.abc.Sequence[str]) -> pysparq._core.QFT
Condition this operation on registers where all bits are 1.
Calling this method replaces prior all-ones conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
conditioned_by_all_ones(self: pysparq._core.QFT, cond: typing.SupportsInt | typing.SupportsIndex) -> pysparq._core.QFT
Condition this operation on registers where all bits are 1.
Calling this method replaces prior all-ones conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
conditioned_by_all_ones(self: pysparq._core.QFT, conds: collections.abc.Sequence[typing.SupportsInt | typing.SupportsIndex]) -> pysparq._core.QFT
Condition this operation on registers where all bits are 1.
Calling this method replaces prior all-ones conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
- conditioned_by_bit(*args, **kwargs)¶
Overloaded function.
conditioned_by_bit(self: pysparq._core.QFT, cond: str, pos: typing.SupportsInt | typing.SupportsIndex) -> pysparq._core.QFT
Condition this operation on a specific bit position.
Calling this method replaces prior bit conditions. Pass the list-of-pairs overload to require several bits simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Bit position to check (0-indexed).
conds – List of (register, position) pairs.
- Returns:
Self, for method chaining.
conditioned_by_bit(self: pysparq._core.QFT, conds: collections.abc.Sequence[tuple[str, typing.SupportsInt | typing.SupportsIndex]]) -> pysparq._core.QFT
Condition this operation on a specific bit position.
Calling this method replaces prior bit conditions. Pass the list-of-pairs overload to require several bits simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Bit position to check (0-indexed).
conds – List of (register, position) pairs.
- Returns:
Self, for method chaining.
conditioned_by_bit(self: pysparq._core.QFT, cond: typing.SupportsInt | typing.SupportsIndex, pos: typing.SupportsInt | typing.SupportsIndex) -> pysparq._core.QFT
Condition this operation on a specific bit position.
Calling this method replaces prior bit conditions. Pass the list-of-pairs overload to require several bits simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Bit position to check (0-indexed).
conds – List of (register, position) pairs.
- Returns:
Self, for method chaining.
conditioned_by_bit(self: pysparq._core.QFT, conds: collections.abc.Sequence[tuple[typing.SupportsInt | typing.SupportsIndex, typing.SupportsInt | typing.SupportsIndex]]) -> pysparq._core.QFT
Condition this operation on a specific bit position.
Calling this method replaces prior bit conditions. Pass the list-of-pairs overload to require several bits simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Bit position to check (0-indexed).
conds – List of (register, position) pairs.
- Returns:
Self, for method chaining.
- conditioned_by_nonzeros(*args, **kwargs)¶
Overloaded function.
conditioned_by_nonzeros(self: pysparq._core.QFT, cond: str) -> pysparq._core.QFT
Condition this operation on registers with nonzero values.
Calling this method replaces prior nonzero-register conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
Example
op.conditioned_by_nonzeros(‘control_reg’)(state)
conditioned_by_nonzeros(self: pysparq._core.QFT, conds: collections.abc.Sequence[str]) -> pysparq._core.QFT
Condition this operation on registers with nonzero values.
Calling this method replaces prior nonzero-register conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
Example
op.conditioned_by_nonzeros(‘control_reg’)(state)
conditioned_by_nonzeros(self: pysparq._core.QFT, cond: typing.SupportsInt | typing.SupportsIndex) -> pysparq._core.QFT
Condition this operation on registers with nonzero values.
Calling this method replaces prior nonzero-register conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
Example
op.conditioned_by_nonzeros(‘control_reg’)(state)
conditioned_by_nonzeros(self: pysparq._core.QFT, conds: collections.abc.Sequence[typing.SupportsInt | typing.SupportsIndex]) -> pysparq._core.QFT
Condition this operation on registers with nonzero values.
Calling this method replaces prior nonzero-register conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
Example
op.conditioned_by_nonzeros(‘control_reg’)(state)
- conditioned_by_value(*args, **kwargs)¶
Overloaded function.
conditioned_by_value(self: pysparq._core.QFT, cond: str, pos: typing.SupportsInt | typing.SupportsIndex) -> pysparq._core.QFT
Condition this operation on registers holding a specific value.
Calling this method replaces prior value conditions. Pass the list-of-pairs overload to require several values simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Value to match.
conds – List of (register, value) pairs.
- Returns:
Self, for method chaining.
conditioned_by_value(self: pysparq._core.QFT, conds: collections.abc.Sequence[tuple[str, typing.SupportsInt | typing.SupportsIndex]]) -> pysparq._core.QFT
Condition this operation on registers holding a specific value.
Calling this method replaces prior value conditions. Pass the list-of-pairs overload to require several values simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Value to match.
conds – List of (register, value) pairs.
- Returns:
Self, for method chaining.
conditioned_by_value(self: pysparq._core.QFT, cond: typing.SupportsInt | typing.SupportsIndex, pos: typing.SupportsInt | typing.SupportsIndex) -> pysparq._core.QFT
Condition this operation on registers holding a specific value.
Calling this method replaces prior value conditions. Pass the list-of-pairs overload to require several values simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Value to match.
conds – List of (register, value) pairs.
- Returns:
Self, for method chaining.
conditioned_by_value(self: pysparq._core.QFT, conds: collections.abc.Sequence[tuple[typing.SupportsInt | typing.SupportsIndex, typing.SupportsInt | typing.SupportsIndex]]) -> pysparq._core.QFT
Condition this operation on registers holding a specific value.
Calling this method replaces prior value conditions. Pass the list-of-pairs overload to require several values simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Value to match.
conds – List of (register, value) pairs.
- Returns:
Self, for method chaining.
- dag(self: pysparq._core.QFT, state: pysparq._core.SparseState) None¶
Apply the adjoint (inverse) of this operation.
- Parameters:
state – The quantum state to operate on.
Note: Only available for self-adjoint operators.
Operation: Performs the quantum Fourier transform on an integer register
Type constraints: UnsignedInteger or SignedInteger
Bit constraints: The register size determines the transform dimension
import pysparq as ps
ps.System.clear()
# 4-bit register
ps.System.add_register("q", ps.UnsignedInteger, 4)
state = ps.SparseState()
# Initialize to the basis state |1⟩
ps.Init_Unsafe("q", 1)(state)
print("Initial state:")
ps.pprint(state)
# |q=1⟩ : (1+0j)
# Apply the QFT
op = ps.QFT("q")
op(state)
print("\nAfter QFT:")
ps.pprint(state)
# Produces a superposition with uniformly distributed phases
# Undo (inverse transform)
op.dag(state)
InverseQFT¶
- class pysparq.InverseQFT¶
Inverse Quantum Fourier Transform on a register.
Applies the inverse QFT to transform from Fourier basis back to computational basis.
- Parameters:
reg_name – Name of the register (str) or register ID (int).
- clear_control_all_ones(self: pysparq._core.InverseQFT) None¶
Clear all control conditions of the specified type.
- clear_control_by_bit(self: pysparq._core.InverseQFT) None¶
Clear all control conditions of the specified type.
- clear_control_by_value(self: pysparq._core.InverseQFT) None¶
Clear all control conditions of the specified type.
- clear_control_nonzeros(self: pysparq._core.InverseQFT) None¶
Clear all control conditions of the specified type.
- property condition_variable_all_ones¶
- property condition_variable_by_bit¶
- property condition_variable_by_value¶
- property condition_variable_nonzeros¶
- conditioned_by_all_ones(*args, **kwargs)¶
Overloaded function.
conditioned_by_all_ones(self: pysparq._core.InverseQFT, cond: str) -> pysparq._core.InverseQFT
Condition this operation on registers where all bits are 1.
Calling this method replaces prior all-ones conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
conditioned_by_all_ones(self: pysparq._core.InverseQFT, conds: collections.abc.Sequence[str]) -> pysparq._core.InverseQFT
Condition this operation on registers where all bits are 1.
Calling this method replaces prior all-ones conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
conditioned_by_all_ones(self: pysparq._core.InverseQFT, cond: typing.SupportsInt | typing.SupportsIndex) -> pysparq._core.InverseQFT
Condition this operation on registers where all bits are 1.
Calling this method replaces prior all-ones conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
conditioned_by_all_ones(self: pysparq._core.InverseQFT, conds: collections.abc.Sequence[typing.SupportsInt | typing.SupportsIndex]) -> pysparq._core.InverseQFT
Condition this operation on registers where all bits are 1.
Calling this method replaces prior all-ones conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
- conditioned_by_bit(*args, **kwargs)¶
Overloaded function.
conditioned_by_bit(self: pysparq._core.InverseQFT, cond: str, pos: typing.SupportsInt | typing.SupportsIndex) -> pysparq._core.InverseQFT
Condition this operation on a specific bit position.
Calling this method replaces prior bit conditions. Pass the list-of-pairs overload to require several bits simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Bit position to check (0-indexed).
conds – List of (register, position) pairs.
- Returns:
Self, for method chaining.
conditioned_by_bit(self: pysparq._core.InverseQFT, conds: collections.abc.Sequence[tuple[str, typing.SupportsInt | typing.SupportsIndex]]) -> pysparq._core.InverseQFT
Condition this operation on a specific bit position.
Calling this method replaces prior bit conditions. Pass the list-of-pairs overload to require several bits simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Bit position to check (0-indexed).
conds – List of (register, position) pairs.
- Returns:
Self, for method chaining.
conditioned_by_bit(self: pysparq._core.InverseQFT, cond: typing.SupportsInt | typing.SupportsIndex, pos: typing.SupportsInt | typing.SupportsIndex) -> pysparq._core.InverseQFT
Condition this operation on a specific bit position.
Calling this method replaces prior bit conditions. Pass the list-of-pairs overload to require several bits simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Bit position to check (0-indexed).
conds – List of (register, position) pairs.
- Returns:
Self, for method chaining.
conditioned_by_bit(self: pysparq._core.InverseQFT, conds: collections.abc.Sequence[tuple[typing.SupportsInt | typing.SupportsIndex, typing.SupportsInt | typing.SupportsIndex]]) -> pysparq._core.InverseQFT
Condition this operation on a specific bit position.
Calling this method replaces prior bit conditions. Pass the list-of-pairs overload to require several bits simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Bit position to check (0-indexed).
conds – List of (register, position) pairs.
- Returns:
Self, for method chaining.
- conditioned_by_nonzeros(*args, **kwargs)¶
Overloaded function.
conditioned_by_nonzeros(self: pysparq._core.InverseQFT, cond: str) -> pysparq._core.InverseQFT
Condition this operation on registers with nonzero values.
Calling this method replaces prior nonzero-register conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
Example
op.conditioned_by_nonzeros(‘control_reg’)(state)
conditioned_by_nonzeros(self: pysparq._core.InverseQFT, conds: collections.abc.Sequence[str]) -> pysparq._core.InverseQFT
Condition this operation on registers with nonzero values.
Calling this method replaces prior nonzero-register conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
Example
op.conditioned_by_nonzeros(‘control_reg’)(state)
conditioned_by_nonzeros(self: pysparq._core.InverseQFT, cond: typing.SupportsInt | typing.SupportsIndex) -> pysparq._core.InverseQFT
Condition this operation on registers with nonzero values.
Calling this method replaces prior nonzero-register conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
Example
op.conditioned_by_nonzeros(‘control_reg’)(state)
conditioned_by_nonzeros(self: pysparq._core.InverseQFT, conds: collections.abc.Sequence[typing.SupportsInt | typing.SupportsIndex]) -> pysparq._core.InverseQFT
Condition this operation on registers with nonzero values.
Calling this method replaces prior nonzero-register conditions. Pass the list overload to require several registers simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int) to condition on.
conds – List of register names or IDs for multi-condition.
- Returns:
Self, for method chaining.
Example
op.conditioned_by_nonzeros(‘control_reg’)(state)
- conditioned_by_value(*args, **kwargs)¶
Overloaded function.
conditioned_by_value(self: pysparq._core.InverseQFT, cond: str, pos: typing.SupportsInt | typing.SupportsIndex) -> pysparq._core.InverseQFT
Condition this operation on registers holding a specific value.
Calling this method replaces prior value conditions. Pass the list-of-pairs overload to require several values simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Value to match.
conds – List of (register, value) pairs.
- Returns:
Self, for method chaining.
conditioned_by_value(self: pysparq._core.InverseQFT, conds: collections.abc.Sequence[tuple[str, typing.SupportsInt | typing.SupportsIndex]]) -> pysparq._core.InverseQFT
Condition this operation on registers holding a specific value.
Calling this method replaces prior value conditions. Pass the list-of-pairs overload to require several values simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Value to match.
conds – List of (register, value) pairs.
- Returns:
Self, for method chaining.
conditioned_by_value(self: pysparq._core.InverseQFT, cond: typing.SupportsInt | typing.SupportsIndex, pos: typing.SupportsInt | typing.SupportsIndex) -> pysparq._core.InverseQFT
Condition this operation on registers holding a specific value.
Calling this method replaces prior value conditions. Pass the list-of-pairs overload to require several values simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Value to match.
conds – List of (register, value) pairs.
- Returns:
Self, for method chaining.
conditioned_by_value(self: pysparq._core.InverseQFT, conds: collections.abc.Sequence[tuple[typing.SupportsInt | typing.SupportsIndex, typing.SupportsInt | typing.SupportsIndex]]) -> pysparq._core.InverseQFT
Condition this operation on registers holding a specific value.
Calling this method replaces prior value conditions. Pass the list-of-pairs overload to require several values simultaneously; conditions of different kinds are combined with logical AND.
- Parameters:
cond – Register name (str) or ID (int).
pos – Value to match.
conds – List of (register, value) pairs.
- Returns:
Self, for method chaining.
Operation: Performs the inverse quantum Fourier transform on an integer register
Purpose: Undo a QFT or extract phase information
ps.System.clear()
ps.System.add_register("q", ps.UnsignedInteger, 4)
state = ps.SparseState()
# Create a superposition
ps.Hadamard_Int_Full("q")(state)
# Apply the inverse QFT
ps.InverseQFT("q")(state)
# The inverse QFT and the QFT are inverses of each other
ps.QFT("q")(state)
—
Use Cases¶
Period Finding (Shor’s Algorithm)¶
import pysparq as ps
import numpy as np
ps.System.clear()
# Phase register
n_bits = 8
ps.System.add_register("phase", ps.UnsignedInteger, n_bits)
state = ps.SparseState()
# Simulate a phase estimation result (assume period r = 5)
# |phase⟩ contains periodic phase information
ps.Hadamard_Int_Full("phase")(state)
# Apply the inverse QFT to extract the period
ps.InverseQFT("phase")(state)
# Measure the phase register to determine the period
# ...
Phase Estimation¶
# Assume a phase estimation circuit already exists
# The inverse QFT converts phase information into the computational basis
# 1. Prepare the initial state
ps.Hadamard_Int_Full("estimate")(state)
# 2. Apply the controlled-unitary operation
# controlled_U(...)(state)
# 3. Extract the phase with the inverse QFT
ps.InverseQFT("estimate")(state)
# 4. Measure to obtain the phase estimate
# ...
Quantum Signal Processing¶
# The QFT is used for frequency-domain analysis
ps.System.add_register("signal", ps.UnsignedInteger, 16)
state = ps.SparseState()
# Load the signal data...
# Transform to the frequency domain
ps.QFT("signal")(state)
# Frequency-domain processing...
# Transform back to the time domain
ps.InverseQFT("signal")(state)
Performance Considerations¶
Number of basis states: When the QFT acts on a superposition, it produces \(2^n\) basis states
Memory limits: For large n (e.g. n > 20), memory problems may arise
Sparse optimization: PySparQ stores only the basis states with nonzero amplitudes, which can be efficient for certain inputs
Note
For superpositions that are not complete, the sparse implementation of the QFT can be more efficient than full-state simulation.
Practical Examples¶
Full QFT + InverseQFT Cycle¶
import pysparq as ps
import numpy as np
ps.System.clear()
n = 3
ps.System.add_register("q", ps.UnsignedInteger, n)
state = ps.SparseState()
# Initial value
initial_value = 5
ps.Init_Unsafe("q", initial_value)(state)
print("Initial state:")
ps.pprint(state)
# QFT
ps.QFT("q")(state)
print("\nAfter QFT:")
ps.pprint(state)
# InverseQFT
ps.InverseQFT("q")(state)
print("\nAfter InverseQFT:")
ps.pprint(state)
# Restored to |q=5⟩