Is there an efficient circuit implementing the unitary $U|x\rangle|0\rangle=|x\rangle\Big(\sqrt{1 - x/2^n}\,|0\rangle+\sqrt{x/2^n}|1\rangle\Big)?$

Question

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.

Answer 1

I think that asking for an exact solution is pointless, because quantum computers don't have infinite precision. You are limited, for example, by accuracy of pulses that control the gates.

To implement the idea of the mentioned answer, you can refer to this paper which introduces a general method for constructing an efficient and highly accurate quantum circuit for evaluating functions such as $sin(x)$, $arcsin(x)$ and $\sqrt x$.

And if using Qiskit is an option for you, this method is implemented in PiecewiseChebyshev class, Which constructs a circuit for the transformation:

$|x\rangle|0\rangle \mapsto |x\rangle\Big(\cos(f(x)) |0\rangle + \sin(f(x))|1\rangle\Big)$

If you choose $f(x) = \arcsin(\sqrt{x/2^n})$, you will get your circuit:

# number of state qubits:
N = 2

# The function to be implemented:
func = lambda x: np.arcsin(np.sqrt(x / 2 ** N))

# The degree of Chebyshev polynomials. Use higher degree for better approximation
degree = 5

breakpoints = [1, 4]

# You may use breakpoints param to breakdown the interval into sub-intervals.
# This allows to achieve a good approximation using low-degree polynomials.
# For example:
# breakpoints = [1, 2, 4]

pw_approx = PiecewiseChebyshev(func, degree, breakpoints, N)
pw_approx._build()

num_ancilla_qubits = pw_approx.num_ancillas

qc = QuantumCircuit(pw_approx.num_qubits)
qc.h(list(range(N)))
qc.append(pw_approx.to_instruction(), qc.qubits)