# New theory hints at more efficient way to develop quantum algorithms

August 31, 2020WEST 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 2300 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.

-end-

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.**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.

Purdue University

## Related Quantum Computers Articles from Brightsurf:

Optical wiring for large quantum computers

Researchers at ETH have demonstrated a new technique for carrying out sensitive quantum operations on atoms.

New algorithm could unleash the power of quantum computers

A new algorithm that fast forwards simulations could bring greater use ability to current and near-term quantum computers, opening the way for applications to run past strict time limits that hamper many quantum calculations.

A new technique prevents errors in quantum computers

A paper recently published in Nature presents a protocol allowing for the error detection and the protection of quantum processors in case of qubit loss.

New method prevents quantum computers from crashing

Quantum information is fragile, which is why quantum computers must be able to correct errors.

Natural radiation can interfere with quantum computers

Radiation from natural sources in the environment can limit the performance of superconducting quantum bits, known as qubits.

New model helps to describe defects and errors in quantum computers

A summer internship in Bilbao, Spain, has led to a paper in the journal Physical Review Letters for Jack Mayo, a Master's student at the University of Groningen, the Netherlands.

The first intuitive programming language for quantum computers

Several technical advances have been achieved recently in the pursuit of powerful quantum computers.

Hot qubits break one of the biggest constraints to practical quantum computers

A proof-of-concept published today in Nature promises warmer, cheaper and more robust quantum computing.

Future quantum computers may pose threat to today's most-secure communications

Quantum computers that are exponentially faster than any of our current classical computers and are capable of code-breaking applications could be available in 12 to 15 years, posing major risks to the security of current communications systems, according to a new RAND Corporation report.

Novel error-correction scheme developed for quantum computers

Experimental quantum computers are plagued with errors. Here Dr Arne Grimsmo from the University of Sydney and colleagues from RMIT and the University of Queensland offer a novel method to reduce errors in a scheme applicable across different types of quantum hardware.

Read More: Quantum Computers News and Quantum Computers Current Events

Researchers at ETH have demonstrated a new technique for carrying out sensitive quantum operations on atoms.

New algorithm could unleash the power of quantum computers

A new algorithm that fast forwards simulations could bring greater use ability to current and near-term quantum computers, opening the way for applications to run past strict time limits that hamper many quantum calculations.

A new technique prevents errors in quantum computers

A paper recently published in Nature presents a protocol allowing for the error detection and the protection of quantum processors in case of qubit loss.

New method prevents quantum computers from crashing

Quantum information is fragile, which is why quantum computers must be able to correct errors.

Natural radiation can interfere with quantum computers

Radiation from natural sources in the environment can limit the performance of superconducting quantum bits, known as qubits.

New model helps to describe defects and errors in quantum computers

A summer internship in Bilbao, Spain, has led to a paper in the journal Physical Review Letters for Jack Mayo, a Master's student at the University of Groningen, the Netherlands.

The first intuitive programming language for quantum computers

Several technical advances have been achieved recently in the pursuit of powerful quantum computers.

Hot qubits break one of the biggest constraints to practical quantum computers

A proof-of-concept published today in Nature promises warmer, cheaper and more robust quantum computing.

Future quantum computers may pose threat to today's most-secure communications

Quantum computers that are exponentially faster than any of our current classical computers and are capable of code-breaking applications could be available in 12 to 15 years, posing major risks to the security of current communications systems, according to a new RAND Corporation report.

Novel error-correction scheme developed for quantum computers

Experimental quantum computers are plagued with errors. Here Dr Arne Grimsmo from the University of Sydney and colleagues from RMIT and the University of Queensland offer a novel method to reduce errors in a scheme applicable across different types of quantum hardware.

Read More: Quantum Computers News and Quantum Computers Current Events

Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.