constructive mathematics, realizability, computability
propositions as types, proofs as programs, computational trinitarianism
quantum algorithms:
In quantum computing (but the idea applies generally to nondeterministic computation), repeat-until-success [Shah & Oi (2013), Lim, Beige & Kwek (2005)] is a computation scheme where a given non-deterministic logic gate is re-applied to its given input data until a failure syndrome vanishes to indicate that the desired kind of gate operation has been performed.
Concretely, in quantum computation this means that a quantum logic gate is executed followed by quantum measurement of parts of its output data, and depending on this measurement either the remaining quantum state output is accepted and forwarded to the next logic gate in the quantum circuit, or else the result is uncomputed? and the procedure repeated.
While it has been shown [Lim, Beige & Kwek (2005)] that such repeat-until-success gates may be efficient (as they can avoid use of gate elements which yield guaranteed outcomes but at a high resource cost), they fall out of the plain quantum logic circuit scheme in that the nature and even the number of quantum gates being executed depends on classical control measurement results known only at runtime (i.e. on “dynamic lifting” of measurement results back into the classical context).
Phrased differently, repeat-until-success algorithms do have a generalized quantum circuit-description, but involving an infinite number of “wires” (since it may take arbitrarily long until the failure syndrome vanishes).
Kerem Halil Shah, Daniel Kuan Li Oi, Ancilla Driven Quantum Computation with arbitrary entangling strength, Theory of Quantum Computation 22 (2013) [arXiv:1303.2066, doi:10.4230/LIPIcs.TQC.2013.1]
Yuan Liang Lim, Almut Beige, Leong Chuan Kwek, Repeat-Until-Success Quantum Computing, Phys. Rev. Lett. 95 (2005) 030505 [doi:10.1103/PhysRevLett.95.030505, arXiv:quant-ph/0408043]
Yuan Liang Lim, Sean D. Barrett, Almut Beige, Pieter Kok, Leong Chuan Kwek, Repeat-Until-Success quantum computing using stationary and flying qubits, Phys. Rev. A 73 (2006) 012304 [arXiv:quant-ph/0508218, doi:10.1103/PhysRevA.73.012304]
Adam Paetznick, Krysta M. Svore, Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries, Quantum Information & Computation 14 15-16 (2014) 1277-1301 [arXiv:1311.1074, doi:10.5555/2685179.2685181]
Discussion of the setup where “fail” (non-success) is guaranteed to act as the identity on the input quantum states (“success or draw”)
On repeat-until-success algorithms for creating “quantum imaginary time evolution”:
Review:
Last revised on December 12, 2022 at 09:02:05. See the history of this page for a list of all contributions to it.