betaFeedback

WorksComputer Science

Parameterized Weakest-Precondition Calculus for Fine-grained Properties of Quantum Loops

Abstract

Quantum loops may execute arbitrarily many iterations, and understanding their runtime behavior requires knowing how often they terminate, how long terminating runs take, and how common very long runs are. We develop a compositional weakest-precondition framework for analyzing these properties on possibly infinite-dimensional state spaces. It uses parameterized predicates: families of quantum effects indexed by a positive observation scale. These families retain runtime information even when the expected runtime is infinite and can be reused through sequential composition and nested loops. We prove that weakest-precondition equations for loops have unique solutions in the parameterized predicate domain. From the asymptotic behavior of the derived weakest preconditions, we then recover these runtime properties and quantify the influence of very long terminating executions. For the classic discrete-time quantum walk on the one-dimensional infinite line with one absorbing boundary at the origin and the Hadamard gate as its coin operator, we verify its termination probability 2/π2/π, conditional mean π/2π/2, and logarithmic growth of the conditional capped second moment. We then reuse the walk's specification to verify the termination probability and conditional mean runtime of an outer loop that repeatedly invokes it.

Introduction

Quantum programs can contain loops that execute arbitrarily many iterations [3, 51]. Understanding their termination and runtime behavior involves more than deciding whether they terminate: we would like to know how often a loop terminates, how long its terminating runs take on average, and how common very long terminating runs are [5, 8]. These questions describe different aspects of completing a computation. Termination probability measures the likelihood of completion, conditional expected runtime describes its average duration [30], and higher moments—averages of higher powers of runtime, such as its square—give greater weight to long executions [33, 48]. This information helps us both understand a program in isolation and assess the behavior of a larger program that invokes it as a subroutine [4]. It is therefore desirable for a verification framework to establish these properties in a form that supports compositional reasoning, whether the relevant runtime moments are finite or infinite.

Quantum walks, a standard tool in quantum algorithm design, illustrate this difficulty [3, 5, 30]. Consider a particle moving along an infinite line whose positions are labeled by integers, with a quantum coin controlling whether each move is to the left or right. Before each move, the program uses a quantum measurement to check whether the particle is at the origin (position 0). If so, the walk stops; otherwise, the program tosses the coin (using a Hadamard operation) and moves the particle one position left or right according to the coin state. The quantum walk can evolve into a superposition of positions and coin states, allowing interference between different paths and thereby producing termination and runtime behavior different from that of a classical random

Authors’ Contact Information: Tianshi Yu, Institute of Software, Chinese Academy of Sciences, Beijing, China, [email protected]; Minbo Gao, Institute of Software, Chinese Academy of Sciences, Beijing, China and University of Chinese Academy of Sciences, Beijing, China, [email protected]; Li Zhou, Institute of Software, Chinese Academy of Sciences, Beijing, China, [email protected]. walk. Suppose the walk starts at position 1 with its coin in the rightward state. Then the runtime τ\tau, measured in loop iterations, satisfies

P(τ<∞)=2π,E[τ]=∞,E[τ∣τ<∞]=π2,E[min⁡(τ,N)2∣τ<∞]=log⁡N+O(1).\mathbb{P}(\tau< \infty) = \frac{2}{\pi}, \qquad\mathbb{E}[\tau] = \infty, \qquad\mathbb{E}[\tau\mid\tau< \infty] = \frac{\pi}{2}, \qquad\mathbb{E}[\min(\tau,N)^2 \mid\tau< \infty] = \log N + O(1).

Therefore, the walk fails to terminate with probability greater than one third, yet takes fewer than two iterations on average conditional on termination. Moreover, when each terminating run’s duration is capped at NN, the resulting conditional second moment grows logarithmically with NN, which implies the conditional second moment E[τ2∣τ<∞]\mathbb{E}[\tau^2 \mid\tau< \infty] is infinite.

The example above exhibits two distinct sources of infinite moments. On the one hand, the unconditional mean E[τ]\mathbb{E}[\tau] is infinite because nontermination has positive probability. On the other hand, the conditional second moment E[τ2∣τ<∞]\mathbb{E}[\tau^2 \mid\tau< \infty] remains infinite even after restricting attention to terminating runs, because long executions make a sufficiently large contribution. Both facts matter, and the value +∞+\infty alone leaves verifying their quantitative structure unresolved. Moreover, the walk explores an infinite-dimensional state space, so directly representing its unbounded runtime quantities requires a theory of unbounded quantum observables. Thus the challenge is to encode these finer aspects of unbounded behavior in a structure suitable for program reasoning.

