Phase estimation with t counting qubits (N = 2^t) measures an eigenphase \varphi in [0, 1) (from U|u\rangle = e^{2\pi i\varphi}|u\rangle) and returns an outcome y in 0..N-1, whose estimate is y/N. Outcome y comes up with probability
Phases live on a circle (0.99 and 0.01 are only 0.02 apart), so the error of an estimate is the circular distance \mathrm{dist}(a, b) = \min(|a-b| \bmod 1,\ 1 - (|a-b| \bmod 1)). An estimate is good when \mathrm{dist}(y/N, \varphi) \le \delta; a distance within 1e-12 of \delta counts as good, so rounding never decides.
A lab wants the estimate to be good with probability at least p. Write counting_qubits(phi, delta, p) that returns the smallest t \ge 1 for which the probability of a good outcome, \sum_{y\ \text{good}} P_t(y), is at least p. Check t = 1, 2, 3, \dots in turn: a larger t is not always better for a fixed \delta (the second example's numbers show a dip).
Examples
Input: phi = 0.375, delta = 0.01, p = 0.9
Output: 3
Explanation: t = 1 and t = 2 have no estimate within 0.01 of 0.375 (probability 0);
with t = 3, 3/8 = 0.375 exactly and outcome 3 is certain.
Input: phi = 0.3, delta = 0.05, p = 0.9
Output: 4
Explanation: good probability 0 for t = 1, 0.8824 for t = 2 (only 0.25 is good),
0.5775 for t = 3 (again only 0.25 is good), 0.9307 for t = 4.
Input: phi = 0.999, delta = 0.01, p = 0.9
Output: 1
Explanation: with t = 1, outcome 0 (estimate 0.0) is only 0.001 away around the circle.
Constraints
0 <= phi < 1;0.0001 <= delta <= 0.5;0.5 <= p <= 0.99- every test's answer is at most 14, and no probability on the way is within
1e-9ofp - an answer of 14 means sums over 16384 outcomes: keep the work per outcome small
Goals
- Compute the probability that a phase estimate lands within a given distance of the true phase
- Search for the smallest number of counting qubits that meets a precision and a success target
- Measure distances between phases on a circle, where 0.99 and 0.01 are close