Logic gates are the fundamental building blocks of digital computing systems. This is true for both conventional digital computers and future quantum computers; each processes information by moving it through a circuit containing an arrangement of logic gates designed to perform a calculation. This new research is the first attempt to determine the number of logic gates that quantum states need to process information. The number of gates, or “creation complexity,” determines whether quantum algorithms outperform classical algorithms. Understanding creation complexity will potentially lead to a systematic way for researchers to design efficient quantum algorithms. The research also deepens our understanding of the quantum state, which is critical to the field of quantum computing.
Quantum computing is making enormous progress. Harnessing the unique powers of quantum physics, quantum computing could revolutionize many applications. These applications include molecular simulation, machine learning, and cryptography. A key problem for quantum computing is how to design quantum algorithms and circuits that scale efficiently with the size of the system being studied. Researchers have proposed many quantum algorithms over the last two decades. However, at present researchers design new quantum algorithms in an accidental trial and error process because there is no systematic way to look for algorithms that scale efficiently. This new research paves the way to a systematic way to design those quantum algorithms.
Since any quantum algorithm is essentially a sequence of unitary gates operating on an input state and producing an output state, researchers can relate the complexity of creating the output state to the complexity of the quantum algorithm. Identifying quantum states that have a polynomial creation complexity is the first step towards the development of efficient quantum algorithms that outperform classical algorithms. This paper gives an answer to the question of what quantum states can be created with a number of elementary gates that scale polynomially with the number of qubits.
The research was funded by the Department of Energy Office of Science, Office of Basic Energy Sciences.