Existing approaches to representing unbounded information. There are two approaches to representing such unbounded information [12, 16, 47]. One approach is to admit infinite values directly into the domain of reasoning. For example, interval analyses use infinite endpoints to describe program values with no finite upper or lower bound [16], and probabilistic runtime calculi reason with cost functions taking values in the extended nonnegative reals [27]. Another approach is to represent an infinite collection of quantitative information through a parameterized object. A famous example is the generating function, which encodes an infinite sequence as the coefficients of a formal power series and allows asymptotic properties of the sequence to be recovered from the series’ analytic behavior. This approach supports average-case analysis of sorting, searching, and hashing algorithms [47], as well as reasoning about the output distributions of probabilistic programs [12, 28]. Similarly, in finite-state Markov decision processes, rewards over an infinite horizon are encoded in normalized discounted values, whose limits recover optimal long-run average rewards [22].

Existing works in quantum runtime analysis either do not cover infinite expected costs or follow the first approach, admitting infinite values directly into their reasoning domains. Expected runtime calculi provide compositional methods with finite-dimensional quantum registers or finite-dimensional computational techniques [4, 37]; these techniques do not cover the coherent walk on the infinite line. Yu [56] reduces flowchart programs to a single loop while preserving runtime moments and gives algorithms for termination and exact expected runtime; the computation of this work assumes a finite-dimensional state space and almost-sure termination, conditions under which all runtime moments are finite. Unbounded pre-expectations [21] and closed positive quadratic forms [59] follow the direct approach, extending expectation-transformer reasoning to infinite-dimensional systems through unbounded predicates. These calculi can establish that an expected cost is infinite, but that conclusion alone leaves the finer properties above unresolved. Thus we want to seek a representation that retains this finer information and supports quantum program composition.

Design choice. We take the second approach: encoding the unbounded information into a parameterized object. Its central design problem is to choose how execution times are weighted at each parameter value. The weights are designed to meet three requirements. First, they are bounded, so that the resulting observations remain finite even when runtime moments are infinite. Second, they support composition, so that verified specifications for individual commands can be combined according to the program structure. For quantum programs, this involves preserving the dependence between execution time and the state on which the next command acts. Third, they retain enough runtime information to recover termination probabilities, conditional moments, and the divergence rates of infinite moments. Meeting these requirements together allows the parameterized representation to support both quantitative analysis and compositional verification.

To meet the above requirements, we use an auxiliary observation scale s>0s > 0 and assign a finite runtime nn the weight

rs(n)≜ss+n,rs(∞)≜0.r_s(n) \triangleq\frac{s}{s+n}, \qquad r_s(\infty) \triangleq0.

At each scale, these weights give bounded observations of execution time. Changing the scale changes how strongly long executions contribute to the observation. The weights also allow time consumed by a command to be accounted for by shifting the scale, which supports sequential calls and nested loops. Their large-scale behavior retains the information used to recover the runtime properties above. Thus the scale provides a common means of organizing both program composition and quantitative analysis.

Contributions. Building on the above choice of weights, we develop a weakest-precondition calculus for reasoning about fine-grained properties of quantum loops. The concrete contributions are as follows:

  • Runtime-graded semantics and parameterized predicates. To express specifications in this calculus, we introduce parameterized predicates: families of bounded quantum effects indexed by the observation scale. We support them with a runtime-graded semantics that records, for each finite runtime nn, the output state of executions that terminate after exactly nn loop iterations. We also show how to translate a valid cost Hoare triple in [59] into a valid triple over parameterized predicates.

  • A compositional weakest-precondition calculus. Our weakest-precondition calculus propagates these parameterized predicates backward through the program syntax using the runtime weights and scale shifts. Moreover, for loops, we prove that the weakest-precondition equation has a unique solution in the predicate domain and show how to certify an approximation by checking it against the weakest-precondition equation.

  • Rules for extracting runtime properties. Since our parameterized weight has a clear probabilistic interpretation, the asymptotic behavior of a precondition yields termination probabilities and conditional moments. We provide rules for recovering these properties from a runtime family verified on the program’s full state space. When a conditional moment is infinite, the same family gives its rate of divergence, which is measured by how quickly the corresponding capped moment grows as the cap on runtime increases.

Applications. Using this calculus, we verify the termination and runtime properties of the quantum walk mentioned above. To the best of our knowledge, this is the first direct verification of all these properties for the quantum walk on the one-dimensional infinite line using a weakest-precondition calculus.

For the one-dimensional absorbing walk with a Hadamard coin, we verify the termination probability and conditional mean runtime from the program and show that the conditional second moment diverges. When the durations of terminating runs are capped, we establish that the resulting second moment grows logarithmically with the cap. We also extend the analysis to biased walks with arbitrary initial coin states.

