Consider a Hilbert space of dimension $p$ where $p$ is a prime number. Quantum Fourier transform (QFT) in this space is defined as $$ |j\rangle \rightarrow \frac{1}{\sqrt{p}} \sum_{k=0}^{p-1}e^{\frac{2\pi i j k}{p}} |k\rangle. $$ How to construct a quantum circuit that performs this transformation? The standard circuit for QFT requires the dimension to be a power of 2. That's no longer possible when $p$ is prime.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ quantumcomputing.stackexchange.com $\endgroup$– hftCommented Jan 23 at 21:57
-
$\begingroup$ Why would you want to do that? This circuit will not be efficient, unless the dimension is small. The point of the QFT is that is scales up to large dimensions which factor into a product of small primes. $\endgroup$– Norbert SchuchCommented Jan 23 at 22:51
-
$\begingroup$ see Bocharov A, Roetteler M, Svore KM. Factoring with qutrits: Shor's algorithm on ternary and metaplectic quantum architectures. Physical Review A. 2017 Jul 5;96(1):012306 for a related discussion. $\endgroup$– ZeroTheHeroCommented Jan 24 at 1:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The point of the QFT is that if your dimension is $N=2^n$, there is a way to build a circuit for the QFT which is efficient (polynomial-time) in $n$, rather than $N$.
This advantage is gone when you want to design the QFT for a single large prime. Leaving aside that you will need to figure out how to decompose such a circuit into qubits, it will generally be complicated -- just as the QFT contains Hadamards, that is, one-qubit QFTs, it will contain the QFT for the prime under consideration.
On the other hand, the design principle of the QFT for $n$ qubits directly generalizes to $N=p_1^{n_1}p_2^{n_2}\cdots$ which is efficient as long as the involved (prime) factors $p_i$ are small.
answered Jan 23 at 22:54