6 votes

Anything in between quadratic and exponential speedups?

A subexponential-time quantum algorithm for the dihedral hidden subgroup problem by Kuperberg. Constructing elliptic curve isogenies in quantum subexponential time by Childs, Jao, and Soukharev. A ...
Egretta.Thula's user avatar
6 votes
Accepted

Is the $\mathcal O(n^2)$ cost of the quantum Fourier transform (QFT) known to be optimal?

Here's an $O(n \lg^2 n)$ construction of the QFT based on merging groups of phasing operations into multiplications: You can verify the circuit works in Quirk. The "reverse" gate reverses ...
Craig Gidney's user avatar
  • 34.9k
4 votes
Accepted

confusion on the LCU method regarding the normalization

You're correct, LCU will prepare a state proportional to $A|\psi\rangle$, with whatever renormalization is required for that to be true. Its possible that the normalization factor was omitted because ...
forky40's user avatar
  • 6,348
4 votes

Is the $\mathcal O(n^2)$ cost of the quantum Fourier transform (QFT) known to be optimal?

I think this is a good question. But the answers might depend on the precise meaning behind "exact" as even Coppersmith's improvement provides an approximate algorithm. For example, Shor ...
Mark Spinelli's user avatar
3 votes

How does the complexity of extracting eigenvalues via quantum phase estimation compare with the classical one?

Even eigenvalue sampling itself is BQP-complete; thus, a quantum computer most likely provides an exponential speedup to finding such eigenvalues (under the standard assumption that BPP$\subsetneq$BQP)...
Mark Spinelli's user avatar
3 votes

Algorithm to reveal properties of a random quantum permutation gate

To answer 1: Find the smallest Hamming code that acts on $n$ or more bits. Write out its parity-check matrix. Remove as many columns as you need (doesn't matter which ones) so that it only has $n$ ...
DaftWullie's user avatar
  • 56.8k
2 votes
Accepted

Optimal dependency of HHL (or any QLSP) algorithm on condition number $\kappa$

What is the best known lower bound on condition number? Costa et. la.[1] use the discrete adiabatic theorem to develop a quantum algorithm for solving linear systems with complexity strictly linear ...
Egretta.Thula's user avatar
1 vote
Accepted

How can I use Quantum Shanon Decomposition for any $N \times N$ matrix?

Given that the matrix that you are trying to implement is non-unitary, the quantum Shannon decomposition (originally introduced in this paper by Shende, Bullock and Markov) is not a useful approach. ...
bm442's user avatar
  • 1,027

Only top scored, non community-wiki answers of a minimum length are eligible