What is Quantum Algorithm?
In quantum computing, a quantum algorithm is an algorithm designed to run on a quantum computer, with the quantum circuit model being the most commonly used framework[1]. In the quantum circuit model, various quantum gates serves as the fundamental building blocks that manipulate the quantum states of qubits and perform computations. Unlike classical gates which operate on classical bits (0 or 1) and can only process one input at a time, quantum gates act on qubits in superposition, which allows them to process multiple inputs simultaneously. This capability, combined with quantum entanglement, enables quantum circuits to execute specific quantum algorithms, offering the potential for exponential speedup over classical computers for certain tasks.
Quantum algorithm can be categorized into two main types, full quantum circuits and hybrid classical-quantum algorithms. In full quantum circuits, the entire algorithm is executed on a quantum computer using quantum gates. With quantum algorithms, full quantum circuits require a large number of qubits and gates to achieve a specific function. However, the number of qubits is limited in a real quantum computer. In addition, the quantum gate fidelity is not high and current quantum circuits suffer from high quantum errors. It is challenging to achieve a quantum algorithm with a large number of quantum gates. Also, quantum circuits often require qubits to interact with each other through two-qubit gates. However, qubit connectivity is limited because of the physical layout of the qubits and the limitations of the underlying hardware architecture. Some quantum circuits can not be executed efficiently so quantum optimization technology can reduce the effects of limited qubit connectivity. It converts a quantum circuit to an equivalent circuit which can be efficiently executed on the available quantum hardware.
1. Full quantum algorithmsIn this approach, the entire algorithm is executed on a quantum computer using only quantum gates. Full quantum circuits often require a large number of qubits and quantum gates to achieve specific computational tasks. However, real quantum computers face several challenges, such as the restricted number of qubits, low gate fidelity, and high error rates. These challenges make it difficult to implement complex quantum algorithms that involve a large number of qubits and quantum gates. Moreover, quantum gates often rely on qubit reactions through two-qubit gates. Due to the physical layout of qubits and the constraints of current hardware architectures, qubit connectivity is limited. This limitation can hinder the efficient execution of certain quantum circuits. To address these limitations, quantum optimization techniques are used to convert a quantum circuit to an equivalent one that can be executed more efficiently on the available computer hardware, mitigating the effects of limited qubit connectivity.
2. Hybrid classical-quantum algorithmsThese algorithms combine classical and quantum computation, with certain parts of the algorithm executed on classical computers and others on quantum computers. Hybrid approaches can alleviate some challenges, such as gate fidelity and coherence time, by offloading certain computations to classical processors. This strategy aims to efficiently execute quantum algorithms within the constraints of current technology. Additionally, certain tasks that are computationally intensive on quantum hardware may be more easily performed on classical computers. By integrating classical computing, hybrid algorithms can simplify the complexity of quantum algorithms. For example, finding the lowest energy state in a quantum system can be challenging for quantum hardware, so a classical optimization method like gradient descent can be used to handle this task, making the overall algorithm more practical and efficient.
Now, I will introduce some basic quantum algorithms. These foundational algorithms are key to understanding how quantum computing can solve certain problems more efficiently than classical methods. They also serve as building blocks for more advanced quantum applications, showcasing the unique strengths of quantum computers.
The common quantum algorithms are as follow: