In paper The Quantum Fourier Transform Has Small Entanglement the authors showed that strong entanglement of qubits caused by QFT comes mainly from ordering the qubits. QFT itself prepares only weak entanglement:

We have shown that the maximum-entanglement property of the standard QFT mainly comes from the trivial bit-reversal operation, while the core part of QFT has Schmidt coefficients decaying exponentially quickly.

As a result, it is possible to simulate QFT on classical computer with complexity $O(n)$, where $n$ is number of qubits involved:

Thus simulating the QFT on a classical computer with high precision can be done in $O(n)$ time if a low-bond-dimension MPS representation of the initial state is given.

As QFT is part of many algorithms promising exponential speed-up over classical computers, like Shor or HHL algorithm, I was wondering whether results of the paper would have impact on classical simulation of mentioned algorithms. Based on second quote from the paper, I feel that to reach the speed-up we still need to prepare superpositions the QFT acts on (e.g. results of modular exponentiation in Shor algorithm) on quantum computer.

Could anybody shed more light on meaning of the paper results for quantum algorithms simulation on classical computers?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.