Furthermore, to demonstrate the composability of our framework, we verify the termination and runtime properties of a nested loop: an outer loop that repeatedly invokes the Hadamard walk as a subprogram. At each loop test, a fair coin measurement decides whether to exit or to reinitialize the state and run the walk again. By reusing the verified runtime family of the inner walk, we obtain the outer loop’s termination probability and its expected runtime conditional on termination.

Organization. Section 2 presents the motivating example. Sections 3–5 develop the runtime-graded semantics, weakest-precondition calculus, and rules for extracting runtime properties. Section 6 presents the case studies, followed by related work in Section 7 and the conclusion in Section 8. The supplemental text provides full proofs and detailed calculations.

Motivating Example

We use the one-dimensional absorbing quantum walk [5, 30] to illustrate what runtime information a verification framework should retain and what it takes to reuse that information in a larger program. Quantum walks are important algorithmic primitives and universal for quantum computation [14, 15]. As a classic model, the absorbing walk is a concrete and useful setting in which termination probability, finite moments, and infinite moments all matter, both for a single invocation and for a program that calls it repeatedly.

Finite and infinite runtime properties

Figure 1 presents the absorbing Hadamard walk as a quantum loop over a coin register and an integer position register. The coin states ∣L⟩|L\rangle and ∣R⟩|R\rangle control the direction of movement along the integer lattice. At each loop test, the guard MM measures whether the particle is at the origin, grouping all nonzero positions into a single continuation outcome. If the position is zero, the loop terminates; otherwise, the body applies a Hadamard gate C1/2C_{1/2} to the coin and shifts the position left or right accordingly. The guard preserves superpositions among nonzero positions. We measure runtime by the number of entries into the loop body.

Figure 1. The program and its first iteration. The guard distinguishes the origin (outcome zero) from all nonzero sites together (outcome one). Here τ\tau is the total runtime and tt is the remaining runtime from ∣R,2⟩|R,2\rangle.

Starting from ∣R,1⟩|R,1\rangle, the first iteration produces the superposition shown in Figure 1. At the next guard measurement, half of the probability mass terminates at the origin with total runtime τ=1\tau= 1. The other half continues from ∣R,2⟩|R,2\rangle with one iteration already spent.

To characterize the whole execution, we want to answer three questions:

  1. How often does the walk terminate? Its termination probability on this input is 2/π2/\pi.

  2. How long do terminating executions take on average? Their expected runtime is π/2\pi/2, fewer than two iterations.

(3) How strongly do long terminating executions affect the runtime? The conditional second moment is infinite. To describe its divergence, we ask how the conditional second moment grows when each terminating run’s duration is capped at NN before squaring.

The probability, conditional mean, and infinite conditional second moment are known properties of this walk [30 Section 4]. The capped second moment grows logarithmically with NN; establishing this rate is a further verification target, treated in Section E.2 of the supplemental text.

The expected-cost calculus of [59] (or equivalently [21]) allows us to prove that the unconditional expected runtime is infinite (Theorem A.2 of the supplemental text). This follows from the positive probability of nontermination. The infinite conditional second moment has a different source: long executions still make an unbounded contribution after nonterminating runs have been excluded. Thus a verification framework should establish both the finite quantities and the quantitative behavior of the infinite ones.

These questions place two requirements on the parameterized approach outlined in the introduction. Each observation should remain bounded when a runtime moment is infinite. At the same time, the observations taken across parameter values must retain enough information to recover the termination probability, conditional moments, and the growth of capped moments. For this walk, all three questions should be answered from the same verified representation.

Reusing a verified loop in a caller

Figure 2 places Walk inside an outer loop that draws a fresh fair bit at each guard. Outcome one exits the outer loop; outcome one initializes the registers to ∣R,1⟩\lvert R, 1\rangle and executes Walk. When the inner walk terminates, execution continues at the outer guard. Each continuing pass contributes one unit of runtime for entering the outer body plus the runtime tit_i of that call to Walk.

An outer loop calling Walk, with caller pseudocode and example executions

The caller

while randomBit() = 1 do
    coin := |R⟩;
    position := |1⟩;
    Walk
od
Example executionTotal runtime
Exit immediately0
One call finishes, then exit1+t11 + t_1
Two calls finish, then exit2+t1+t22 + t_1 + t_2
A call never terminates∞\infty

Figure 2. An outer loop calling Walk. Each tit_i is the runtime of a terminating call. Total runtime counts entries into both the outer and inner loop bodies.

We now ask for the outer loop’s termination probability and conditional expected runtime. As the table in Figure 2 shows, the caller can terminate before making a call or after several calls have finished. If any call fails to terminate, the caller also fails to terminate. A compositional analysis should obtain the caller’s properties by reusing a verified specification of the initialized walk.

