Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2009.08832 · Quantum Science and Technology

Weakly measured while loops: peeking at quantum states

Pablo Andrés-Martínez, Chris Heunen

Published Jan 4, 2022• 16 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/2058-9565/ac47f1

Related papers

Weakly Measured Loops for Quantum Amplitude Amplification: Oracle Savings and Adaptive Search with Unknown Target Probability

Wang Fang, Chris Heunen

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 \to 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))/\sqrt{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 < p_0 \leq 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 $p_0$, the expected number of Grover iterations is at most $\frac{1}{2\sqrt{2}}(\frac{1}{\sqrt{p}}+\frac{1}{\sqrt{p_0}})$, where the expected cost decreases as the actual $p$ increases, and gives the leading constant $1/\sqrt{2}$ at the promise boundary $p = p_0$. 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))/\sqrt{p}$ expected iterations. Numerical minimisation of this explicit expression gives $b \approx 5.2$ and $C(b)/2 \approx 1.01$. The results show that weak measurements preserve the $Θ(1/\sqrt{p})$ search scale while adding an explicit fixed-point control mechanism and provable oracle savings.

quant-pharXiv:2609.39621•Oct 1, 2026•1 citation

Simpler quantum counting

Chu-Ryang Wie

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.

Quantum Information and Computation•Sep 1, 2019•38 citations

A quantum while loop for amplitude amplification

Pablo Andrés-Martínez, Chris Heunen

Grover's algorithm searches an unstructured database of $N$ entries, finding a marked element in time $\mathcal{O}(\sqrt{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.

•Sep 18, 2020•0 citations

Finding All Solutions with Grover’s Algorithm by Integrating Estimation and Discovery

Sihyung Lee, Seung Yeob Nam

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.

Electronics•Dec 6, 2024•9 citations

Experimental Feedback Control of Quantum Systems Using Weak Measurements

Geoff Gillett, R. B. Dalton, B. P. Lanyon +7 more

A goal of the emerging field of quantum control is to develop methods for quantum technologies to function robustly in the presence of noise. Central issues are the fundamental limitations on the available information about quantum systems and the disturbance they suffer in the process of measurement. In the context of a simple quantum control scenario-the stabilization of nonorthogonal states of a qubit against dephasing-we experimentally explore the use of weak measurements in feedback control. We find that, despite the intrinsic difficultly of implementing them, weak measurements allow us to control the qubit better in practice than is even theoretically possible without them. Our work shows that these more general quantum measurements can play an important role for feedback control of quantum systems.

arXiv:0911.3698•Physical Review Letters•Feb 26, 2010•154 citations

Efficient Quantum Computing With Weak Measurements

Austin P. Lund

We show that constraining a quantum computing architecture to low strength measurement does not introduce an inefficient overhead provided non-local measurements are allowed. With only local measurements an inefficient overhead must be introduced.

•Jan 1, 2011•0 citations
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.
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→0p \to 0p→0. For a known target probability ppp, an exact weak measurement-conditioned loop for states near the angle π/4π/4π/4 uses (π/8+1/4+o(1))/p(π/8+1/4+o(1))/\sqrt{p}(π/8+1/4+o(1))/p​ iterations, improving on the standard Grover constant π/4π/4π/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/20 < p_0 \leq p < 1/20<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 p0p_0p0​, the expected number of Grover iterations is at most 122(1p+1p0)\frac{1}{2\sqrt{2}}(\frac{1}{\sqrt{p}}+\frac{1}{\sqrt{p_0}})22​1​(p​1​+p0​​1​), where the expected cost decreases as the actual ppp increases, and gives the leading constant 1/21/\sqrt{2}1/2​ at the promise boundary p=p0p = p_0p=p0​. For completely unknown ppp, we identify measurement strength κ(t)=Θ(1/t)κ(t)=Θ(1/t)κ(t)=Θ(1/t) as the critical scale within the regular schedules considered here and analyse κb(t)=min⁡{1/2,b/t}κ_b(t)=\min\{1/2,b/t\}κb​(t)=min{1/2,b/t}. For each fixed b>2b > 2b>2, we rigorously derive a closed-form Gamma-function expression C(b)C(b)C(b) giving (C(b)/2+o(1))/p(C(b)/2+o(1))/\sqrt{p}(C(b)/2+o(1))/p​ expected iterations. Numerical minimisation of this explicit expression gives b≈5.2b \approx 5.2b≈5.2 and C(b)/2≈1.01C(b)/2 \approx 1.01C(b)/2≈1.01. The results show that weak measurements preserve the Θ(1/p)Θ(1/\sqrt{p})Θ(1/p​) search scale while adding an explicit fixed-point control mechanism and provable oracle savings.
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 searches an unstructured database of NNN entries, finding a marked element in time O(N)\mathcal{O}(\sqrt{N})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.
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.
A goal of the emerging field of quantum control is to develop methods for quantum technologies to function robustly in the presence of noise. Central issues are the fundamental limitations on the available information about quantum systems and the disturbance they suffer in the process of measurement. In the context of a simple quantum control scenario-the stabilization of nonorthogonal states of a qubit against dephasing-we experimentally explore the use of weak measurements in feedback control. We find that, despite the intrinsic difficultly of implementing them, weak measurements allow us to control the qubit better in practice than is even theoretically possible without them. Our work shows that these more general quantum measurements can play an important role for feedback control of quantum systems.