# 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:**

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

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.

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.

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

Sussex study enables predicting computational power of early quantum computers

University of Sussex quantum physicists have developed an algorithm which helps early quantum computers to perform calculations most efficiently

University of Sussex quantum physicists have developed an algorithm which helps early quantum computers to perform calculations most efficiently

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.

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.

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.

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.

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.

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.

## Trending Science News

**Current Coronavirus (COVID-19) News**

## Top Science Podcasts

We have hand picked the**top science podcasts of 2020**.

**Now Playing: TED Radio Hour**

**Listen Again: The Power Of Spaces**

How do spaces shape the human experience? In what ways do our rooms, homes, and buildings give us meaning and purpose? This hour, TED speakers explore the power of the spaces we make and inhabit. Guests include architect Michael Murphy, musician David Byrne, artist Es Devlin, and architect Siamak Hariri.

**Now Playing: Science for the People**

**#576 Science Communication in Creative Places**

When you think of science communication, you might think of TED talks or museum talks or video talks, or... people giving lectures. It's a lot of people talking. But there's more to sci comm than that. This week host Bethany Brookshire talks to three people who have looked at science communication in places you might not expect it. We'll speak with Mauna Dasari, a graduate student at Notre Dame, about making mammals into a March Madness match. We'll talk with Sarah Garner, director of the Pathologists Assistant Program at Tulane University School of Medicine, who takes pathology instruction out of...

**Now Playing: Radiolab**

**What If?**

There's plenty of speculation about what Donald Trump might do in the wake of the election. Would he dispute the results if he loses? Would he simply refuse to leave office, or even try to use the military to maintain control? Last summer, Rosa Brooks got together a team of experts and political operatives from both sides of the aisle to ask a slightly different question. Rather than arguing about whether he'd do those things, they dug into what exactly would happen if he did. Part war game part choose your own adventure, Rosa's Transition Integrity Project doesn't give us any predictions, and it isn't a referendum on Trump. Instead, it's a deeply illuminating stress test on our laws, our institutions, and on the commitment to democracy written into the constitution. This episode was reported by Bethel Habte, with help from Tracie Hunte, and produced by Bethel Habte. Jeremy Bloom provided original music. Support Radiolab by becoming a member today at Radiolab.org/donate. You can read The Transition Integrity Project's report here.