Abstract A while loop tests a termination condition on every iteration. On a quantum computer, such measurements perturb the evolution of the algorithm. We define a while loop primitive using weak measurements, offering a trade-off between the perturbation caused and the amount of information gained per iteration. This trade-off is adjusted with a parameter set by the programmer. We provide sufficient conditions that let us determine, with arbitrarily high probability, a worst-case estimate of the number of iterations the loop will run for. As an example, we solve Grover’s search problem using a while loop and prove the quadratic quantum speed-up is maintained.
Abstract A while loop tests a termination condition on every iteration. On a quantum computer, such measurements perturb the evolution of the algorithm. We define a while loop primitive using weak measurements, offering a trade-off between the perturbation caused and the amount of information gained per iteration. This trade-off is adjusted with a parameter set by the programmer. We provide sufficient conditions that let us determine, with arbitrarily high probability, a worst-case estimate of the number of iterations the loop will run for. As an example, we solve Grover’s search problem using a while loop and prove the quadratic quantum speed-up is maintained.
Grover's algorithm searches an unstructured database of N entries, finding a marked element in time O(N). The algorithm was later generalised to amplitude amplification. The original algorithm succeeds with probability close to one and needs to run for a number of iterations chosen ahead of time. We discuss an implementation of amplitude amplification that, instead, runs for a number of iterations unspecified a priori and only halts on success. We prove that this approach maintains the quadratic speed-up of the original quantum algorithm. The key component is a feedback loop controlled by a weak measurement that allows limited monitoring of the evolution of the quantum state.
We present a family of quantum amplitude amplification algorithms that interleave ordinary Grover rotations with tunable weak measurements in loops. A successful measurement yields the target state and stops the algorithm, while after a failure, the loop resumes from the post-measurement state without restarting. We express the leading costs in expected Grover iterations as p→0. For a known target probability p, an exact weak measurement-conditioned loop for states near the angle π/4 uses (π/8+1/4+o(1))/p iterations, improving on the standard Grover constant π/4 and on optimised restart Grover, and matching the corresponding infimum in our continuous-angle analysis. When only a lower bound 0<p0≤p<1/2 is available, a discrete Lyapunov equation gives the exact expected oracle cost for every fixed measurement strength and a closed-form optimal strength. Using the strength selected from p0, the expected number of Grover iterations is at most 221(p1+p01), where the expected cost decreases as the actual p increases, and gives the leading constant 1/2 at the promise boundary p=p0. For completely unknown p, we identify measurement strength κ(t)=Θ(1/t) as the critical scale within the regular schedules considered here and analyse κb(t)=min{1/2,b/t}. For each fixed b>2, we rigorously derive a closed-form Gamma-function expression C(b) giving (C(b)/2+o(1))/p expected iterations. Numerical minimisation of this explicit expression gives b≈5.2 and C(b)/2≈1.01. The results show that weak measurements preserve the Θ(1/p) search scale while adding an explicit fixed-point control mechanism and provable oracle savings.
Run-times of quantum algorithms are often studied via an asymptotic, worst-case analysis. Whilst useful, such a comparison can often fall short: it is not uncommon for algorithms with a large worst-case run-time to end up performing well on instances of practical interest. To remedy this it is necessary to resort to run-time analyses of a more empirical nature, which for sufficiently small input sizes can be performed on a quantum device or a simulation thereof. For larger input sizes, alternative approaches are required.In this paper we consider an approach that combines classical emulation with detailed complexity bounds that include all constants. We simulate quantum algorithms by running classical versions of the sub-routines, whilst simultaneously collecting information about what the run-time of the quantum routine would have been if it were run instead. To do this accurately and efficiently for very large input sizes, we describe an estimation procedure and prove that it obtains upper bounds on the true expected complexity of the quantum algorithms.We apply our method to some simple quantum speedups of classical heuristic algorithms for solving the well-studied MAX- k -SAT optimization problem. This requires rigorous bounds (including all constants) on the expected- and worst-case complexities of two important quantum sub-routines: Grover search with an unknown number of marked items, and quantum maximum-finding. These improve upon existing results and might be of broader interest.Amongst other results, we found that the classical heuristic algorithms we studied did not offer significant quantum speedups despite the existence of a theoretical per-step speedup. This suggests that an empirical analysis such as the one we implement in this paper already yields insights beyond those that can be seen by an asymptotic analysis alone.
A simpler quantum counting algorithm based on amplitude amplification is presented. This algorithm is bounded by O(sqrt(N/M)) calls to the controlled-Grover operator where M is the number of marked states and N is the total number of states in the search space. This algorithm terminates within log(sqrt(N/M)) consecutive measurement steps when the probability p1 of measuring the state |1> is at least 0.5, and the result from the final step is used in estimating M by a classical post processing. The purpose of controlled-Grover iteration is to increase the probability p1. This algorithm requires less quantum resources in terms of the width and depth of the quantum circuit, produces a more accurate estimate of M, and runs significantly faster than the phase estimation-based quantum counting algorithm when the ratio M/N is small. We compare the two quantum counting algorithms by simulating various cases with a different M/N ratio, such as M/N > 0.125 or M/N < 0.001.
Grover’s algorithm leverages quantum computing to efficiently locate solutions in unstructured search spaces, outperforming classical approaches. Since Grover’s algorithm requires prior knowledge of the number of solutions (M) within a search space of size N, previous studies assume M is estimated beforehand and focus on identifying all solutions. Here, we propose a two-step process that integrates both the estimation of M and the discovery of the solutions, optimizing the interactions between the two steps. To enhance efficiency, the estimation step captures as many solutions as possible, leaving the discovery step to focus on the remaining ones. To ensure accuracy, the discovery step continues searching until the probability of finding additional solutions becomes sufficiently low. We implemented and evaluated our methods, showing that over 80% of solutions were found during the estimation phase, allowing the discovery phase to conclude earlier, while identifying over 99% of solutions on average. In theory, the process requires NM × log(M) Grover’s iterations in the worst case, but in practice, it typically terminates after iterations proportional to N. We expect that our methods will be applicable to various search problems and inspire further research on efficiently finding all solutions.
Quantum information processing and computation requires high accuracy qubit configuration readout. In many practical schemes, the initial qubit configuration has to be inferred from readout that is a time-dependent weak measurement record. However, a combination of the measurement scheme and intrinsic dynamics can end up scrambling the initial state and lose information irretrievably. Here, we study the information physics of quantum trajectories based on weak measurements in order to address the optimal achievable performance in qubit configuration readout for two realistic models of single qubit readout: (i) Model I is informationally complete, but without intrinsic dynamics; (ii) Model II is informationally incomplete weak measurements with intrinsic dynamics. We first use mutual information to characterize how much intrinsic information about the initial state is encoded in the measurement record. Using a fixed discrete time-step formulation, we compute the mutual information while varying the measurement strength, duration of measurement record, and the relative strength of intrinsic dynamics in our measurement schemes. We also exploit the emergence of continuum scaling and the Stochastic Master Equation in the weak measurement limit. We develop an asymptotic expansion in the measurement efficiency parameter to calculate mutual information, which captures qualitative and quantitative features of the numerical data. The bounds on information extraction are manifested as plateaux in mutual information, our analysis obtains these bounds and also optimal duration of measurement required to saturate them. Our results should be useful both for quantum device operation and optimization and also, possibly, for improving the performance of recent machine learning approaches for qubit and multiqubit configuration readout in current Noisy Intermediate-Scale Quantum (NISQ) experiment regimes.