3
$\begingroup$

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?

$\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$
    – Mauricio
    Sep 12 at 12:22
3
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much. I will read these papers tomorrow, I'm pretty sure they will help me. $\endgroup$
    – stopper
    Sep 12 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.