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, 2021 at 12:22

1 Answer 1

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, 2021 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.