Probabilistic unitary synthesis with optimal accuracy

Abstract

The purpose of unitary synthesis is to find a gate sequence that optimally approximates a target unitary transformation. A new synthesis approach, called probabilistic synthesis, has been introduced, and its superiority has been demonstrated over traditional deterministic approaches with respect to approximation error and gate length. However, the optimality of current probabilistic synthesis algorithms is unknown. We obtain the tight lower bound on the approximation error obtained by the optimal probabilistic synthesis, which guarantees the sub-optimality of current algorithms. We also show its tight upper bound, which improves and unifies current upper bounds depending on the class of target unitaries. These two bounds reveal the fundamental relationship of approximation error between probabilistic approximation and deterministic approximation of unitary transformations. From a computational point of view, we show that the optimal probability distribution can be computed by the semidefinite program (SDP) we construct. We also construct an efficient probabilistic synthesis algorithm for single-qubit unitaries, rigorously estimate its time complexity, and show that it reduces the approximation error quadratically compared with deterministic algorithms.

27 pages, 6 figures

References in corpus (18)

• Fault-tolerant quantum computation by anyons
• Entanglement of a Pair of Quantum Bits
• Quantum Error Correction for Quantum Memories
• Quantum Resource Theories
• Theoretical framework for quantum networks
• The general structure of quantum resource theories
• Resilient Quantum Computation: Error Models and Thresholds
• (Quantumness in the context of) Resource Theories
• Efficient synthesis of universal Repeat-Until-Success circuits
• Toward a general theory of quantum games
• Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits
• Efficient Discrete Approximations of Quantum Gates
• Factorization and dilation problems for completely positive maps on von Neumann algebras
• Practical approximation of single-qubit unitaries by single-qubit quantum Clifford and T circuits
• Shorter gate sequences for quantum computing by mixing unitaries
• Shorter quantum circuits via single-qubit gate approximation
• Convex approximations of quantum channels
• Optimal convex approximations of quantum states

Cited by in corpus (4)

• Halving the Cost of Quantum Algorithms with Randomization
• Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization
• Error Crafting in Mixed Quantum Gate Synthesis
• Averaging gate approximation error and performance of Unitary Coupled Cluster ansatz in Pre-FTQC Era