Three insights into the foundations of computer science

This year CQT researchers have three papers accepted for one of the most important conferences in theoretical computer science, the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011). The papers present new results in quantum query complexity, quantum bit commitment, and positive semi-definite programming.

Being selected for such a major conference counts in computer science as publication in a peer-reviewed journal matters in physics: results presented at such conferences are not necessarily submitted to journals as well.

CQT researchers (from left to right) Iordanis Kerenidis, Troy Lee, Penghui Yao and Rahul Jain will present results at the prestigious computer science conference FOCS 2011.

"It is encouraging to see the work conducted in our group get recognition at top conferences and journals in theoretical computer science. We hope to continue to do good work," says Rahul Jain, who is one of CQT's Principal Investigators in computer science and an NUS Assistant Professor. The three CQT papers are among a total of 85 to be presented at FOCS 2011 in Palm Springs, California, 23-25 October 2011.

Query complexity

CQT Research Fellow Troy Lee and Visiting Professor Mario Szegedy are co-authors of the accepted paper "Quantum query complexity of state conversion" (arXiv:1011.3020).

Quantum query complexity is a simplified model of quantum computation in which algorithms are formulated as a sequence of queries to the input. For example an algorithm to solve the problem "does this graph have a triangle?" would proceed via queries such as "is there an edge between vertex i and j?". As the algorithm is quantum, these queries can be made in superposition. The total number of queries required is a measure of the hardness of the problem the algorithm tackles and, as long as appropriate queries can be identified quickly, the query complexity is also a measure of how long the algorithm will take to run. Well-known quantum programs such as Grover's search algorithm and Shor's factorization algorithm can be formulated in the query model.

Troy, Mario and their collaborators show that the query complexity of a problem is approximately equivalent to a new quantity that measures the distance between a successful algorithm's initial and final states. "Hopefully, this characterization will aid in finding new algorithms and resolving the query complexity of some open problems," says Troy. The information-theoretic measure is related to a previously studied quantity known as the 'Schur product operator norm'.

Bit commitment

"Optimal bounds for quantum bit commitment" (arXiv: 1102.1678) by CQT Visiting Scholar Iordanis Kerenidis and his coauthor is the second accepted paper with a CQT link. It answers what had been an open question concerning the security of a type of quantum information protocol known as bit commitment.

Bit commitment refers to a scheme where one party, Alice, "commits" a bit, 0 or 1, to another party, Bob. After committing the bit, Alice should not be able to change it, and the bit should remain secret from Bob. Later Alice reveals the bit to Bob. Neither party trusts the other, and the question is, with what probability can either party cheat? The cheating probability of Alice is the probability with which she is able to change her committed bit while revealing it. The cheating probability of Bob is the probability with which he is able to guess the bit committed by Alice, before the reveal phase starts. The cheating probability of the protocol is the maximum of these two cheating probabilities. Using quantum protocols a better level of trust can be enforced than can be achieved in classical protocols.

Previously the best known quantum protocol had cheating probability of no more than 3/4 (0.750). It had also been shown that no quantum protocol could have cheating probability less than 1/√2 (0.707). In the new paper, Iordanis and his coauthor close the gap, showing that the smallest possible cheating probability is 0.739 and identifying a quantum protocol that achieves this.

Approximations

The third paper to be presented at FOCS 2011 is "A Parallel Approximation Algorithm for Positive Semi-definite Programming" (arXiv: 1104.2502) by Rahul and CQT PhD student Penghui Yao. Their algorithm provides an efficient way to solve 'positive semi-definite programs'. Fast parallel algorithms for solving semi-definite programs have had several applications in the past, including the derivation by Rahul and others of QIP=PSPACE, an important result in theoretical quantum computing.

The new parallel approximation algorithm takes an amount of time that scales polylogarithmically with the size of the problem, i.e., as (log n)^k for problem size n where k is a constant. It gets rid of a polynomial dependence that the previous algorithms of this type had on certain 'width parameters'.