How a new quantum approach can develop faster algorithms to deduce complex networks

March 03, 2020

Our world has no dearth of complex networks--from cellular networks in biology to intricate web networks in technology. These networks also form the basis of various applications in virtually all fields of science, and to analyze and manipulate these networks, specific "search" algorithms are required. But, conventional search algorithms are slow and, when dealing with large networks, require a long computational time. Recently, search algorithms based on the principles of quantum mechanics have been found to vastly outperform classical approaches. One such example is the "quantum walk" algorithm, which can be used to find a specific point or a "vertex" on a given N-site graph. Instead of simply going through neighboring vertices, the quantum walk approach employs probabilistic estimations based on the quantum mechanical theory, which drastically reduces the number of steps required to find the objective. To achieve this, before moving from one point to another, an operation called "oracle call" needs to be performed repeatedly to adjust the probability values in the quantum system representation. One main issue is to understand the relationship between the optimal computational time of the oracle call and the structure of the network, as this relationship is well understood for standard shapes and bodies, but it remains unclear for complex networks.

In a new study published in Physical Review A, a team of scientists at Tokyo University of Science, led by Prof Tetsuro Nikuni, dug deeper into the intricacies of these networks in an effort to develop more efficient quantum algorithms. Prof Nikuni explains, "Many real-world systems, such as the World Wide Web and social/biological networks, exhibit complex structures. To fully explore the potential of these network systems, developing an efficient search algorithm is crucial."

To begin with, the scientists looked into the "fractal properties" (geometrical properties of figures that seem to infinitely replicate their overall shape) of networks. The researchers focused on some basic fractal lattices (structures with a fractal network), such as "Sierpinski gasket," "Sierpinski tetrahedron," and "Sierpinski carpet," to try to find out the relationship between the number of vertices (nodes of the network) and the optimal computational time in a quantum walk search. To this end, they performed numerical simulations with over a million vertices and checked whether the results were in line with previous studies, which proposed a mathematical law or a "scaling law" to explain this relationship.

The researchers found that the scaling law for some fractal lattices varied according to their spectral dimension, confirming the previous conjecture for other lattices. Surprisingly, they even found that the scaling law for another type of fractal lattice depends on a combination of its intrinsic characteristics, again showing that the previous conjecture on the optimal number of oracle calls might be accurate. Prof Nikuni says, "It may indeed be a fact that the quantum spatial search on fractal lattices is surprisingly subject to combinations of the characteristic quantities of the fractal geometry. It remains an open question as to why the scaling law for the number of oracle calls is given by such combinations." With this understanding, the team even proposed a new scaling hypothesis, which slightly differs from the ones proposed earlier, so as to gain more insight into different fractal geometries of networks.

The research team hopes that, with their findings, quantum searches will become easier to analyze experimentally--especially with recent experiments performing quantum walks on physical systems like optical lattices. The wide applicability of quantum algorithms on fractal lattices highlights the importance of this study. Owing to its exciting findings, this study was even selected as "Editor's suggestion" in the February 2020 issue of Physical Review A. Optimistic about the results and with future research directions laid out, Prof Nikuni concludes, "We hope that our study further promotes the interdisciplinary study of complex networks, mathematics, and quantum mechanics on fractal geometries."
About The Tokyo University of Science

Tokyo University of Science (TUS) is a well-known and respected university, and the largest science-specialized private research university in Japan, with four campuses in central Tokyo and its suburbs and in Hokkaido. Established in 1881, the university has continually contributed to Japan's development in science through inculcating the love for science in researchers, technicians, and educators.

With a mission of "Creating science and technology for the harmonious development of nature, human beings, and society", TUS has undertaken a wide range of research from basic to applied science. TUS has embraced a multidisciplinary approach to research and undertaken intensive study in some of today's most vital fields. TUS is a meritocracy where the best in science is recognized and nurtured. It is the only private university in Japan that has produced a Nobel Prize winner and the only private university in Asia to produce Nobel Prize winners within the natural sciences field.


About Professor Tetsuro Nikuni from Tokyo University of Science

Prof Tetsuro Nikuni is a Professor at the Department of Physics, Tokyo University of Science. He received his PhD in Physics from Tokyo Institute of Technology and has worked as a postdoctoral research fellow at Tokyo Institute of Technology and the University of Toronto. A senior and respected researcher, he has more than 100 research publications to his credit. His current research interests include the theory of many-body quantum systems and quantum algorithms.

Funding information

This research was supported by JSPS KAKENHI grant no. JP18K03499 and grant no. JP16K05504.

Media contact

Tsutomu Shimizu

Tokyo University of Science

Related Science Articles from Brightsurf:

75 science societies urge the education department to base Title IX sexual harassment regulations on evidence and science
The American Educational Research Association (AERA) and the American Association for the Advancement of Science (AAAS) today led 75 scientific societies in submitting comments on the US Department of Education's proposed changes to Title IX regulations.

Science/Science Careers' survey ranks top biotech, biopharma, and pharma employers
The Science and Science Careers' 2018 annual Top Employers Survey polled employees in the biotechnology, biopharmaceutical, pharmaceutical, and related industries to determine the 20 best employers in these industries as well as their driving characteristics.

Science in the palm of your hand: How citizen science transforms passive learners
Citizen science projects can engage even children who previously were not interested in science.

Applied science may yield more translational research publications than basic science
While translational research can happen at any stage of the research process, a recent investigation of behavioral and social science research awards granted by the NIH between 2008 and 2014 revealed that applied science yielded a higher volume of translational research publications than basic science, according to a study published May 9, 2018 in the open-access journal PLOS ONE by Xueying Han from the Science and Technology Policy Institute, USA, and colleagues.

Prominent academics, including Salk's Thomas Albright, call for more science in forensic science
Six scientists who recently served on the National Commission on Forensic Science are calling on the scientific community at large to advocate for increased research and financial support of forensic science as well as the introduction of empirical testing requirements to ensure the validity of outcomes.

World Science Forum 2017 Jordan issues Science for Peace Declaration
On behalf of the coordinating organizations responsible for delivering the World Science Forum Jordan, the concluding Science for Peace Declaration issued at the Dead Sea represents a global call for action to science and society to build a future that promises greater equality, security and opportunity for all, and in which science plays an increasingly prominent role as an enabler of fair and sustainable development.

PETA science group promotes animal-free science at society of toxicology conference
The PETA International Science Consortium Ltd. is presenting two posters on animal-free methods for testing inhalation toxicity at the 56th annual Society of Toxicology (SOT) meeting March 12 to 16, 2017, in Baltimore, Maryland.

Citizen Science in the Digital Age: Rhetoric, Science and Public Engagement
James Wynn's timely investigation highlights scientific studies grounded in publicly gathered data and probes the rhetoric these studies employ.

Science/Science Careers' survey ranks top biotech, pharma, and biopharma employers
The Science and Science Careers' 2016 annual Top Employers Survey polled employees in the biotechnology, biopharmaceutical, pharmaceutical, and related industries to determine the 20 best employers in these industries as well as their driving characteristics.

Three natural science professors win TJ Park Science Fellowship
Professor Jung-Min Kee (Department of Chemistry, UNIST), Professor Kyudong Choi (Department of Mathematical Sciences, UNIST), and Professor Kwanpyo Kim (Department of Physics, UNIST) are the recipients of the Cheong-Am (TJ Park) Science Fellowship of the year 2016.

Read More: Science News and Science Current Events 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