The Primitive Root Problem: a Problem in BQP

Authors

Shixin Wu, Rose-Hulman Institute of TechnologyFollow

Document Type

Dissertation

Publication Date

5-2022

First Advisor

Joshua Holden

Abstract

Shor’s algorithm proves that the discrete logarithm problem is in BQP. Based on his algorithm, we prove that the primitive root problem, a problem that verifies if some integer g is a primitive root modulo p where p is the largest prime number smaller than 2n for a given n, which is assumed to be harder than the discrete logarithm problem, is in BQP by using an oracle quantum Turing machine.

Comments

Senior Thesis, Department of Mathematics, Rose-Hulman Institute of Technology

Recommended Citation

Wu, Shixin, "The Primitive Root Problem: a Problem in BQP" (2022). Mathematical Sciences Technical Reports (MSTR). 178.
https://scholar.rose-hulman.edu/math_mstr/178