Given an $n$-qubit register $|x\rangle$, does there exist an efficient circuit implementing unitary operation $U$ such that

$$U |x\rangle|0\rangle = |x\rangle\Big(\sqrt{1 - x/2^n}\, |0\rangle + \sqrt{x/2^n}\, |1\rangle\Big)?$$

I've found this related question from which the answer suggests to rotate and apply an $\arccos$ approximation (which is very complicated, and only provides an approximation). Is there not an exact circuit implementing this from simple gates plus $R_k$?

The context of this question is trying to implement Algorithm 1 from Quantum speedup of Monte Carlo methods by Ashley Montanaro. They say (paraphrased):

Also observe that $U$ can be implemented efficiently, as it is a controlled rotation of one qubit dependent on the value of $x$ [59]

I did not find the linked reference (Quantum algorithm for approximating partition functions by Wocjan et al) particularly enlightening. And I don't believe they used the $\arccos$ approximation either, as they did not include this in the error analysis. So I am confused as to how $U$ is actually implemented.


Your Answer

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

Browse other questions tagged or ask your own question.