New theory hints at more efficient way to develop quantum algorithms

Method to further understanding of the quantum state space

WEST LAFAYETTE, Ind. — In 2019, Google claimed it was the first to demonstrate a quantum computer performing a calculation beyond the abilities of today’s most powerful supercomputers.

But most of the time, creating a quantum algorithm that stands a chance at beating a classical computer is an accidental process, Purdue University scientists say. To bring more guidance to this process and make it less arbitrary, these scientists developed a new theory that may eventually lead to more systematic design of quantum algorithms.

The new theory, described in a paper published in the journal Advanced Quantum Technologies, is the first known attempt to determine which quantum states can be created and processed with an acceptable number of quantum gates to outperform a classical algorithm.

Physicists refer to this concept of having the right number of gates to control each state as “complexity.” Since the complexity of a quantum algorithm is closely related to the complexity of quantum states involved in the algorithm, the theory could therefore bring order to the search for quantum algorithms by characterizing which quantum states meet that complexity criteria.

An algorithm is a sequence of steps to perform a calculation. The algorithm is usually implemented on a circuit.

In classical computers, circuits have gates that switch bits to either a 0 or 1 state. A quantum computer instead relies on computational units called “qubits” that store 0 and 1 states simultaneously in superposition, allowing more information to be processed.

What would make a quantum computer faster than a classical computer is simpler information processing, characterized by the enormous reduction in the number of quantum gates in a quantum circuit compared with a classical circuit.

In classical computers the number of gates in circuits increases exponentially with respect to the size of the problem of interest. This exponential model grows so astonishingly fast that it becomes physically impossible to handle for even a moderately sized problem of interest.

“For example, even a small protein molecule may contain hundreds of electrons. If each electron can only take two forms, then to simulate 300 electrons would require 2³⁰⁰ classical states, which is more than the number of all the atoms in the universe,” said Sabre Kais, a professor in Purdue’s Department of Chemistry and member of the Purdue Quantum Science and Engineering Institute.

For quantum computers, there is a way for quantum gates to scale up “polynomially” – rather than just exponentially like a classical computer – with the size of the problem (like the number of electrons in the last example). “Polynomial” means that there would be drastically fewer steps (gates) needed to process the same amount of information, making a quantum algorithm superior to a classical algorithm.

Researchers so far haven’t had a good way to identify which quantum states could satisfy this condition of polynomial complexity.

“There is a very large search space for finding the states and sequence of gates that match up in complexity to create a useful quantum algorithm capable of performing calculations faster than a classical algorithm,” said Kais, whose research group is developing quantum algorithms and quantum machine learning methods.

Kais and Zixuan Hu, a Purdue postdoctoral associate, used the new theory to identify a large group of quantum states with polynomial complexity. They also showed that these states may share a coefficient feature that could be used to better identify them when designing a quantum algorithm.

“Given any quantum state, we are now able to design an efficient coefficient sampling procedure to determine if it belongs to the class or not,” Hu said.

This work is supported by the U.S. Department of Energy (Office of Basic Energy Sciences) under Award No. DE-SC0019215. The Purdue Quantum Science and Engineering Institute is part of Purdue’s Discovery Park.

About Discovery Park

Discovery Park is a place where Purdue researchers move beyond traditional boundaries, collaborating across disciplines and with policymakers and business leaders to create solutions for a better world. Grand challenges of global health, global conflict and security, and those that lie at the nexus of sustainable energy, world food supply, water and the environment are the focus of researchers in Discovery Park. The translation of discovery to impact is integrated into the fabric of Discovery Park through entrepreneurship programs and partnerships. 

About Purdue University

Purdue University is a top public research institution developing practical solutions to today’s toughest challenges. Ranked the No. 6 Most Innovative University in the United States by U.S. News & World Report, Purdue delivers world-changing research and out-of-this-world discovery. Committed to hands-on and online, real-world learning, Purdue offers a transformative education to all. Committed to affordability and accessibility, Purdue has frozen tuition and most fees at 2012-13 levels, enabling more students than ever to graduate debt-free. See how Purdue never stops in the persistent pursuit of the next giant leap at https://purdue.edu/.

Writer, Media contact: Kayla Wiles, 765-494-2432, wiles5@purdue.edu

Source: Sabre Kais, kais@purdue.edu

Journalists visiting campus: Journalists should follow Protect Purdue protocols and the following guidelines:

• Campus is open, but the number of people in spaces may be limited. We will be as accommodating as possible, but you may be asked to step out or report from another location.
• To enable access, particularly to campus buildings, we recommend you contact the Purdue News Service media contact listed on the release to let them know the nature of the visit and where you will be visiting. A News Service representative can facilitate safe access and may escort you on campus.
• Correctly wear face masks inside any campus building, and correctly wear face masks outdoors when social distancing of at least six feet is not possible.

ABSTRACT

Characterization of quantum states based on creation complexity

Zixuan Hu and Sabre Kais

DOI: 10.1002/qute.202000043

The creation complexity of a quantum state is the minimum number of elementary gates required to create it from a basic initial state. The creation complexity of quantum states is closely related to the complexity of quantum circuits, which is crucial in developing efficient quantum algorithms that can outperform classical algorithms. A major question unanswered so far is what quantum states can be created with a number of elementary gates that scales polynomially with the number of qubits. In this work we first show for an entirely general quantum state it is exponentially hard (requires a number of steps that scales exponentially with the number of qubits) to determine if the creation complexity is polynomial. We then show it is possible for a large class of quantum states with polynomial creation complexity to have common coefficient features such that given any candidate quantum state we can design an efficient coefficient sampling procedure to determine if it belongs to the class or not with arbitrarily high success probability. Consequently partial knowledge of a quantum state’s creation complexity is obtained, which can be useful for designing quantum circuits and algorithms involving such a state.