Quantum-accelerated algorithms for generating random primitive polynomials over finite fields

Abstract

Primitive polynomials over finite fields are crucial for various domains of computer science, including classical pseudo-random number generation, coding theory and post-quantum cryptography. Nevertheless, the pursuit of an efficient classical algorithm for generating random primitive polynomials over finite fields remains an ongoing challenge. In this paper, we show how to solve this problem efficiently through hybrid quantum-classical algorithms, and designs of the specific quantum circuits to implement them are also presented. Our research paves the way for the rapid and real-time generation of random primitive polynomials in diverse quantum communication and computation applications.

References in corpus (11)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• Semiclassical Fourier Transform for Quantum Computation
• Quantum circuits of T-depth one
• Secure communication using mesoscopic coherent states
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Efficient factorization with a single pure qubit and $logN$ mixed qubits
• Pretending to factor large numbers on a quantum computer
• Key Generation: Foundations and a New Quantum Approach
• Realization of quantum gates with multiple control qubits or multiple target qubits in a cavity
• Upper bounds on cyclotomic numbers

Cited by in corpus (1)

• Beating the fault-tolerance bound and security loopholes for Byzantine agreement with a quantum solution