Search

The problems of quantum state preparation and matrix block-encoding are ubiquitous in quantum computing: they are crucial parts of various quantum algorithms for the purpose for initial state preparation as well as loading problem relevant data. We first present an algorithm based on QRS that prepares a quantum state $|\psi_f\rangle \propto \sum^N_{x=1} f(x)|x\rangle$. When combined with efficient reference states the algorithm reduces the cost of quantum state preparation substantially, if certain criteria on $f$ are met. When the preparation of the reference state is not the dominant cost, and the function $f$ and relevant properties are efficiently computable or provided otherwise with cost $o(N)$, the QRS-based method outperforms the generic state preparation algorithm, which has cost $O(N)$. We demonstrate the detailed performance (in terms of the number of Toffoli gates) of the QRS-based algorithm for quantum states commonly appearing in quantum applications, e.g., those with coefficients that obey power law decay, Gaussian, and hyperbolic tangent, and compare it with other methods. Then, we adapt QRS techniques to the matrix block-encoding problem and introduce a QRS-based algorithm for block-encoding a given matrix $A = \sum_{ij} A_{ij} |i\rangle \langle j|$. We work out rescaling factors for different access models, which encode how the information about the matrix is provided to the quantum computer. We exemplify these results for a particular Toeplitz matrix with elements $A_{{\mathbf{ij}}}= 1/\|{\mathbf{i}}-{\mathbf{j}}\|^2$, which appears in quantum chemistry, and PDE applications, e.g., when the Coulomb interaction is involved. Our work unifies, and in certain ways goes beyond, various quantum state preparation and matrix block-encoding methods in the literature, and gives detailed performance analysis of important examples that appear in quantum applications., Comment: 58 pages, 28 figures, 5 tables

We introduce a framework for fault-tolerant post-selection (FTPS) of fault-tolerant codes and channels -- such as those based on surface-codes -- using soft-information metrics based on visible syndrome and erasure information. We introduce several metrics for ranking configurations of syndromes and erasures. In particular, we introduce the \emph{logical gap} (and variants thereof) as a powerful soft-information metric for predicting logical error rates of fault-tolerant channels based on topological error-correcting codes. The logical gap is roughly the unsigned weight difference between inequivalent logical corrections and is adaptable to any tailored noise model or decoder. We deploy this framework to prepare high-quality surface code magic states with low overhead under a model of independent and identically distributed (\emph{i.i.d.}) Pauli and erasure errors. Post-selection strategies based on the logical gap can suppress the encoding error rate of a magic state preparation channel to the level of the physical error rate with low overhead. For example, when operating at $60\%$ the bulk threshold of the corresponding surface code, an overall reduction of the encoding error rate by a factor of $15$ is achievable with a relative overhead factor of ${< 2}$ (approximately $23$ times less than that of simple syndrome-counting rules). We analyze a schematic buffer architecture for implementing post-selection rules on magic state factories in the context of magic state distillation. The FTPS framework can be utilized for mitigating errors in more general fault-tolerant logical channels., Comment: 10+7 pages, 13 figures, comments welcome