New answers tagged

1 vote

I have question about cost of 'modular multiplication unitary' in Shor's algorithm

The point is that you can perform this calculation efficiently on a classical computer. So you can implement the same algorithm on a quantum computer. Just think: if you had to do this calculation by ...
user avatar
  • 46.1k
2 votes

Are there quantum algorithms showing a double exponential advantage?

There is a super exponential query reduction for a quantum algorithm that solves SEARCH WITH ADVICE problem for a power law advice distribution with average-case query complexity O(1) as N tends to ...
user avatar
5 votes

Proven quantum advantage (in the algorithmic sense) without error correction (for specific algo, or noise models)

A photon based quantum computer named Jiuzhang in 2020 performed gaussian boson sampling (GBS) (Link to paper) of 76 photons.Researchers are interested in quantum algorithm for Boson sampling using ...
user avatar
3 votes
Accepted

Exponential advantage with Hadamard test

The Aharonov–Jones–Landau (AJL) algorithm[1] calculates an additive approximates of the Jones polynomial of the plat closure of a braid on $n$ strands with $m$ crossings at a kth root of unity $e^{2\...
user avatar
1 vote

Proven quantum advantage (in the algorithmic sense) without error correction (for specific algo, or noise models)

This kind of asymptotic advantage strikes me as obviously impossible, or maybe even ill-defined, because without error correction the quantum computer can only do O(1) gates before your signal is ...
user avatar
  • 21.8k
2 votes

Quantum advantage without phase?

It is well known that quantum computing with real numbers (i.e., only states & gates with real entries) is as powerful as quantum computing with complex entries. (While you obviously cannot ...
user avatar
0 votes
Accepted

Derivation of the linear cross entropy

In case anyone else gets caught up on this detail: I spoke to Soonwon Choi and he explained that the "linear" cross-entropy is not a linearization of the cross-entropy. Rather it is called ``...
user avatar
1 vote

Are qubits just analog, continuous classical bits?

Another point of view for this could be a complexity one. Namely, we know how to efficiently simulate analog computation classically. Whereas we still haven’t figured out how to do so for quantum ...
user avatar
1 vote

Are qubits just analog, continuous classical bits?

I consider only one qubit in this explanation. A qubit does not contain as much information as a "continuous classical needle" living in a sphere, in the following sense. If I assume that it ...
user avatar

Top 50 recent answers are included