6
$\begingroup$

When testing my quantum programs, I wonder how many shots I must take to get a specific accuracy.

Are there any papers that you can recommend that analyze this?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

This is depends on what algorithm you are executing.

For example, if you look at the Bernstein-Vazirani algorithm then theoretically the number of shot you need is 1 if you have a perfect quantum computer. This is because the end result that you are looking for collapsed onto a single eigenstate. However, because of noise, we would like to do more. In term of how many more, this is depends on the device. Not all device have the same noise level. You can, actually, look at the gate fidelity on the machines (at least you can do that for IBM's machines) and work out the probability that your circuit will fail, then from there determine the number of shots you might want to use. However, without doing that analysis, then you can just be on the safe side by using the maximum number of shots giving to you. For IBM's machines this works out to be 8192 shots. However, you can run multiple jobs to collect the statistics if you think you need more shots than this. Now, of course, if your quantum circuit is too long, the errors will built up so much that your circuit will "essentially" guarantee to fails, then additional shots will not help.

The above discussion is for quantum algorithms that only need $O(1)$ shots/samples. This is not true for algorithm like VQE. For VQE, we need to do $O(1/\epsilon^2)$ shots to achieve error of $\epsilon$. For chemical accuracy, which is for $\epsilon = 10^{-3}$, you would need to do ~$10^6$ shots at each iteration... which is insane!

Now if you just create a random circuit, which output a state that could be in super-position of $2^n$ eigenbasis then you will need $O(2^n)$ shots to able to able to extract the output probabilities. This why, designing a quantum algorithm is like an art. Therefore, You can't just do some operations on a quantum computers, and claim that because you did it on a quantum computer, it must be faster than doing it classically. You do not have access to the state of the qubits! This is also the reason why you can't just perform Quantum Fourier Transform ( essentially doing Discrete Fourier Transform on a quantum computer) and claim that you have a speed-up. Although, QFT does give you an exponential speed-up over DFT or even FFT (Fast Fourier Transform), doing it randomly will output a generic quantum state that in superposition of $2^n$ eigenbasis... Extracting out this state would take exponential amount of samples which then defeat the entire purpose.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thankyou :) How has the accuracy of $\mathcal{O}(1/\epsilon^2) $ been proven? Is there a paper in which it is that I can read? $\endgroup$
    – Hannah
    Nov 2, 2020 at 19:59
  • 1
    $\begingroup$ @Hannah The $O(1/\epsilon^2)$ samples needed for VQE is a direct result of the Chebyshev inequality en.wikipedia.org/wiki/Chebyshev%27s_inequality . Also, if you want a paper reference then in the original paper: arxiv.org/abs/1304.3061 you can look at the first paragraph of page 9 for their discussion on this as well. Hope this help. $\endgroup$
    – KAJ226
    Nov 2, 2020 at 20:34
  • $\begingroup$ thank you so much ! :) $\endgroup$
    – Hannah
    Nov 2, 2020 at 21:37
  • 1
    $\begingroup$ In this paper is the shot-number needed for QAOA with gradient-descent otimizers analysed. This is super interesting! arxiv.org/pdf/1910.01155.pdf $\endgroup$
    – Hannah
    Jan 8, 2021 at 5:50
0
$\begingroup$

One way of this estimation is to analyze how many states will be there. Suppose there will be $N$ states and the shots are $N$, then the average observation of each should be 1, which is easy to forget some states, while if you change to $N^2$ shots the risk is decreased.

For $N$ states, if you take $n$ shots, the probability that a state has not been detected is $n \choose 1$=$(\frac{1}{N})^n$, where degeneracy is ignored.

Another way is rather interesting, I think the shots number only influence the running time slightly. Here comes my observation:

enter image description here

The first case is to search the number 24 from the range [0,31], the second case is to search number 64 from the range [0,127], the last one is printed on the figure (in my code, the number of qubits needed is 3*len(bin(24/64/128)[2:]), three times of the binary length).

According to this observation, I think the time-consuming part of computing is to get the state vector, and the role this 'shot' variable plays is to generate output based on the state vector. So, if you just want to save the running time of your script, maybe you do not need to change the number of shots.

NOTICE that this test is not sophisticated, loopholes maybe continue hidden.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Could you please replace the first picture with actual text? $\endgroup$
    – Martin Vesely
    Nov 4, 2020 at 7:58
  • 2
    $\begingroup$ FINE, I will, later. $\endgroup$
    – Yitian Wang
    Nov 5, 2020 at 2:27

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.