The 46th Annual IEEE Symposium on Foundations of Computer Science (a.k.a. FOCS) submission deadline was last Friday. Not surprisingly this means that there are more than the average number of interesting papers being posted on the Tuesday listing of the arXiv.
Of course, I will start by doing a little shameless self-promotion. Here is the latest and greatest from myself, Andrew Childs (Caltech) and Wim van Dam (UCSB) (everyone do the new paper dance) quant-ph/0504083:
From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
Dave Bacon, Andrew Childs, and Wim van Dam
We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form (Z_p)^r X| Z_p for fixed r (including the Heisenberg group, r=2). In particular, our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.
The nonabelian hidden subgroup problem is one of the most frustratingly well studied problems in the theory of quantum algorithms. This is because an efficient algorithm for the hidden subgroup problem over the symmetric group would lead to an efficient algorithm for the graph isomorphism problem (the graph isomorphism problem is telling if two graphs that I present to you by their adjacency matrices are really the same graph under some relabeling of the vertices.) To this end, there are many positive and many negative results about this problem. One thing we do know is that the query complexity of the problem is efficient. We just don’t know how to turn this into efficient algorithms. In our paper we show, in particular for certain groups which include the Heissenberg group, that there are multi-query quantum algorithms which make explicit use of the numerous queries to produce an efficient quantum algorithm. Certainly I take this as evidence that there is much left to be understood about how exactly we can achieve exponential speedups of quantum over classical computers.
Another interesting component to this algorithm is that it shows how an efficient quantum algorithm for the hidden subgroup problems we consider can be achieved by producing an efficient quantum algorithm for certain algebraic problems. This was also true for the case of the dihedral hidden subgroup problem, where, in that case, the algebraic problem turned out to be the subset sum problem. Since this problem is NP-compete, this didn’t lead to an efficient algorithm. But for the groups we consider in our new paper, the problem is efficiently solvable classically, and we are able to bootstrap this onto a quantum algorithm to achieve the speedup.
Another interesting, and closely related paper, is the paper by Cris Moore (University of New Mexico…no “h!”) and Alex Russell (University of Connecticut), quant-ph/0504067:
Bratteli Diagrams and Subexponential Time Quantum Algorithms for Hidden Subgroup Problems: or, Fourier Sampling Strikes Back
Cristopher Moore and Alexander Russell
We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This entangled measurement uses $k=log_2 |G|$ registers, and each of the $2^k$ subsets of the registers contributes some information. We then give a general framework using the Bratteli diagram of the group for constructing worst-case to average-case reductions from the HSP to generalized Subset Sum problems analogous to those of Regev for the dihedral group. As a result, we obtain subexponential-time quantum algorithms for the hidden subgroup problem on a number of new group families, including the Heisenberg and affine groups. Our framework also yields subexponential-time algorithms for finding the order of hidden subgroups in all solvable groups of low degree, including all nilpotent groups.
Here, Cris and Alex present a large number of subexponential time algorithms for numerous groups (including the Heisenberg group for which were able to find a polynomial time algorithm.) They are able to do this by showing how these algorithms can arise from the classical solution to a problem which arises from the representation theory of these groups. Again, what is essential in these algorithms is the use of multiple quantum queries.
As you can see, there seems to be quite a revival going on in research on the hidden subgroup problem. There is a lot of structure which many of us are starting to see! Fun times.
Along different lines, Ran Raz (Weizmann Institute) also has a very intriguing paper, quant-ph/0504075:
Quantum Information and the PCP Theorem
Ran Raz
We show how to encode $2^n$ (classical) bits $a_1,…,a_{2^n}$ by a single quantum state $|Psi>$ of size O(n) qubits, such that: for any constant $k$ and any $i_1,…,i_k in {1,…,2^n}$, the values of the bits $a_{i_1},…,a_{i_k}$ can be retrieved from $|Psi>$ by a one-round Arthur-Merlin interactive protocol of size polynomial in $n$. This shows how to go around Holevo-Nayak’s Theorem, using Arthur-Merlin proofs.
We use the new representation to prove the following results:
1) Interactive proofs with quantum advice: We show that the class $QIP/qpoly$ contains ALL languages. That is, for any language $L$ (even non-recursive), the membership $x in L$ (for $x$ of length $n$) can be proved by a polynomial-size quantum interactive proof, where the verifier is a polynomial-size quantum circuit with working space initiated with some quantum state $|Psi_{L,n} >$ (depending only on $L$ and $n$). Moreover, the interactive proof that we give is of only one round, and the messages communicated are classical.
2) PCP with only one query: We show that the membership $x in SAT$ (for $x$ of length $n$) can be proved by a logarithmic-size quantum state $|Psi >$, together with a polynomial-size classical proof consisting of blocks of length $polylog(n)$ bits each, such that after measuring the state $|Psi >$ the verifier only needs to read {bf one} block of the classical proof.
While the first result is a straight forward consequence of the new representation, the second requires an additional machinery of quantum low-degree-test that may be interesting in its own right.
I haven’t had time to work through this paper in detail, but one of the main results, that QIP(2) (one round Quantum Interactive Proofs) with polynomial quantum advice (a polynomial sized quantum state) contains all languages seems to me to be very surprising. I know that previously Scott Aaronson had shown that BQP (i.e. your standard efficient quantum algorithms) with polynomial quantum advice was in PP (probabilistic polynomial time..the worst named complexity class ever!) with polynomial classical advice, but the jump to all languages seems to me to be quite a huge jump! Well I certainly have some reading to do!
Finally there is a paper by Harry Buhrman (University of Amsterdam, CWI Amsterdam), Matthias Christandl (CQC Cambridge), Patrick Hayden (McGill), Hoi-Kwong Lo (University of Toronto) and Stephanie Wehner(CWI Amsterdam), quant-ph/0504078:
On the (Im)Possibility of Quantum String Commitment
Harry Buhrman, Matthias Christandl, Patrick Hayden, Hoi-Kwong Lo, and Stephanie Wehner
Unconditionally secure non-relativistic bit commitment is known to be impossible in both the classical and quantum worlds. However, when committing to a string of n bits at once, how far can we stretch the quantum limits? We consider quantum schemes where Alice commits a string of n bits to Bob, in such a way that she can only cheat on a bits and Bob can learn at most b bits of ”information” before the reveal phase. We show a negative and a positive result, depending on how we measure Bob’s information. If we use the Holevo quantity, no good schemes exist: a+b is at least n. If, however, we use accessible information, there exists a scheme where a=4 log n+O(1) and b=4. This is classically impossible. Our protocol is not efficient, however, we also exhibit an efficient scheme when Bob’s measurement circuit is restricted to polynomial size. Our scheme also implies a protocol for n simultaneous coin flips which achieves higher entropy of the resulting string than any previously known protocol.
Bit commitment is something like the cryptographic version of a securely sealed safe. Alice and Bob begin by Alice supplying Bob data which commits Alice to a bit, but does not reveal the value of Alice’s bit to Bob. Later, when they wish to reveal the commitment, Alice sends some information to Bob such that Bob can infer what value Alice commited to. Unconditional security would mean that there is no way for Alice to change her commitment after she has communicated to Bob without Bob being able to detect the commitment. Similarly Bob should not be able to learn anything about Alice’s bit. It is known (or I should say there is a proof with what seem like reasonable foundations) that in the standard quantum information setting, unconditionally secure quantum bit commitment is not possible. But what about the problem of not committing to a bit, but committing to a string? Now Alice can cheat on some bits, and Bob can learn some bits, but what exactly is the relationship between these two quantities? Interestingly the authors show that in the case where the measure of information about how much Bob learns is the accessible information there are quantum schemes which are impossible classically. Nothing like a result showing that quantum information kicks classical information’s rear end!
So, by my count, on Tuesday we had two algorithms papers demonstrating new speedups, a complexity theory paper demonstrating the amazing power of quantum advice for quantum interactive proofs, and a cryptographic paper demonstrating a new sepeartion between quantum and classical cryptography. Not a bad day for the arXivs!
