I would like to study circuits with only one possible outcome. Quantum phase estimation, Bernstein-Vazirani, and in part Deutsch-Jozsa (for constant functions) come to mind - do you know any other important algorithms with only one possible outcome? Or, even better, do you know any criteria to build a circuit in such a way such that it can have only one possible outcome?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ The criteria is that the final state is in the qubit-$z$ basis but that depends a lot on what you want to do. $\endgroup$– MauricioCommented Sep 12, 2021 at 12:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
I think the algorithm class you are referring to is EQP (Exact Quantum Polynomial-Time).
There is a famous breakthrough paper by Ambainis that shows for a superlinear advantage between exact quantum algorithms over their classical counterparts (classical deterministic algorithms) for the query complexity of a total Boolean function. Later Ambainis, Iraids and Smotrovs in another paper developed the optimal exact quantum algorithms to determine whether an $n$-bit string has Hamming weight exactly $k$, and to determine whether an $n$-bit string has Hamming weight at least $k$.
-
1$\begingroup$ Thank you very much. I will read these papers tomorrow, I'm pretty sure they will help me. $\endgroup$– stopperCommented Sep 12, 2021 at 15:48