椭圆曲线离散对数求解量子算法的线路优化

OPTIMIZATION FOR THE QUANTUM CIRCUIT OF ELLIPTIC CURVE DISCRETE LOGARITHMS

  • 摘要: 该文借助加密技术和整数取模的降集表示技术,在加法的近似编码表示基础上给出了椭圆曲线群上离散对数求解量子线段的整体优化和资源估计,并对设计的量子线路进行了仿真实验。借助加密技术和整数取模的降集表示技术可以有效降低T门的数目以及T门深度,其中T门数目为32n³ + O(n²log n),T门深度为12n³ + O(n²log n)。由于采用加密的半经典傅里叶变换,使得空间资源代价为8n + O(log n)个量子比特。该文在增加少量近似误差(误差可以随着填充数目增加且指数降低)的前提下,实现了时间空间资源代价的折中。

     

    Abstract: With the help of techniques such as windowed arithmetic and the coset representation of modular integers, the overall optimization and resource estimation for the quantum circuit of elliptic curve discrete logarithms Shor's algorithm was shown. The simulation experiment of the designed quantum circuit was carried out. The T gate and the depth of the overall circuit could be reduced by techniques such as windowed arithmetic and the coset representation of modular integers. The T count was 32n³ + O(n²log n) and the measurement depth was 12n³ + O(n²log n). Due to the windowed semiclassical Fourier transform, the space usage included 8n + O(log n) logical qubits. This paper achieved a trade-off between time, space, and resource costs while introducing only a small approximation error (which could exponentially decrease with the increase in the number of padding elements).

     

/

返回文章
返回