In backward reasoning, we must account for the execution that follows the call. Suppose the first call takes either one or three iterations. Including the step spent entering the outer body, these executions reach the outer guard after two or four iterations. If the remaining execution takes tt further iterations, their total runtimes are 2+t2+t and 4+t4+t. Although both executions continue with the same code, an observation of their total runtime must account for the different amounts of time already spent.

This gives the third design requirement: the representation must support composition. Propagating a postcondition backward through a call must account for its possible runtimes and yield a precondition of the same form, allowing the same rules to be reused through further commands and enclosing loops. In a general quantum program, the remaining execution also depends on the quantum state produced by the call. Reasoning about the continuation must therefore retain the dependence between runtime and output state. We seek parameterized predicates that carry this information through program composition and support the quantitative questions raised by the walk.

Runtime Semantics and Parameterized Predicates

To reason compositionally about both runtime and quantum state transformations, we refine the standard denotational semantics ⟦S⟧\llbracket S \rrbracket of a quantum program SS into runtime-graded completely positive maps ⟦S⟧rt=(⟦S⟧n)n≥0\llbracket S \rrbracket_{\mathrm{rt}} = (\llbracket S \rrbracket_n)_{n \ge0} and test them against scale-indexed families of bounded effects F=(Fs)s>0F = (F_s)_{s > 0}.

Programs and Their Runtime-Graded Semantics

Fix a finite set Var\mathrm{Var} of quantum variables. Each variable qq has a separable Hilbert space Hq\mathcal{H}_q, possibly infinite-dimensional, and a distinguished unit vector ∣0⟩q\lvert0 \rangle_q. The joint space and its partial density operators are

H≜⨂q∈VarHq,D(H)≜{ρ∈T(H):ρ≥0, tr⁡(ρ)≤1}.\mathcal{H} \triangleq\bigotimes_{q \in\mathrm{Var}} \mathcal{H}_q,\qquad\mathcal{D}(\mathcal{H}) \triangleq\{ \rho\in\mathcal{T}(\mathcal{H}) : \rho\ge0,\ \operatorname{tr}(\rho) \le1 \}.

Here T(H)\mathcal{T}(\mathcal{H}) is the space of trace-class operators. Following standard quantum while-language conventions [50, 59], programs are generated by

S::=skip⁡∣abort⁡∣q:=∣0⟩∣qˉ:=U[qˉ]∣S1;S2∣if⁡(□i∈JM[qˉ]=i→Si)fi⁡∣while⁡ M[qˉ]=1 do⁡ B od⁡.S ::= \operatorname{skip} \mid\operatorname{abort} \mid q := \lvert0 \rangle\mid\bar{q} := U[\bar{q}] \mid S_1; S_2 \mid\operatorname{if}\left(\Box_{i \in J} M[\bar{q}] = i \to S_i\right)\operatorname{fi} \mid\operatorname{while}\ M[\bar{q}] = 1\ \operatorname{do}\ B\ \operatorname{od}.

Here UU is unitary, and operators on a subsystem are extended by the identity on the remaining variables. Initialization resets qq to ∣0⟩q\lvert0 \rangle_q. A conditional measurement has a finite outcome set JJ and satisfies ∑i∈JMi†Mi=I\sum_{i \in J} M_i^\dagger M_i = I. A loop uses a binary measurement: outcome zero exits, and outcome one enters the body.

Mi(ρ)≜MiρMi†,Rq(ρ)≜∣0⟩⟨0∣q⊗tr⁡q(ρ),Uqˉ(ρ)≜UρU†.\mathcal{M}_i(\rho) \triangleq M_i \rho M_i^\dagger,\qquad\mathcal{R}_q(\rho) \triangleq\lvert0 \rangle\langle0 \rvert_q \otimes\operatorname{tr}_q(\rho),\qquad\mathcal{U}_{\bar{q}}(\rho) \triangleq U \rho U^\dagger.

Definition 3.1 (Runtime-graded denotational semantics). The runtime-graded denotational semantics of a program SS is the sequence

⟦S⟧rt≜(⟦S⟧n)n≥0,⟦S⟧n:T(H)→T(H),\llbracket S \rrbracket_{\mathrm{rt}} \triangleq(\llbracket S \rrbracket_n)_{n \ge0},\qquad\llbracket S \rrbracket_n : \mathcal{T}(\mathcal{H}) \to\mathcal{T}(\mathcal{H}),

where the grade-nn map ⟦S⟧n\llbracket S \rrbracket_n produces the subnormalized output state of executions terminating after exactly nn total loop-body entries (accumulating iterations across nested loops, while loop exits and loop-free commands contribute zero). For n≥0n \ge0, the grades are defined by

