Result co-authored by CQT student accepted for top conferences

CQT's Anurag Anshu has a result selected for two top conferences in computer science. With his international coauthors, he found an exponential separation between quantum communication and information, showing a limit to how much a message can be compressed.

CQT PhD student Anurag Anshu has co-authored a paper accepted into one of the world's most prestigious computer science conferences.

The paper "Exponential Separation of Quantum Communication and Classical Information" will be presented at STOC 2017, the Annual ACM Symposium on the Theory of Computing, in Montreal, Canada in June.

Anurag and his colleagues' work clarifies what kind of compression is possible for tasks involving quantum communication, when individuals (or the computers they operate) can exchange quantum bits of information. Such quantum bits can have properties of entanglement and superposition that allow doing things that are impossible with classical bits.

This is not the first time the result has hit high profile conferences. The findings were also presented as a plenary talk at QIP 2017, the 20th Annual Conference on Quantum Information Processing held in Seattle in January.

"It feels good that with my co-authors I've managed to do some concrete things," says Anurag.

A limit to compression

In 2016, Anurag went on exchange to the Institute for Quantum Computing (IQC) at the University of Waterloo in Canada for four months. There he started collaborating with CQT alumnus Penghui Yao and researchers David Touchette and Nengkun Yu, all then postdocs at IQC. Penghui is now at the University of Maryland in the US and Nengkun at the University of Technology Sydney in Australia.

The group were interested in how much communication it takes to complete certain tasks, compared to how much information the tasks involve. This relates to the idea of compression. Compressing a picture with image-processing software, for example, maintains the file’s information content while minimising the communication needed to transmit it.

A few years ago, computer scientists Anat Ganor, Gilat Kol and Ran Raz discovered a protocol with an unexpected property. They found a task that required very little information but took lots of communication to complete. "It's like the antithesis of what computer scientists want," says Anurag.

Persistence pays off

Anurag, Penghui, David and Nengkun set out to investigate whether similar problems could exist with quantum communication. The example Ran Raz and his coauthors had given used only classical communication.

"We met frequently, and for one or two months it was kind of hopeless. It was hard to find the key ideas required to crack the quantum version," he says. The group persisted and slowly got a clearer picture.

The researchers found that, even calling on quantum powers, there exist protocols that take exponentially more communication than information to complete. This exponential separation shows a limit to what kind of message compression is possible in the quantum world. Luckily for us, it does not rule out other powers of quantum communication, such as computing some distributed functions more efficiently than classical communication.

"The way it is designed, the function of Ganor, Kol and Raz is the hardest thing you can think of. It is particularly fabricated to reveal such exponential separations," says Anurag.

The authors' other attempt to demonstrate exponential separation (of themselves) was arguably less successful. Pictured from left to right are Nengkun Yu, Penghui Yao, Anurag Anshu and David Touchette.