Skip to content
TheChatArchiveThe Chat Archive
Human-written demonstration (OpenAssistant volunteers)· OpenAssistant (human-written)Hugging Face OpenAssistant Conversations (oasst2)

Why can't Shor's algorithm be run on a classical computer?

In OpenAssistant data, “assistant” turns were written by human volunteers as demonstrations. They are not model outputs.
  1. User

    Why can't Shor's algorithm be run on a classical computer?

  2. Assistant

    Shor's algorithm is a quantum-computer algorithm for integer factorization. It runs in polylogarithmic (sub-polynomial) time on a quantum computer, while there is currently no known polynomial-time classical algorithm for integer factorization, and it is unknown whether such an algorithm exists.

    Shor's algorithm cannot run on a classical computer since it operates on quantum bits (qubits) rather than bits. Abstractly, quantum bits are said to be in a superposition of two states - they can assume either state when measured, with a certain probability. In contrast, classical bits can only assume one of their two possible states at any given time.

    This property of the qubit allows quantum computers to sample functions in multiple points simultaneously. Shor's algorithm uses this fact to find the period of the modular exponentiation function, which can be used to factorize the modulous. Since a classical computer must sample each point in the function individually, it would not be able to finish this task in a reasonable time.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.