Compare Papers

Paper 1

The PPKN Gate: An Optimal 1-Toffoli Input-Preserving Full Adder for Quantum Arithmetic

G. Papakonstantinou

Year

2025

Journal

arXiv preprint

DOI

arXiv:2512.12073

arXiv

2512.12073

Efficient arithmetic operations are a prerequisite for practical quantum computing. Optimization efforts focus on two primary metrics: Quantum Cost (QC), determined by the number of non-linear gates, and Logical Depth, which defines the execution speed. Existing literature identifies the HNG gate as the standard for Input-Preserving Reversible Full Adders. HNG gate typically requires a QC of 12 and a logical depth of 5, in the area of classical reversible circuits. This paper proposes the PPKN Gate, a novel design that achieves the same inputpreserving functionality using only one Toffoli gate and five CNOT gates. With a Quantum Cost of 10 and a reduced logical depth of 4, the PPKN gate outperforms the standard HNG gate in both complexity and speed. Furthermore, we present a modular architecture for constructing an n-bit Ripple Carry Adder by cascading PPKN modules.

Open paper

Paper 2

Computational Complexity of Learning Efficiently Generatable Pure States

Taiga Hiroka, Min-Hsiu Hsieh

Year

2024

Journal

arXiv preprint

DOI

arXiv:2410.04373

arXiv

2410.04373

Understanding the computational complexity of learning efficient classical programs in various learning models has been a fundamental and important question in classical computational learning theory. In this work, we study the computational complexity of quantum state learning, which can be seen as a quantum generalization of distributional learning introduced by Kearns et.al [STOC94]. Previous works by Chung and Lin [TQC21], and Bădescu and O$'$Donnell [STOC21] study the sample complexity of the quantum state learning and show that polynomial copies are sufficient if unknown quantum states are promised efficiently generatable. However, their algorithms are inefficient, and the computational complexity of this learning problem remains unresolved. In this work, we study the computational complexity of quantum state learning when the states are promised to be efficiently generatable. We show that if unknown quantum states are promised to be pure states and efficiently generateable, then there exists a quantum polynomial time algorithm $A$ and a language $L \in PP$ such that $A^L$ can learn its classical description. We also observe the connection between the hardness of learning quantum states and quantum cryptography. We show that the existence of one-way state generators with pure state outputs is equivalent to the average-case hardness of learning pure states. Additionally, we show that the existence of EFI implies the average-case hardness of learning mixed states.

Open paper