Home Schools Computational Sciences Publications

Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation
KIAS Author
Kim, Myungshik,Park, Jungjun,Lim, Youngrong,Lim, Youngrong
New Journal of Physics, 2022
The noisy binary linear problem (NBLP) is a known computationally intractable problem. Thus, NBLP offers primitives for post-quantum cryptography. An efficient quantum NBLP algorithm that exhibits a polynomial quantum sample and time complexities has recently been proposed. However, a large number of samples should be loaded in a highly entangled state, and it is unclear whether such a precondition does not affect the quantum speedup obtained. Here, we analyse the quantum solvability of NBLP by considering the entire algorithm process, namely from the preparation of the quantum sample to the main computation. Assuming that the algorithm runs on fault-tolerant quantum circuitry, the cost is defined in terms of the overall number of layers of T gates, often referred to as T-depth complexity. We show that the cost of solving the NBLP can be polynomial in the problem size, at the expense of an exponentially increasing number of logical qubits.