Cooking with quantum gas

C. Di Castro, Roberto Raimondi

Rini Wisnu Wardhani, Dedy Septono Catur Putranto

This paper studies the asymptotic bounds of quantum resources required for high-degree multiplication based on the Toom–Cook algorithm. This work extends prior investigations on high- and half-degree quantum multiplication and proposes an optimized Toom–Cook 25.5-way quantum multiplication architecture to establish optimal asymptotic bounds on quantum resource consumption for Toom–Cook-based multiplication schemes. We provide asymptotic expressions for qubit complexity, Toffoli gate count, and Toffoli depth. The proposed Toom–Cook 25.5-way architecture achieves improved asymptotic performance, requiring a qubit count of n1.176, approximately 648nlog2651 − 666n Toffoli count, and n1.03025 Toffoli depth. Compared with existing classical and quantum Toom–Cook-based methods, the proposed 25.5-way Toom–Cook algorithm achieves lower asymptotic complexity and reduced quantum resource costs, yielding tighter bounds for optimal quantum multiplication.

Rini Wisnu Wardhani, Dedy Septono Catur Putranto, Howon Kim

This paper provides a thorough examination of strategies related to the design of the polynomial multiplication approach, which is essential to resolving large number operations, including multiplication in the post-quantum cryptography algorithm. Our research specifically centers on the implementation of Toom-Cook-based multiplication algorithms for high- and half-degree quantum multiplication, up to 20.5-way degrees, considering that existing Toom-Cook lower degrees are combined with a lattice-based approach like the Saber algorithm. In particular, we propose the quantum multiplication design, conduct computation step experiments, and implement the division-free method. In addition to examining the Toom-Cook 20.5-way algorithm, this study also provides an overview of the results obtained from the Toom-Cook 8.5-way and Toom-Cook 10.5-way algorithms. The Toom-Cook 20.5-way design exhibits significant performance improvement over its predecessor, as evidenced by its lower value of asymptotic complexity and lower cost of quantum implementation, with a qubit count ofn1.186, approximately 522nlog2141- 540nToffoli count, andn1.033Toffoli depth. Concerning the asymptotic performance analysis and quantum cost compared to alternative Toom-Cook-based multiplication, the results indicate the development of a more efficient multiplication polynomial that may be utilized in the evaluation of post-quantum security.

Keith S. Stowe

Fred Jendrzejewski, Selim Jochim

In this first lecture we will review the foundations of quantum mechanics at the level of a cooking recipe. This will enable us to use them later for the discussion of the atomic structure and interaction between atoms and light.