Towards the separation of quantum and classical query complexities

May 1, 2017, Science China Press
The result of 2-fold and 3-fold Forreation is shown. Credit: ©Science China Press

Correlation functions are often employed to quantify the relationships among interdependent variables or sets of data. A few years ago, two researchers proposed a property-testing problem involving Forrelation for studying the query complexity of quantum devices. Now, scientists have realized an experimental study of Forrelation in a 3-qubit nuclear magnetic resonance quantum information processor.

The new study was published in Science Bulletin. Four scholars from Tsinghua University, Li Hang, Gao Xun, Xin Tao and Long Guilu, collaborated with a scholar from Southern University of Science and Technology, Yung Man-Hong. In the study, they solved two-fold and three-fold Forrelation problems in nuclear spins and controlled the spin fluctuation to within a threshold value using a set of optimized GRAPE pulse sequences.

It is widely believed that computers have an advantage over classical computers in many computational problems. In the black-box model, many quantum algorithms exhibit quantum speedups. This raises a question: Within the black-box model, just how large a quantum speedup is possible? Specifically, in query complexity, can we find the largest separation between classical and quantum query complexities?

Two years ago, Aaronson and Ambainis introduced a new property-testing problem called Forrelation, which determines whether one Boolean function is highly correlated with the Fourier transform of another Boolean function. And they showed that it gave the largest quantum black-box speedup yet known.

Professor Long Guilu and his collaborators designed a quantum circuit for implementing multi-fold Forrelations. They realized the two-fold and three-fold case of Forrelations on a spectrometer by measuring the value of Forrelation to determine if it was larger than 3/5 or the absolute value was less than 1/100. This is the first experimental realization of the Forrelation problem reported in literature. Their results are shown in figure 1.

Professor Long Guilu, who directed the experiment, says, "One of the difficulties is achieving a high fidelity of the final states, since the value of Forrelation is highly sensitive to the measurement. To control the error within a threshold value, we utilized an optimized gradient ascent pulse engineering technique instead of a composite pulse sequence of hard pulses and J-coupling evolutions."

Professor Yung Man-Hong points out the future development of their work: "All the quantum algorithms are implemented on a three-qubit quantum information processor, which may not present the power of quantum computation over classical computation due to the present experimental techniques. However, this prototype experiment indicates that we may gain quantum supremacy in relatively simple in the near future."

Explore further: Beyond classical computing without fault-tolerance: Looking for the quantum frontier

More information: Hang Li et al, Experimental study of Forrelation in nuclear spins, Science Bulletin (2017). DOI: 10.1016/j.scib.2017.03.006

Related Stories

The exciting new age of quantum computing

October 25, 2016

What does the future hold for computing? Experts at the Networked Quantum Information Technologies Hub (NQIT), based at Oxford University, believe our next great technological leap lies in the development of quantum computing.

Quantum algorithm breakthrough

February 24, 2013

An international research group led by scientists from the University of Bristol, UK, and the University of Queensland, Australia, has demonstrated a quantum algorithm that performs a true calculation for the first time. ...

Recommended for you


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.