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

The related research entitled “Experimental study of Forrelation in nuclear spins” was published on Science Bulletin of volume 62 and pages 497, 2017. Scholar from Southern University of Science and Technology, Yung Man-Hong, collaborated with scholars from Tsinghua University, Li Hang, Gao Xun, Xin Tao and Long Guilu, completed the research, among which, Professor Yung Man-Hong and Long Guilu act the corresponding authors. The above 5 scholars solved the 2-fold and 3-fold Forrelation problems in nuclear spins and controlled the spin fluctuation to within a threshold value by developing a set of optimized GRAPE pulse sequences.

Quantum computers have an advantage of exponential speedups over classical computers in certain problems. However, in the black-box model, most quantum algorithms can give evidence that quantum computation can achieve exponential and even larger speedups. There raises a question: Within the black-box model, just how large of 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, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. And they show it’s the largest quantum black-box speedup yet known.

Professor Yung Man Hong and his collaborators designed a quantum circuit for implementing multi-fold Forrelations. They realized the 2-fold and 3-fold case of Forrelations on a nuclear magnetic resonance spectrometer by measuring the value of Forrelation to check it’s in the case of larger than 3/5 or the absolute value of it is less than 1/100. This is the first experimental realization of solving the Forrelation problem reported in the literature. Their results are shown in figure 1. 

Figure 1: The result of 2-fold and 3-fold Forreation

Professor Long Guilu gave Forrelation the Chinese translation 傅换关联. He stated: “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 their quantum algorithms are implemented on a three-qubit quantum information processor, which may not greatly 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 quantum devices in the near future.”

This research was funded by the National Natural Science Foundation of China (No. 11175094, 91221205 and 11405093), and the National Basic Research Program of China (No. 2015CB921002).

See the article: H. Li, X. Gao, T. Xin, MH Yung, G. Long, “Experimental Study of Forrelation in Nuclear Spins” Sci. Bull. (2017) 62(7): 497-502. doi: 10.1016/j.scib.2017.03.006

This article was published online (http://www.sciencedirect.com/science/article/pii/S2095927317301299), in the Science Bulletin, by Science China Press and Elsevier.