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

assistant: Shor's algorithm requires the use of a quantum computer, because it relies on the properties of quantum mechanics. Specifically, it uses the fact that a quantum computer can perform operations on many different inputs simultaneously, in a process known as superposition. While it could be run on a classical computer any increases in efficiency it offers over traditional factorization algorithms would be lost.

prompter: Do you know any open-source libraries which allow running Shor's algorithm on usual PC?

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.

prompter: Schor’s algorithm does work on a classical computer.  Shor’s algorithm contains many steps, all of which run quickly on a classical computer except for the period finding step, which runs slowly and can only be efficiently evaluated by a quantum computer. There are various ways to factor classically, but they all require exponential time. The best current algorithm is the general number field sieve. Quantum computers, though, can factor in polynomial time and fully utilize the benefits from Shor’s algorithm.

assistant: Shor's algorithm uses both classical and quantum techniques to factor large numbers into their prime factors. In particular, finding the period of a modular exponentiation function can be done using quantum phase estimation. If there is a classical alternative to this approach, it has not yet been found. While the remaining portion of work required for factoring the original number can be done using classical techniques, the quantum computer is quite capable of this—so technically you could involve a classical computer in the job in part if you wanted, but it wouldn't be efficient to do so.

Although it is possible to simulate a small-scale quantum computer on a classical computer, the exponential growth in the number of potential states would make it intractable to simulate the large number of qubits required for Shor's algorithm.

prompter: Can I use a cloud service to run it?

assistant: It is technically feasible to use a cloud-based quantum computer to run Shor's algorithm, given that you have access to one. Users can test out quantum algorithms using cloud-based quantum computing services provided by a number of organizations, including IBM, Microsoft, Google, and Amazon.

Unfortunately, given the current state of quantum computing technology, it is currently impractical to perform Shor's algorithm on a cloud-based quantum computer. Shor's technique has been successfully employed by some experimental quantum computers to factor tiny numbers, but the huge numbers that are of practical significance, such as those used in contemporary encryption, cannot yet be factored in by existing quantum computers due to their current lack of power.

Furthermore, quantum computing technology is still in its infancy and is not yet broadly accessible. Researchers, academics, and specific industry partners often get access to cloud-based quantum computing services only after receiving permission from the service providers.

In conclusion, even if it is technically conceivable to run Shor's algorithm on a cloud-based quantum computer, the status of quantum computing technology at the moment and the lack of widespread access to these systems make this option unfeasible for the majority of users.

assistant: Yes, it is possible to use a cloud service to run Shor's algorithm, which is a quantum algorithm for integer factorization. However, running Shor's algorithm on a quantum computer requires significant computational resources and is currently only feasible on a few specialized platforms, such as those provided by IBM, Google, and D-Wave.

If you have access to a quantum computer, you can use cloud services provided by these platforms to run Shor's algorithm. IBM provides access to quantum computers through IBM Quantum Experience, while Google provides access through Google Quantum Computing. D-Wave provides access to its quantum annealing platform through Leap.

prompter: How expensive would it be?

assistant: I believe you could use a cloud computing server that supports quantum computing.

prompter: Can you give me a specific example?