⟦skip⁡⟧n=1{n=0}id⁡,⟦abort⁡⟧n=0,\llbracket\operatorname{skip} \rrbracket_n = 1_{\{n=0\}}\operatorname{id},\qquad\llbracket\operatorname{abort} \rrbracket_n = 0,
⟦q:=∣0⟩⟧n=1{n=0}Rq,⟦qˉ:=U[qˉ]⟧n=1{n=0}Uqˉ,\llbracket q := \lvert0 \rangle\rrbracket_n = 1_{\{n=0\}}\mathcal{R}_q,\qquad\llbracket\bar{q} := U[\bar{q}] \rrbracket_n = 1_{\{n=0\}}\mathcal{U}_{\bar{q}},
⟦S1;S2⟧n=∑a+b=n⟦S2⟧b∘⟦S1⟧a,\llbracket S_1; S_2 \rrbracket_n = \sum_{a+b=n} \llbracket S_2 \rrbracket_b \circ\llbracket S_1 \rrbracket_a,
⟦if⁡(□iM[qˉ]=i→Si)fi⁡⟧n=∑i⟦Si⟧n∘Mi,\llbracket\operatorname{if}\left(\Box_i M[\bar{q}] = i \to S_i\right)\operatorname{fi} \rrbracket_n = \sum_i \llbracket S_i \rrbracket_n \circ\mathcal{M}_i,
⟦while⁡ M[qˉ]=1 do⁡ B od⁡⟧n=∑j=0n ∑k1,…,kj∈N+k1+⋯+kj=nM0∘Ckj∘⋯∘Ck1.(1)\llbracket\operatorname{while}\ M[\bar{q}] = 1\ \operatorname{do}\ B\ \operatorname{od} \rrbracket_n = \sum_{j=0}^{n}\ \sum_{\substack{k_1,\ldots,k_j \in\mathbb{N}_+\\ k_1+\cdots+k_j=n}} \mathcal{M}_0 \circ\mathcal{C}_{k_j} \circ\cdots\circ\mathcal{C}_{k_1}. \tag*{(1)}

