Holographic algorithms: from art to science

ABSTRACT

We develop the theory of holographic algorithms. We definea basis manifold and give characterizations of algebraic varieties of realizable symmetric generators and recognizers on this manifold. We present a polynomial time decision algorithm for the simultaneous realizability problem. Using the general machinery we are able to giveunexpected holographic algorithms for some counting problems, modulo certain Mersenne type integers. These counting problems are P-complete without the moduli. Going beyond symmetric signatures, we define d-admissibility and d-realizability for general signatures, and give a characterizationof 2-admissibility.

REFERENCES

• 1: S. Aaronson and D. Gottesman. Improved simulation of stabilizer circuits. Phys. Rev. A 70, 052328 (2004).
• 2: Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. MIT Press, 1996.
• 3: J.-Y. Cai and Vinay Choudhary. Some Results on Matchgates and Holographic Algorithms. In Proceedings of ICALP 2006, Part I. LNCS vol. 4051. pp 703--714. Also available at ECCC TR06-048, 2006.
• 4: J.-Y. Cai and Vinay Choudhary. Valiant's Holant Theorem and Matchgate Tensors. In Proceedings of TAMC 2006: LNCS vol. 3959, pp 248--261. Also available at ECCC Report TR05-118.
• 5: Jin-Yi Cai , Vinay Choudhary , Pinyan Lu, On the Theory of Matchgate Computations, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.305-318, June 13-March 16, 2007 [doi>10.1109/CCC.2007.22]
• 6: J.-Y. Cai and Pinyan Lu. On Symmetric Signatures in Holographic Algorithms. In Proc. of STACS 2007. LNCS Vol. 4393, pp 429--440. Available at ECCC Report TR06-135.
• 7: Jin-Yi Cai , Pinyan Lu, Bases Collapse in Holographic Algorithms, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.292-304, June 13-March 16, 2007 [doi>10.1109/CCC.2007.6]
• 8: J.-Y. Cai and Pinyan Lu. Holographic Algorithms: The Power of Dimensionality Resolved. Submitted. Also at ECCC TR07-020.
• 9: J.-Y. Cai and Pinyan Lu. On Block-wise Symmetric Signatures for Matchgates. Submitted. Also at ECCC TR07-019.
• 10: E. Farhi, J. Goldstone, S. Gutmann and M. Sipser. Quantum Computation by Adiabatic Evolution. http://arxiv.org/abs/quant-ph/0001106 (January 2000)
• 11: W. Foody and A. Hedayat. On theory and applications of BIB designs with repeated blocks, Annals Statist., 5 (1977), pp. 932--945.
• 12: W. Foody and A. Hedayat. Note: Correction to "On Theory and Application of BIB Designs with Repeated Blocks". Annals of Statistics, Vol. 7, No. 4 (Jul., 1979), p. 925.
• 13: D. Gottesman. The Heisenberg Representation of Quantum Computers. At http://arxiv.org/abs/quant-ph/9807006.
• 14: R. L. Graham, S.-Y. R. Li, and W.-C. W. Li. On the Structure of t-Designs. SIAM. J. on Algebraic and Discrete Methods 1, 8 (1980).
• 15: N. Linial and B. Rothschild. Incidence Matrices of Subsets--A Rank Formula. SIAM. J. on Algebraic and Discrete Methods 2, 333 (1981).
• 16: D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput. 11, 2:329--343.
• 17: M. Jerrum. Two-dimensional monomer-dimer systems are computationally intractable. J. Stat. Phys. 48 (1987) 121--134; erratum, 59 (1990) 1087--1088
• 18: P. W. Kasteleyn. The statistics of dimers on a lattice. Physica, 27: 1209--1225 (1961).
• 19: P. W. Kasteleyn. Graph Theory and Crystal Physics. In Graph Theory and Theoretical Physics, Academic Press, 43--110 (1967).
• 20: M. Kneser. "Aufgabe 360" . Jahresbericht der Deutschen Mathematiker-Vereinigung, 2. Abteilung 58: 27. 1955.
• 21: E. Knill. Fermionic Linear Optics and Matchgates. At http://arxiv.org/abs/quant-ph/0108033
• 22: L. Lovász. "Kneser's conjecture, chromatic number, and homotopy". Journal of Combinatorial Theory, Series A 25: 319--324. 1978.
• 23: Jiří Matoušek, A Combinatorial Proof of Kneser’s Conjecture, Combinatorica, v.24 n.1, p.163-170, January 2004 [doi>10.1007/s00493-004-0011-1]
• 24: K. Murota. Matrices and Matroids for Systems Analysis, Springer, Berlin, 2000.
• 25: H. N. V. Temperley and M. E. Fisher. Dimer problem in statistical mechanics -- an exact result. Philosophical Magazine 6: 1061-- 1063 (1961).
• 26: Salil P. Vadhan, The Complexity of Counting in Sparse, Regular, and Planar Graphs, SIAM Journal on Computing, v.31 n.2, p.398-427, 2001 [doi>10.1137/S0097539797321602]
• 27: Leslie G. Valiant, Quantum Circuits That Can Be Simulated Classically in Polynomial Time, SIAM Journal on Computing, v.31 n.4, p.1229-1254, 2002 [doi>10.1137/S0097539700377025]
• 28: Leslie G. Valiant, Expressiveness of matchgates, Theoretical Computer Science, v.289 n.1, p.457-471, 23 October 2002 [doi>10.1016/S0304-3975(01)00325-5]
• 29: Leslie G. Valiant, Holographic Algorithms (Extended Abstract), Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.306-315, October 17-19, 2004 [doi>10.1109/FOCS.2004.34]
• 30: L. G. Valiant. Holographic circuits. In Proc. 32nd International Colloquium on Automata, Languages and Programming, 2005, 1--15.
• 31: L. G. Valiant. Completeness for parity problems. In Proc. 11th International Computing and Combinatorics Conference (COCOON), LNCS, Vol. 3595, pp 1--8, (2005).
• 32: Leslie G. Valiant, Accidental Algorthims, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.509-517, October 21-24, 2006 [doi>10.1109/FOCS.2006.7]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
holographic algorithms, matchgates, signatures