Holographic algorithms: The power of dimensionality resolved

Jin‐Yi Cai, Pinyan Lu

Mingji Xia

A holographic algorithm solves a problem in a domain of size n, by reducing it to counting perfect matchings in planar graphs. It may simulate a n-value variable by a bunch of t matchgate bits, which has 2t values. The transformation in the simulation can be expressed as a n × 2t matrix M, called the base of the holographic algorithm. We wonder whether more matchgate bits bring us more powerful holographic algorithms. In another word, whether we can solve the same original problem, with a collapsed base of size n × 2r, where r<t.

Jin‐Yi Cai, Pinyan Lu

In holographic algorithms, symmetric signatures have been particularly useful. We give a complete characterization of these symmetric signatures over all bases of size 1. These improve previous results by Cai and Choudhary (ICALP 2006, vol. 4051, pp. 703–714, 2006) where only symmetric signatures over the Hadamard basis (special basis of size 1) were obtained. In particular, we give a complete list of Boolean symmetric signatures over bases of size 1. It is an open problem whether signatures over bases of higher dimensions are strictly more powerful. The recent result by Valiant (FOCS 2006, pp. 509–517, 2006) seems to suggest that bases of size 2 might be indeed more powerful than bases of size 1. This result is with regard to a restrictive counting version of #SAT called #Pl-Rtw-Mon-3CNF. It is known that the problem is #P-hard, and its mod 2 version is ⊕P-hard. Yet its mod 7 version is solvable in polynomial time by holographic algorithms. This was ac complished by a suitable symmetric signature over a basis of size 2. We show that the same unexpected holographic algorithm can be realized over a basis of size 1. Furthermore we prove that 7 is the only modulus for which such an "accidental algorithm" exists.

Leslie Gabriel Valiant

I. V. Sokolov, Mikhail I. Kolobov, A. Gatti +1 more

We describe a continious variable teleportation scheme that allows to teleport the quantum state of distributed in space-time multimode electromagnetic field. Our teleportation protocol uses the spatially-multimode entangled Einstein-Podolsky-Rosen lihgt beams. We evaluate the "resolving power" of teleportation in space-time and specify the degrees of freedom of electromagnetic field whose quantum state can be effectively teleported. We call this scheme "quantum holographic teleportation" because it can be considered as an extension of conventional holography to quantum domain.