Why can't Shor's algorithm be run on a classical computer?
- User
Why can't Shor's algorithm be run on a classical computer?
- 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.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.
Identical first prompt
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →