Skip to main content
Quantum Computing

Return to Question

added 186 characters in body
Source Link
Mark Spinelli
Mark Spinelli
  • 14.4k
  • 2
  • 24
  • 78

The (classical) lower bound on Fast Fourier transform is still open question. IheThe complexity of $\mathcal{O}(Nlog(N))$$\mathcal{O}(N\log(N))$ (due to Cooley-TuckeyCooley-Tukey) is not shownknown to be optimal. (Here, N$N$ is the vector size.)

In the Quantumquantum counterpart, there is an $\mathcal{O}(n^2)$ algorithm (duedue to Coppersmith Coppersmith, 1994, and also Deutsch (1994)unpublished). Here n$n$ is number of qubits.

Is this result known to be optimal?

There has been some approximate QFT algorithm that do better [see- see, $\mathcal{O}(nlog(n))$$\mathcal{O}(n\log(n))$ due to HalesHales,2002] 2002. But, I am restricting to exact algorithms only for this question.

The (classical) lower bound on Fast Fourier transform is still open question. Ihe complexity of $\mathcal{O}(Nlog(N))$ (due to Cooley-Tuckey) is not shown to be optimal. (Here, N is the vector size.)

In the Quantum counterpart, there is $\mathcal{O}(n^2)$ algorithm (due to Coppersmith (1994)). Here n is number of qubits.

Is this result known to be optimal?

There has been some approximate QFT algorithm that do better [see, $\mathcal{O}(nlog(n))$ due to Hales,2002]. But, I am restricting to exact algorithms only for this question.

The (classical) lower bound on Fast Fourier transform is still open question. The complexity of $\mathcal{O}(N\log(N))$ (due to Cooley-Tukey) is not known to be optimal. (Here, $N$ is the vector size.)

In the quantum counterpart, there is an $\mathcal{O}(n^2)$ algorithm due to Coppersmith, 1994, and also Deutsch (unpublished). Here $n$ is number of qubits.

Is this result known to be optimal?

There has been some approximate QFT algorithm that do better - see, $\mathcal{O}(n\log(n))$ due to Hales, 2002. But, I am restricting to exact algorithms only for this question.

edited title
Link
glS ♦
glS ♦
  • 26.9k
  • 6
  • 35
  • 121

Lower bound for Quantum Is the $\mathcal O(n^2)$ cost of the quantum Fourier Tranformtransform (QFT) known to be optimal?

Source Link
Manish Kumar
Manish Kumar
  • 913
  • 1
  • 6
  • 19

Lower bound for Quantum Fourier Tranform (QFT)

The (classical) lower bound on Fast Fourier transform is still open question. Ihe complexity of $\mathcal{O}(Nlog(N))$ (due to Cooley-Tuckey) is not shown to be optimal. (Here, N is the vector size.)

In the Quantum counterpart, there is $\mathcal{O}(n^2)$ algorithm (due to Coppersmith (1994)). Here n is number of qubits.

Is this result known to be optimal?

There has been some approximate QFT algorithm that do better [see, $\mathcal{O}(nlog(n))$ due to Hales,2002]. But, I am restricting to exact algorithms only for this question.