New answers tagged

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
0 votes

Quantum Phase Estimation answers distribution

Doublecheck your inverse QFT circuit. I get a distribution similar to yours if I put QFT instead of its inverse in the second part of the phase estimation algorithm. If the correct inverse QFT is used,...
Vladimir Lysikov's user avatar
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
0 votes

Question on efficiency of HOBO Quadratization and other depth reducing techniques

Quadratization is often used classically. On a quantum variational algorithm, like QAOA would be not so easy to put in practice, since it would add constraints and therefore penalties in the cost. ...
Andrea's user avatar
  • 1
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

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
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
0 votes

Implementing a Quantum Recurrent Neural Network

Your implementation of a Quantum Recurrent Neural Network (QRNN) using PyTorch and PennyLane is a good start but needs some adjustments and completion. Let's go through the code to identify areas for ...
Sadegh Bendokht'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

Top 50 recent answers are included