  When preparing a pure state with a quantum circuit, there is an unavoidable
approximation error due to the compilation error in fault-tolerant
implementation. A recently proposed approach called probabilistic state
synthesis, where the circuit is probabilistically sampled, is able to reduce
the approximation error compared to conventional deterministic synthesis. In
this paper, we demonstrate that the optimal probabilistic synthesis
quadratically reduces the approximation error. Moreover, we show that a
deterministic synthesis algorithm can be efficiently converted into a
probabilistic one that achieves this quadratic error reduction. We also
numerically demonstrate how this conversion reduces the $T$-count and
analytically prove that this conversion halves an information-theoretic lower
bound on the circuit size. In order to derive these results, we prove general
theorems about the optimal convex approximation of a quantum state.
Furthermore, we demonstrate that this theorem can be used to analyze an
entanglement measure.