References

  1. [1]Sheshansh Agrawal, Krishnendu Chatterjee, and Petr Novotný. 2018. Lexicographic Ranking Supermartingales: An Efficient Approach to Termination of Probabilistic Programs. Proceedings of the ACM on Programming Languages 2, POPL, Article 34 (2018), 32 pages. doi:10.1145/3158122DOI
  2. [2]Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani. 2001. Quantum walks on graphs. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC ’01). Association for Computing Machinery, New York, NY, USA, 50–59. doi:10.1145/380752.380758DOI
  3. [3]Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, and John Watrous. 2001. One-dimensional quantum walks. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC ’01). Association for Computing Machinery, New York, NY, USA, 37–49. doi:10.1145/380752.380757DOI
  4. [4]Martin Avanzini, Georg Moser, Romain Péchoux, Simon Perdrix, and Vladimir Zamdzhiev. 2022. Quantum Expectation Transformers for Cost Analysis. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS ’22). Association for Computing Machinery, New York, NY, USA, Article 10, 13 pages. doi:10.1145/3531130.3533332DOI
  5. [5]Eric Bach, Susan Coppersmith, Marcel Paz Goldschen, Robert Joynt, and John Watrous. 2004. One-dimensional quantum walks with absorbing boundaries. J. Comput. Syst. Sci. 69, 4 (2004), 562–592. doi:10.1016/j.jcss.2004.03.005DOI
  6. [6]Gilles Barthe, Justin Hsu, Mingsheng Ying, Nengkun Yu, and Li Zhou. 2020. Relational Proofs for Quantum Programs. Proceedings of the ACM on Programming Languages 4, POPL, Article 21 (2020), 29 pages. doi:10.1145/3371089DOI
  7. [7]Aleksandar Chakarov and Sriram Sankaranarayanan. 2013. Probabilistic Program Analysis with Martingales. In Computer Aided Verification (Lecture Notes in Computer Science, Vol. 8044). Springer, Berlin, Heidelberg, 511–526. doi:10.1007/978-3-642-39709-8_34DOI
  8. [8]Krishnendu Chatterjee, Hongfei Fu, Petr Novotný, and Rouzbeh Hashemi­nezhad. 2018. Algorithmic Analysis of Qualitative and Quantitative Termination Problems for Affine Probabilistic Programs. ACM Transactions on Programming Languages and Systems 40, 2, Article 7 (2018), 45 pages. doi:10.1145/3174800DOI
  9. [9]Krishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, and Dordě Zikelić. 2022. Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic Programs. In Computer Aided Verification (Lecture Notes in Computer Science, Vol. 13371). Springer, Cham, Switzerland, 55–78. doi:10.1007/978-3-031-13185-1_4DOI
  10. [10]Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Petr Novotný, Jiří Zárevúcky, and Dordě Zikelić. 2021. On Lexicographic Proof Rules for Probabilistic Termination. In Formal Methods (Lecture Notes in Computer Science, Vol. 13047). Springer, Cham, Switzerland, 619–639. doi:10.1007/978-3-030-90870-6_33DOI
  11. [11]Krishnendu Chatterjee, Petr Novotný, and Dordě Zikelić. 2017. Stochastic Invariants for Probabilistic Termination. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2017). Association for Computing Machinery, New York, NY, USA, 145–160. doi:10.1145/3009837.3009873DOI
  12. [12]Mingshuai Chen, Joost-Pieter Katoen, Lutz Klinkenberg, and Tobias Winkler. 2022. Does a Program Yield the Right Distribution? Verifying Probabilistic Programs via Generating Functions. In Computer Aided Verification (Lecture Notes in Computer Science, Vol. 13371). Springer, Cham, Switzerland, 79–101. doi:10.1007/978-3-031-13185-1_5DOI
  13. [13]Feifei Cheng, Sushen Vangee­puram, Henry Allard, Seyed Mohammad Reza Jafari, Alex Potanin, and Liyi Li. 2025. Embedding Quantum Program Verification into Dafny. Proceedings of the ACM on Programming Languages 9, OOPSLA2, Article 379 (2025), 27 pages. doi:10.1145/3763157DOI
  14. [14]Andrew M. Childs. 2009. Universal Computation by Quantum Walk. Physical Review Letters 102, 18 (2009), 180501. doi:10.1103/PhysRevLett.102.180501DOI
  15. [15]Andrew M. Childs, David Gosset, and Zak Webb. 2013. Universal Computation by Multiparticle Quantum Walk. Science 339, 6121 (2013), 791–794. doi:10.1126/science.1229957DOI
  16. [16]Patrick Cousot and Radhia Cousot. 1977. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL ’77). Association for Computing Machinery, New York, NY, USA, 238–252. doi:10.1145/512950.512973DOI
  17. [17]Ellie D’Hondt and Prakash Panangaden. 2006. Quantum weakest preconditions. Mathematical Structures in Computer Science 16, 3 (2006), 429–451. doi:10.1017/S0960129506005251DOI
  18. [18]B. L. Douglas and J. B. Wang. 2009. Efficient quantum circuit implementation of quantum walks. Physical Review A 79, 5 (2009), 052335. doi:10.1103/PhysRevA.79.052335DOI
  19. [19]Yuan Feng, Nengkun Yu, and Mingsheng Ying. 2013. Model checking quantum Markov chains. J. Comput. System Sci. 79, 7 (2013), 1181–1198. doi:10.1016/j.jcss.2013.04.002DOI
  20. [20]Yuan Feng, Nengkun Yu, and Mingsheng Ying. 2013. Reachability Analysis of Recursive Quantum Markov Chains. In Mathematical Foundations of Computer Science 2013 (Lecture Notes in Computer Science, Vol. 8087). Springer, Berlin, Heidelberg, 385–396. doi:10.1007/978-3-642-40313-2_35DOI
  21. [21]Christina Gehnen, Dominique Unruh, and Joost-Pieter Katoen. 2026. Quantum weakest preconditions revisited: Pre-expectations for expected runtime analysis. arXiv:2607.12532 doi:10.48550/arXiv.2607.12532DOI
  22. [22]Hugo Gimbert and Wieslaw Zielonka. 2007. Limits of Multi-Discounted Markov Decision Processes. In Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007). IEEE Computer Society, 89–98. doi:10.1109/LICS.2007.28DOI
  23. [23]Ji Guan, Yuan Feng, and Mingsheng Ying. 2018. Decomposition of quantum Markov chains and its applications. J. Comput. System Sci. 95 (2018), 55–68. doi:10.1016/j.jcss.2018.01.005DOI
  24. [24]Darion Haase, Kevin Batz, Adrian Gallus, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Lutz Klinkenberg, and Tobias Winkler. 2026. Generating Functions Meet Occupation Measures: Invariant Synthesis for Probabilistic Loops. In Programming Languages and Systems (Lecture Notes in Computer Science, Vol. 16501). Springer, Cham, Switzerland, 314–343. doi:10.1007/978-3-032-22720-1_12DOI
  25. [25]Frank Hansen and Gert K. Pedersen. 2003. Jensen’s operator inequality. Bulletin of the London Mathematical Society 35, 4 (2003), 553–564. doi:10.1112/S0024609303002200DOI
  26. [26]Marcel Hark, Benjamin Lucien Kaminski, Jürgen Giesl, and Joost-Pieter Katoen. 2020. Aiming Low Is Harder: Induction for Lower Bounds in Probabilistic Program Verification. Proceedings of the ACM on Programming Languages 4, POPL, Article 37 (2020), 28 pages. doi:10.1145/3371105DOI
  27. [27]Benjamin Lucien Kaminski, Joost-Pieter Katoen, Christoph Matheja, and Federico Olmedo. 2018. Weakest Precondition Reasoning for Expected Runtimes of Randomized Algorithms. J. ACM 65, 5, Article 30 (2018), 68 pages. doi:10.1145/3208102DOI
  28. [28]Lutz Klinkenberg, Kevin Batz, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Joshua Moerman, and Tobias Winkler. 2021. Generating Functions for Probabilistic Programs. In Logic-Based Program Synthesis and Transformation (Lecture Notes in Computer Science, Vol. 12561). Springer, Cham, Switzerland, 231–248. doi:10.1007/978-3-030-68446-4_12DOI
  29. [29]Lutz Klinkenberg, Christian Blumenthal, Mingshuai Chen, Darion Haase, and Joost-Pieter Katoen. 2024. Exact Bayesian Inference for Loopy Probabilistic Programs using Generating Functions. Proceedings of the ACM on Programming Languages 8, OOPSLA1, Article 127 (2024), 31 pages. doi:10.1145/3649844DOI
  30. [30]Norio Konno, Takao Namiki, Takahiro Soshi, and Aidan Sudbury. 2003. Absorption problems for quantum walks in one dimension. Journal of Physics A: Mathematical and General 36, 1 (2003), 241–253. doi:10.1088/0305-4470/36/1/3096
  31. [31]Hari Krovi and Todd A. Brun. 2006. Hitting time for quantum walks on the hypercube. Physical Review A 73, 3 (2006), 032341. doi:10.1103/PhysRevA.73.032341DOI
  32. [32]Hari Krovi and Todd A. Brun. 2006. Quantum walks with infinite hitting times. Physical Review A 74, 4 (2006), 042334. doi:10.1103/PhysRevA.74.042334DOI
  33. [33]Satoshi Kura, Natsuki Urabe, and Ichiro Hasuo. 2019. Tail Probabilities for Randomized Program Runtimes via Martingales for Higher Moments. In Tools and Algorithms for the Construction and Analysis of Systems (Lecture Notes in Computer Science, Vol. 11428). Springer, Cham, Switzerland, 135–153. doi:10.1007/978-3-030-17465-1_8DOI
  34. [34]Liyi Li, Mingwei Zhu, Rance Cleaveland, Alexander Nicollin, Yi Lee, Le Chang, and Xiaodi Wu. 2024. Qafny: A Quantum-Program Verifier. In 38th European Conference on Object-Oriented Programming (ECOOP 2024) (Leibniz International Proceedings in Informatics, Vol. 313). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 24:1–24:31. doi:10.4230/LIPIcs.ECOOP.2024.24
  35. [35]Yangjia Li and Mingsheng Ying. 2018. Algorithmic Analysis of Termination Problems for Quantum Programs. Proceedings of the ACM on Programming Languages 2, POPL, Article 35 (2018), 29 pages. doi:10.1145/3158123DOI
  36. [36]Yangjia Li, Nengkun Yu, and Mingsheng Ying. 2014. Termination of nondeterministic quantum programs. Acta Informatica 51, 1 (2014), 1–24. doi:10.1007/s00236-013-0185-3DOI
  37. [37]Junyi Liu, Li Zhou, Gilles Barthe, and Mingsheng Ying. 2025. Quantum Weakest Preconditions for Reasoning about Expected Runtimes of Quantum Programs. J. ACM 72, 3, Article 20 (2025), 51 pages. doi:10.1145/3734516DOI
  38. [38]T. Loke and J. B. Wang. 2012. Efficient circuit implementation of quantum walks on non-degree-regular graphs. Physical Review A 86, 4 (2012), 042338. doi:10.1103/PhysRevA.86.042338DOI
  39. [39]T. Loke and J. B. Wang. 2017. Efficient quantum circuits for Szegedy quantum walks. Annals of Physics 382 (2017), 64–84. doi:10.1016/j.aop.2017.04.006DOI
  40. [40]Annabelle McIver and Carroll Morgan. 2005. Abstraction, Refinement and Proof for Probabilistic Systems. Springer, New York, NY, USA. doi:10.1007/b138392
  41. [41]Annabelle McIver, Carroll Morgan, Benjamin Lucien Kaminski, and Joost-Pieter Katoen. 2018. A New Proof Rule for Almost-Sure Termination. Proceedings of the ACM on Programming Languages 2, POPL, Article 33 (2018), 28 pages. doi:10.1145/3158121
  42. [42]Luca Razzoli, Gabriele Cenedese, Maria Bondani, and Giuliano Benenti. 2024. Efficient Implementation of Discrete-Time Quantum Walks on Quantum Computers. Entropy 26, 4, Article 313 (2024), 24 pages. doi:10.3390/e26040313DOI
  43. [43]Michael Reed and Barry Simon. 1980. Methods of Modern Mathematical Physics. I: Functional Analysis (revised and enlarged ed.). Academic Press. ISBN 0-12-585050-6. https://shop.elsevier.com/books/i-functional-analysis/reed/978-0-08-057048-8
  44. [44]Asif Shakeel. 2020. Efficient and scalable quantum walk algorithms via the quantum Fourier transform. Quantum Information Processing 19, 9 (2020), 323. doi:10.1007/s11128-020-02834-yDOI
  45. [45]Barry Simon. 1978. A canonical decomposition for quadratic forms with applications to monotone convergence theorems. Journal of Functional Analysis 28, 3 (1978), 377–385. doi:10.1016/0022-1236(78)90094-0
  46. [46]Gábor Szegő. 1975. Orthogonal Polynomials (fourth ed.). American Mathematical Society Colloquium Publications, Vol. 23. American Mathematical Society, Providence, RI. ISBN 9780821810231. doi:10.1090/coll/023
  47. [47]Jeffrey Scott Vitter and Philippe Flajolet. 1990. Average-Case Analysis of Algorithms and Data Structures. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, Jan van Leeuwen (Ed.). Elsevier, 431–524. doi:10.1016/B978-0-444-88071-0-50014-XDOI
  48. [48]Di Wang, Jan Hoffmann, and Thomas Reps. 2021. Central Moment Analysis for Cost Accumulators in Probabilistic Programs. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2021). Association for Computing Machinery, New York, NY, USA, 559–573. doi:10.1145/3453483.3454062DOI
  49. [49]Ming Xu, Jianling Fu, Hui Jiang, Yuxin Deng, and Zhi-Bin Li. 2024. Termination and Universal Termination Problems for Nondeterministic Quantum Programs. ACM Transactions on Software Engineering and Methodology 33, 8, Article 219 (2024), 41 pages. doi:10.1145/3691632DOI
  50. [50]Mingsheng Ying. 2011. Floyd–Hoare logic for quantum programs. ACM Transactions on Programming Languages and Systems 33, 6, Article 19 (2011), 49 pages. doi:10.1145/2049706.2049708DOI
  51. [51]Mingsheng Ying and Yuan Feng. 2010. Quantum loop programs. Acta Informatica 47, 4 (2010), 221–250. doi:10.1007/s00236-010-0117-4DOI
  52. [52]Mingsheng Ying, Yangjia Li, Nengkun Yu, and Yuan Feng. 2014. Model-Checking Linear-Time Properties of Quantum Systems. ACM Transactions on Computational Logic 15, 3, Article 22 (2014), 31 pages. doi:10.1145/2629680DOI
  53. [53]Mingsheng Ying, Nengkun Yu, Yuan Feng, and Runyao Duan. 2013. Verification of quantum programs. Science of Computer Programming 78, 9 (2013), 1679–1700. doi:10.1016/j.scico.2013.03.016DOI
  54. [54]Shenggang Ying, Yuan Feng, Nengkun Yu, and Mingsheng Ying. 2013. Reachability Probabilities of Quantum Markov Chains. In CONCUR 2013 – Concurrent Theory (Lecture Notes in Computer Science, Vol. 8052). Springer, Berlin, Heidelberg, 334–348. doi:10.1007/978-3-642-40184-8_24DOI
  55. [55]Shenggang Ying and Mingsheng Ying. 2018. Reachability analysis of quantum Markov decision processes. Information and Computation 263 (2018), 31–51. doi:10.1016/j.ic.2018.09.001DOI
  56. [56]Nengkun Yu. 2023. Structured Theorem for Quantum Programs and its Applications. ACM Transactions on Software Engineering and Methodology 32, 4, Article 103 (2023), 35 pages. doi:10.1145/3587154DOI
  57. [57]Nengkun Yu. 2024. Quantum temporal logic and reachability problems of matrix semigroups. Information and Computation 300 (2024), 105197. doi:10.1016/j.ic.2024.105197DOI
  58. [58]Nengkun Yu and Mingsheng Ying. 2012. Reachability and Termination Analysis of Concurrent Quantum Programs. In CONCUR 2012 – Concurrency Theory (Lecture Notes in Computer Science, Vol. 7454). Springer, Berlin, Heidelberg, 69–83. doi:10.1007/978-3-642-32940-1_7DOI
  59. [59]Tianshi Yu, Gilles Barthe, Minbo Gao, Mingsheng Ying, and Li Zhou. 2026. Reasoning about continuous-variable quantum systems. arXiv:2607.23137v2 doi:10.48550/arXiv.2607.23137DOI

Paper details

vlnc:W_x8td2cqe
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra

View statement
Looking for related papers…
Contents