EFFICIENT SYNTHESIS OF PROBABILISTIC QUANTUM CIRCUITS WITH FALLBACK

A Probabilistic Quantum Circuit with Fallback (PQFs) is composed as a series of circuit stages that are selected to implement a target unitary. A final stage is conditioned on unsuccessful results of all the preceding stages as indicated by measurement of one or more ancillary qubits. This final stage executes a fallback circuit that enforces deterministic execution of the target unitary at a relatively high cost (mitigated by very low probability of the fallback). Specific instances of general PQF synthesis method and are disclosed with reference to the specific Clifford+T, Clifford+V and Clifford+π/12 bases. The resulting circuits have expected cost in logb(1/ε)+O(log(log(1/ε)))+const wherein b is specific to each basis. The three specific instances of the synthesis have polynomial compilation time guarantees.