Efficient Triangles Finding Algorithm Holds Potential for Quantum Computing

Two papers about minimising effort took CQT researchers to the prestigious ACM-SIAM SODA conference in New Orleans in January. The CQT computer scientists and their collaborators set bounds on the amount of work that needs to be done to solve two different problems.

Troy Lee presented work done with Miklos Santha and collaborator Frederic Magniez that sets a new efficiency record for finding triangles in a graph, a data-search problem, while Shengyu Zhang presented new bounds on the cost of creating shared quantum states. That work was done by Shengyu with Rahul Jain, Yaoyun Shi and Zhaohui Wei.

Both results provide guidelines to researchers seeking to design and build devices that harness quantum effects.

The ACM-SIAM SODA meeting is the Symposium on Discrete Algorithms (SODA) organised by the Society for Industrial and Applied Mathematics (SIAM) and Association for Computing Machinery (ACM). The 2013 meeting was held 6–8 January.

Finding triangles

"I don't know why, but sometimes people don't understand the interest of finding a triangle in a graph," says Troy. A graph is a set of data points that share connections, and triangles are sets of three points, call them A, B and C, that are interconnected in a triangular way, eg A to B, B to C, and C to A.

"I think the point is that this is an algorithmic testing ground, and each improvement in triangle finding has come with new algorithmic techniques," says Troy.

Triangle-finding is a search problem, and search problems have an illustrious history in quantum information. Grover's search algorithm was one of the first algorithms to show that quantum effects could speed up computation: it finds a specific item in an unsorted list of size n using around √n=n^1/2) queries. In computer science language, the algorithm is described as having complexity O(n^0.5). The only way to solve the search problem classically would be to look at every item, taking n queries, which would be much slower.

"We understand how to find one thing. That is Grover. We understand how to find two things with a certain property. This is the 'collision problem'. The current frontier, where the quantum complexity is still open, is finding three things with some relation, like finding a triangle," explains Troy.

Adapting Grover's algorithm naively to search for three triangularly connected points gives a solution that has complexity O(n3/2). Some years ago, Miklos and other collaborators developed an algorithm that improved this to O(n1.3). The algorithm Troy presented at SODA has complexity O(n9/7), setting a new world efficiency record for this problem.

The algorithm was devised using a technique known as a 'non-adaptive learning graph'. Research since has shown that the algorithm is close to (and may even be) the best solution possible using this approach.

Troy is a Senior Research Fellow at CQT. He was recently awarded a prestigious Singapore NRF Fellowship. Miklos is a Principal Investigator at CQT and a researcher with the French research organisation CNRS based at the University Paris Diderot, where Frederic is also from.

For more about the work, see "Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing" arXiv:1210.1014.

Sharing resources

A good start to solving many problems in quantum computation or simulation is for two parties tackling the problem to have a 'shared resource' — a quantum state that stretches across systems held in both of their possessions. In the second paper presented at SODA, CQT researchers and their collaborators calculate the least amount of work required to create the needed state.

Such lower bounds could tell experimentalists, for example, the most efficient way of creating a specific shared state of some large number of quantum bits (qubits). By comparing the amount of work involved in an experimental protocol with the theoretical bound, the experimentalists would know if they were being as efficient as they could be.

The researchers consider two general cases — the first is that the two parties create their shared quantum state from scratch by sending each other messages. The effort required in this case is the 'communication complexity' of the problem. In the second scenario, the two parties start with a shared state, but not the one they want. They then have to convert that state to the target one by performing measurements on only their part (and using no communication). The 'correlation complexity' measures how small (in terms of qubits) a state the parties can start with and still be able to achieve their goal.

The communication and correlation complexity turn out to be the same. The team showed that for generating shared classical distributions, the complexity is equal to another quantity known as the Positive Semidefinite (PSD) rank of the distribution. The team also found a general expression for generating all shared quantum states, which reduces to PSD rank for classical distributions and to the well known Schmidt rank for pure states.

The link to the PSD rank is interesting, says Rahul, a CQT Principal Investigator and author on the paper, because this quantity was only recently defined in a different type of problem. "It's a connection between the problems," says Rahul.

Finally, the team calculated the complexity of the problem for generating an approximation of a desired shared quantum state, as opposed to generating it exactly. They found the complexity, in case of approximating classical distributions, equals to another quantity called Wyner's information, which is a well studied measure in classical information theory. The hint of connection between PSD rank and Wyner's also intrigues Rahul.

The work emerged from a wide-ranging collaboration of computer scientists, physicists and CQT visiting scholars. Shengyu, who presented the work at the conference, is a Visiting Scholar with CQT from the Chinese University of Hong Kong. Alongside Rahul, the two other researchers on the paper are Yaoyun from the University of Michigan, United States, and Zhaohui,a CQT Research Fellow from PI Kwek Leong Chuan's theoretical physics group.