Success-or-Draw: A Strategy Allowing Repeat-Until-Success in Quantum Computation

The repeat-until-success strategy is a standard method to obtain success with a probability that grows exponentially with the number of iterations. However, since quantum systems are disturbed after a quantum measurement, how to perform repeat-until-success strategies in certain quantum algorithms is not straightforward. In this Letter, we propose a new structure for probabilistic higher-order transformation named success-or-draw, which allows a repeat-until-success implementation. For that we provide a universal construction of success-or-draw structure that works for any probabilistic higher-order transformation on unitary operations. We then present a semidefinite programming approach to obtain optimal success-or-draw protocols and analyze in detail the problem of inverting a general unitary operation.

Figure 1

Success-or-draw supermaps are ones in which, when the supermap fails, the output state remains the same as the initial state. Since the initial state is not altered on failure, one can reiterate this protocol to obtain an exponentially decreasing failure probability. Panel (a) represents the action of a success-or-draw supermap: when it succeeds, the target operation $f(U)$ is obtained; and when it draws, the identity operation $id$ is obtained. Panel (b) illustrates a repeat-until-success protocol that is allowed for a success-or-draw protocol.

Figure 2

A pictorial interpretation of Theorem 1. We consider the case in which there exists a probabilistic comb (upper) that transforms unitary operations $U$ into CPTP maps $f(U)$, whose action is arbitrary on failure. Theorem 1 states that in this case, there exists a $d$-slot probabilistic comb (lower) that performs the same action on success, and performs the identity operation on failure/draw, which corresponds to the preservation of the input state.

Figure 3

The constructed success-or-draw comb in Supplemental Material [25] has an extra structure: it uses one copy of the unitary operation at first, and then uses the remaining $d-1$ copy of the unitary operation in parallel.

Figure 4

The success-or-draw protocol for unitary inversion. When the unitary operation can be used twice, the optimal probability for success is $1/3$, whereas that of the optimal success-or-resetting protocol is $1/4$. In either case, the output on failure is the identity operation, which means the initial input state is preserved and it is possible to run the same protocol again with extra uses of the input unitary operation.