New answers tagged

1

I asked basically the same question on CS stack exchange before this community was created. The answer is that the class of exact quantum algorithms has a name (EQP) but isn't very natural to study theoretically, because whether or not an exact algorithm can be executed depends entirely on the gate set that you have available, and moreover there's no ...


2

Say you want to factorise a large integer $N$. We know (inefficient) classical algorithms to do this, a naive example being: just check all combinations of smaller numbers until you find one that multiplies to $N$. You can make this into a quantum algorithm by simply converting each operation in your classical algorithm into a reversible one (there are ...


3

Only a partial answer, the Deutsch-Jozsa algorithm is an example of an exact algorithm. In my view, the algorithms differ exactly in how the answer is given. Either with probability 1 for exact algorithms, or with a bounded probability for approximate ones. I would say you cannot use amplitude amplification in exact algorithms, as this would imply that ...


Top 50 recent answers are included