nLab repeat-until-success computing

Contents

Context

Computation

Quantum systems

quantum logic


quantum physics


quantum probability theoryobservables and states


quantum information


quantum computation

quantum algorithms:

Contents

Idea

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).

References

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.