Let a simple quantum circuit consist of one qubit and one classical bit. Initially, a qubit has the $|0\rangle$-state and then goes through some sequence of quantum gates, see the circuit below.

Circuit 1

The quantum gates affect the qubit by changing its probability of being in one of two states after measuring. Let suppose that the quantum gates of the sequence are unknown. So in order to extract a qubit probability of being in one of two states after measuring it needs to performe such an action several times (the more the more accurate) pushing other qubits of the $|0\rangle$-state into the circuit.


It is interesting is it possible to do it with another way? Is there maybe a quantum algorithm that ables to do such a thing?


1 Answer 1


I think what you want is the quantum amplitude estimation algorithm developed by Brassard et al. here.

The amplitude estimation problem is given an arbitrary quantum circuit $C$ which outputs the state $$C|0\rangle=\sqrt{1-p}|\psi_0\rangle+\sqrt{p}|\psi_1\rangle,$$ where $p\in[0,1]$, find an estimate of the value $p$.

The algorithm works by performing quantum phase estimation (really eigenvalue estimation) on the Grover operator $G=CR_0C^*R_{\psi_1}$ used in the amplitude amplification algorithm (such an algorithm can be used to boost the probability of obtaining the state $|\psi_1\rangle$ from $C$), where $C$ is the circuit and $R_0$ is the unitary reflection about $|0\rangle$ and $R_{\psi_1}$ is the reflection about $|\psi_1\rangle$. I'll refer you to the links above for the details.

Note that the Grover operator $G$ will need to be queried multiple times to obtain the estimate, and the full complexity is related to how much error you are willing to accept in your estimate of $p$. However, I believe that this algorithm is optimal due to the lower bound on the complexity of Grover search (i.e. amplitude amplification).


Your Answer

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

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