11
$\begingroup$

The average value of an operator $O$ in the state $\left.|\psi\right>$ is $$\overline{O}=\left<\psi|O|\psi\right>$$ Now for simplicity let $\left.|\psi\right>=\left.|0\right>^n$ and assume we have a circuit that prepares $O$. How many times one has to run this circuit and measure $O$ in the computational basis to get an accurate estimation of $\overline{O}$ ?

I guess one needs to somehow describe what kind of operator $O$ is. For example, if there is a very large eigenvalue $\lambda$ of $O$ which appears with a very low probability $p$ in the state $\left.|0\right>^n$ I expect the required number of trials to depends strongly on $p$ and $\lambda$.

Initially my question arose when reading this paper which states on the first page that when $O$ is a product of single-qubit observables its average can be computed efficiently by running the quantum circuit $O$ many times and averaging the results. Then the authors go on to give efficient classical algorithms for the same task, but they do not explain what is the complexity of the quantum algorithm. It is not clear to me if it is not exponential in the number of qubits.

Another motivation for my question. Say we use the VQE (variational quantum eigensolver) to find the ground state of some Hamiltonian. The procedure is to build an ansatz quantum circuit, measure its average energy and then optimize the ansatz parameters to go towards lower energy. My problem is with the second step "measure average energy". How many times one is supposed to run the quantum circuit for to get the average energy estimation?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ There might be some guidance in "Several natural BQP-Complete problems" by Wocjan and Zhang (arxiv) and the references therein. In particular, the general problem of eigenvalue sampling for a local Hamiltonian is $\mathsf{BQP}$-complete. They state that if $H$ (your $O$) is local then "we can obtain the exact average eigenvalue of a local Hamiltonian deterministically in polynomial time". Other references I think give good bounds on $p$, $\lambda$ as you suggest, which depends on the operator norm of $H$ (your $O$). $\endgroup$
    – Mark Spinelli
    Commented Apr 16, 2021 at 13:13

1 Answer 1

Reset to default
10
$\begingroup$

If you want to extract the exact value then would need infinite number of samples.

However, assume no hardware noise, based in the Chebyshev's inequality you would need to do $O(1/\epsilon^2)$ to get within $\epsilon$ accuracy for each circuit in your experiment. Here, each circuit correspond to a Pauli term that your operator $O$ decomposed into. For instance, $O = 1.5Z + 2X - 3Y$. Then you would need to create 3 circuits to calculate each expectation $\langle \psi | Z | \psi \rangle$, $\langle \psi | X | \psi \rangle$, $\langle \psi | Y | \psi \rangle$. See this answer here for more detail. Each of those circuit will require $O(1/\epsilon^2)$ shots/runs to extract an expectation value within $\epsilon$ from the true expectation value.

Thus, you can see that it can be quite expensive.

However, on current quantum devices, the noise is so large that you will never able to get within says $10^{-3}$ accuracy anyway. So by doing a lot of shots/runs won't help much. If you running VQE or any type of variational quantum algorithms on current hardware, $\approx 10,000$ shots should be enough. If you do too many shots, you will ended up picking up the noise landspace of the cost function...

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great thank you. In fact I was thinking about how the number of shots scales with the number of qubits $n$, not the accuracy $\epsilon$. I think I now realize that for operators that appear in VQE are factorized into a single-qubit operators. Then the number of trials should be pretty much independent of $n$ because the total average is just the product of averages. Still, thinking about the accuracy $\epsilon$ is also instructive. $\endgroup$
    – Nikita Nemkov
    Commented Mar 23, 2021 at 7:55

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.