# What is optimum method for measuring the probability for all zero state given an arbitrary circuit using ancilla qubits and additional gates

Given some arbitrary quantum circuit, I want to measure the probability amplitude for the all zero state in an optimum manner, given possibly additional ancilla qubits and by applying additional quantum gates. Given that I am not interested in reconstructing the full state, there must be a method which is more economical with respect to the total number of shots and the number of additional gates.

Is there a more efficient method? What is the optimum approach?

• Why add ancilla and multi-anti-control NOT instead of just 3 measurements on the first 3 registers? Jan 4, 2023 at 16:14
• Because I want to reduce the number of shots. Overall, I want to optimize for the number of shots and the additional number of gates. Jan 4, 2023 at 16:18
• The method described by @MonteNero takes exactly as much time as yours, in both cases you will get the desired result with the probability you seek. Thus, you will get the exact same precision with the same number of shots using both methods Jan 4, 2023 at 17:33
• Indeed, you are right. The question was edited. Jan 4, 2023 at 19:12

As mentioned in this answer, it is not possible to transform a probability to a basis state which you can then measure.

Thus, your only option is to take a statistical approach: repeatedly measure the qubits you're interested in and the probability you seek is the approximately the observed frequency of the all-zeros state.

There are two approaches for this: directly measuring the state as proposed by MonteNero in the comments or boosting the probability beforehand using something like amplitude amplification.

I don't think the latter can be of use if you don't know the amplitude beforehand (which is the point). Plus, even if you were to multiply by a known factor $$q$$ the probability , the associated incertitude gets divided by $$\sqrt{1+\frac{q-1}{1-qp}}$$, which can be either quite small or quite costly to do depending on $$p$$.

• I am accepting this answer as it is correct in spirit, in particular the cost of estimation in terms of number of shots scales exponentially with the number of qubits n. If one is willing to modify the question a bit by asking what is the fidelity of the unknown state w.r.t all zero state, there are methods (arxiv.org/pdf/1104.4695.pdf) that also scale exponentially with n in worst cases but in practice are often significantly faster than 2^n which corresponds to the brute force approach. Jan 6, 2023 at 12:10
• @RaduM. If you have time, I would advise for you to write your own answer and accept it, especially since mine implies that there is no better method. By doing so, you would help the next person to have the same problem as you! That's especially true if you gain a fair understanding of the paper you linked. Jan 6, 2023 at 12:20
• You say you don't think that amplitude amplification can help. I don't know if it can, but I wouldn't rule it out too quickly - after all, amplitude amplification is basically just Grover's search, and there is a version of Grover's search (plus phase estimation) that can estimate the number of solutions to the search problem, which is essentially what we're talking about here. That said, there are some accuracy consequences. Jan 6, 2023 at 13:33
• @DaftWullie That's a fair point. I may be wrong here (in which case I blame my poor intuition about amplitude amplification), but I don't see how this algorithm can help here. The angle of rotation of the Grover operator depends only on the number of solutions, here $1$, and not on the associated probability we want to estimate. If the state was $\sum\limits_{x\in S}|x\rangle$ for $S\subset\{0;1\}^n$, then I see why this algorithm would help. However, in this case of an arbitrary circuit, how would you go using this algorithm? Which problem do you define so that the amplitude of $0$ intervene? Jan 6, 2023 at 14:44

I suspect you should be able to use a multi-qubit swap test. For example, if your state is $$\psi$$, you could add another state $$\phi$$ and an ancilla, both initialized as $$|00...0\rangle$$ and $$|0\rangle$$, and then measure the probability of the ancilla to be $$|0\rangle$$, which is: $$Pr(|0\rangle) = \frac{1}{2} + \frac{1}{2}\langle \phi | \psi \rangle ^ 2$$ In other words, if your original state was close to $$|00...0\rangle$$ the inner product will be close to 1 and you would get a probability close to 1. You would get just $$1/2$$ if the inner product is close to 0.

Here is the multi-qubit swap test circuit for 3 qubits:

• I've thought about it too, but I think this scales worse than the bruteforce approach. Using the $95\%$ interval, the incertitude scales as $\sqrt{\frac{p(1-p)}{n}}\approx\sqrt{\frac{p}{n}}$ for the direct approach but as $\sqrt{\frac{1-p^2}{n}}\approx\sqrt{\frac{1}{n}}$ for the SWAP test approach, which is worse (potentially exponentially worse depending on $p$), assuming my computations are correct Jan 6, 2023 at 12:23