# Is there a quantum algorithm for this?

While a well-established quantum algorithm exists for finding an estimate of the phase of the eigenvalue of a unitary matrix, the following question has a bit of a different requirement. Suppose we have the following quantum state

$$a(0)|0\rangle+a(1)|1\rangle+a(2)|2\rangle+a(3)|3\rangle+a(4)|4\rangle+a(5)|5\rangle+a(6)|6\rangle+a(7)|7\rangle$$

where the $$7$$ values $$a(0)$$ to $$a(6)$$, which maybe any real or any complex numbers, which may have a phase though we are not interested to find that,are all equal to the real value $$1/\sqrt{8}$$ in their magnitude. $$a(7)=\exp(2 \pi i \theta)/\sqrt{8}$$. In other words it is only $$a(7)$$ that has a phase factor with the theta we are interested to find.

Does there exist a quantum algorithm to find theta in $$a(7)$$?

Does there exist a quantum algorithm, for it's obvious generalisation, to find theta in $$a(-1+t)$$? where $$t$$ is a power of $$2$$.

If I understand your question correctly, you are given a state $$|\psi\rangle=\frac{1}{\sqrt{2^n}}\left(\sum_{m=0}^{2^n-2}|m\rangle+e^{i\theta}|2^n-1\rangle\right)$$ and you want to find $$\theta$$? This is fairly straightforward. If you apply a unitary $$U$$ such that $$U\sum_{m=0}^{2^n-2}|m\rangle=\sqrt{2^n-1}|0\rangle$$ and $$U|2^n-1\rangle=|1\rangle,$$ then $$U|\psi\rangle=(\sqrt{2^n-1}|0\rangle+e^{i\theta}|1\rangle)/\sqrt{2^n}.$$ You can run your usual phase detection algorithm on this one qubit state. The only problem is that the phase is massively suppressed so you're going to have to run it many more times to get a good estimate. For example, if you perform $$X$$ measurements on this state, $$p_+=\frac{\sqrt{2^n-1}}{2^{n-1}}\cos\theta,$$ which is exponentially small, meaning you need exponentially good accuracy (and hence repetitions) in order to resolve the value of $$\cos\theta$$.

• That solves it for the special case when there are no complex phase factors in the seven numbers a(0) to a(6).Is it solvable in the general case where there are abitrary phase factors in a(0) to a(t-2)?
– Chez
Oct 11, 2023 at 11:21
• known or unknown? Oct 11, 2023 at 12:18

Up to a global phase, an $$n$$-qubit quantum state $$|\psi\rangle$$ can be written as $$|\psi\rangle = r_0|0\rangle + r_1e^{i\theta_1}|1\rangle + r_2e^{i\theta_2}|2\rangle + \ldots + r_{t-1}e^{i\theta_{t - 1}}|t-1\rangle$$ where $$t = 2^n$$, $$r_j$$ are non-negative real numbers for $$0 ≤ j ≤ t - 1$$, and $$0 ≤ \theta_j ≤ 2\pi$$ for $$1 ≤ j ≤ t - 1$$

Let $$U(u_{00}, u_{0k}, u_{k0}, u_{kk})$$ denotes the two-level unitary $$\begin{pmatrix} u_{00} & 0 & 0 & \cdots{}& u_{0k} & \cdots{} & 0\\ 0 & 1 & 0 & & 0 & & 0\\ 0 & 0 & 1 & & 0 & & 0\\ \vdots{} & & & & \vdots{} & & \vdots{}\\ u_{k0} & 0 & 0 & \cdots{} & u_{kk} & \cdots{} & 0 \\ \vdots{} & & & & \vdots{} & & \vdots{}\\ 0 & 0 & 0 & & 0 & & 1\\ \end{pmatrix}$$ then,

$$\langle\psi|U {\small (u_{00}, u_{0k}, u_{k0}, u_{kk}) } |\psi\rangle=u_{00}r_0^2 + u_{0k}r_0r_ke^{i\theta_k} + r_1^2 + r_2^2 + \cdots{} + u_{k0}r_0r_ke^{-i\theta_k} + u_{kk}r_k^2 + \cdots{} + r_{t-1}^2$$

The real and imaginary parts of this quantity are:

$$\mathrm{Re}[\langle\psi|U {\small (u_{00}, u_{0k}, u_{k0}, u_{kk}) } |\psi\rangle]=u_{00}r_0^2 + r_1^2 + r_2^2 + \cdots{} + u_{kk}r_k^2 + \cdots{} + r_{t-1}^2 \\ + (u_{0k} + u_{k0})r_0r_k \cos(\theta_k) \tag{1}$$

and

$$\mathrm{Im}[\langle\psi|U {\small (u_{00}, u_{0k}, u_{k0}, u_{kk}) } |\psi\rangle]=(u_{0k}-u_{k0})r_0r_k \sin(\theta_k) \tag{2}$$

respectively.

We can use Hadamard test to get these values. So, if we already know the values of $$r_j$$, we can use any one of the previous two formulas to calculate $$\theta_k$$.

For the general case where we don't know the values of $$r_j$$ we can follow the following procedure:

Let's pick two real numbers $$\alpha$$ and $$\beta$$ such that $$|\alpha|^2 + |\beta|^2 = 1$$ (e.g., $$\alpha=0.6, \beta=0.8$$) and assume that

$$x_1=\mathrm{Re}[\langle\psi|U {\small (\alpha, \beta, -\beta, \alpha) } |\psi\rangle]$$,

$$x_2=\mathrm{Re}[\langle\psi|U {\small (\alpha, \beta, \beta, -\alpha) } |\psi\rangle]$$,

$$x_3=\mathrm{Re}[\langle\psi|U {\small (\beta, \alpha, -\alpha, \beta) } |\psi\rangle]$$,

$$x_4=\mathrm{Re}[\langle\psi|U {\small (\beta, \alpha, \alpha, -\beta) } |\psi\rangle]$$, and

$$y_1=\mathrm{Im}[\langle\psi|U {\small (\alpha, \beta, -\beta, \alpha) } |\psi\rangle]$$

By using equation (1),

$$x_1-x_2=2\alpha r_k^2-2\beta r_0r_k\cos(\theta_k), \text{and} \tag{3}$$

$$x_3-x_4=2\beta r_k^2-2\alpha r_0r_k\cos(\theta_k) \;\;\;\;\;\;\; \tag{4}$$

hence

$$r_k^2=[\beta(x_3 - x_4) - \alpha(x_1 - x_2)]/2(\beta^2-\alpha^2) \tag{5}$$

And by using equations (2) and (3), $$\tan(\theta_k) = y_1 / [2\alpha r_k^2 - (x_1 - x_2)] \tag{6}$$

We use Hadamard test to get $$x_1, x_2, x_3, x_4$$, and $$y_1$$ then we use equations (5) and (6) to compute $$r_k$$ and $$\theta_k$$.

Edit: Here is an implementation (using Qiskit) for this idea.