Juan Bermejo Vega
  • Member for 10 years, 2 months
  • Last seen more than 2 years ago
Quantum algorithms based on transforms other than Fourier transforms
Accepted answer
16 votes

I would like to add some more references to Scott's comment: Indeed, Clebsch-Gordan transforms (that you can think of as multi-register quantum Fourier transforms) are a useful tool in the design of ...

View answer
Are there any cases where quantum has given insight for classical algorithms?
11 votes

There is at least one example that I can remember, but there are probably more that I am not aware of. Recently, Maarten Van den Nest and Wolfgang Dürr found a new classical algorithm (arXiv:1304....

View answer
Determinant modulo m
11 votes

To solve this problem there is a fast deterministic algorithm based on Smith normal forms whose worst-case complexity is upper-bounded by the cost of matrix-multiplication over the integers modulo $m$....

View answer
Applications of HHL's algorithm for solving linear equations
Accepted answer
9 votes

If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical ...

View answer
1-way Quantum Finite Automata Example Question
Accepted answer
5 votes

For sure, the automata performs a measurement after reading each symbol "a" and applying an associated unitary $V_a$. Yet, it is not really meaningful to compute the amplitudes of the state to be ...

View answer
What papers should everyone read?
5 votes

A Simple Proof that Toffoli and Hadamard are Quantum Universal, D. Aharonov summarising a result found by Yaoyun Shi. Because it is a simple, well written, 4 pages paper which makes you think and ...

View answer
Difficulty in understanding the quantum algorithm for the abelian hidden subgroup problem
4 votes

This classical post-processing exploits several non-trivial group theoretical properties of Abelian groups. I wrote a didactic explanation of how this classical algorithm works here [1]; other good ...

View answer
Complexity of Membership-Testing for finite abelian groups
Accepted answer
4 votes

After some time, I managed to find a perhaps not-optimal but simple algorithm that proves that the complexity of the problem is polynomial. Algorithm (a) Compute a generating-set of the ...

View answer
Optimal measurement for MUBs
4 votes

It seems that this problem in full-generality is though. These two references might be helpful to you. Here [1] the pure-state discrimination of MUBs is studied in a cryptographic set-up. The ...

View answer
What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs?
4 votes

Correct me if I am wrong, but it seems to me that you are interested in the class BQP/qpoly. Definition from Complexity Zoo: "The class of problems solvable by a BQP machine that receives a quantum ...

View answer
Determinant of a generalized Vandermonde matrix
3 votes

It is important that, in the definition you provide, the matrix lives in a finite field, say $\mathbb{Z}_m$ where $m$ is prime. This allows you to use Euler's theorem to compute the double-...

View answer
Complexity of determinant of k-minors
Accepted answer
2 votes

There are clasical algorithms [1], [2], [3] to compute the determinant of a $k\times k$ matrix using $O(k^\omega)$ floating-point operations, where $O(k^\omega)$ is the number of operations that you ...

View answer
What videos should everybody watch?
2 votes

The archive of recorded seminars of the Perimeter Institute is both useful and entertaining. The Qubit Lab is a Youtube channel that explains advanced topics on quantum information and computation ...

View answer
Real world applications of quantum computing (except for security)
2 votes

Visioning is both dangerous and polemic in this field, so we should be cautious with this topic. Yet some Q-algorithms with polynomial speed-ups have interesting potential applications. It is known ...

View answer
Software package for decomposing quantum circuits
2 votes

In addition to the previous answers, there is a package that computes Fourier transforms for solvable non-commutative groups based on this algorithm. The software has a tool to decompose Fourier ...

View answer