Constant-optimized quantum circuits for modular multiplication and exponentiation

Igor L. Markov, Mehdi Saeedi · 2012 · Quantum Information and Computation 12(5-6)

| 编号 QM009 | 主题 模运算与乘法 | 链接 DOI 10.26421/qic12.5-6-1 |

摘要

摘要保留原文（英文）

摘要取自 Crossref 出版方元数据，未作翻译，以保证与原文一致。

Reversible circuits for modular multiplication $Cx\%M$ with $x<M$ arise as components of modular exponentiation in Shor’s quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific $C$ and $M$ values. In this work, we develop such optimizations in a bottom-up fashion, starting with most convenient $C$ values. When zero-initialized ancilla registers are available, we reduce the search for compact circuits to a shortest-path problem. Some of our modular-multiplication circuits are asymptotically smaller than previous constructions, but worst-case bounds and average sizes remain $\Theta (n^2)$. In the context of modular exponentiation, we offer several constant-factor improvements, as well as an improvement by a constant additive term that is significant for few-qubit circuits arising in ongoing laboratory experiments with Shor’s algorithm.

本站词条在引用该文献时，会以 wikilink（sources/QM009）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。