机构名称：
¥ 2.0
摘要：Shor 算法在多项式时间内解决了椭圆曲线离散对数问题 (ECDLP)。为了优化二进制椭圆曲线的 Shor 算法，降低二进制域乘法的成本至关重要，因为它是最昂贵的基本算法。在本文中，我们提出了用于二进制域 (F 2 n) 乘法的 Toffoli 门数优化的空间高效量子电路。为此，我们利用类 Karatsuba 公式并证明其应用可以在没有辅助量子位的情况下提供，并在 CNOT 门和深度方面对其进行了优化。基于类 Karatsuba 公式，我们驱动了一种空间高效的基于 CRT 的乘法，该乘法采用两种非原地乘法算法来降低 CNOT 门成本。我们的量子电路不使用辅助量子位，并且 TOF 门数极低，为 O ( n 2 log ∗ 2 n )，其中 log ∗ 2 是一个增长非常缓慢的迭代对数函数。与最近基于 Karatsuba 的空间高效量子电路相比，我们的电路仅需要 Toffoli 门数的 (12 ∼ 24%)，且加密字段大小 ( n = 233 ∼ 571 ) 具有可比深度。据我们所知，这是第一个在量子电路中使用类似 Karatsuba 的公式和基于 CRT 的乘法的结果。
用于二进制场乘法的 Toffoli 门数优化的空间高效量子电路
主要关键词
相关文件推荐
