2015/11/04 by Mingji Xia, Xia, Mingji
Computer Science · #68Q99 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Quantum Computing Algorithms and Architecture #cs.CC #msc:68Q99
paper · pdf · doi:10.48550/arxiv.1511.01230
arxiv created 2015/11/04 · openalex publication_date 2015/11/04 · arxiv updated 2015/11/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A holographic algorithm solves a problem in 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. Base collapse was discovered for small domain n=2,3,4. For n=3, 4, the base collapse was proved under the condition that there is a full rank generator. We prove for any n, the base collapse to a r≤ \lfloor log n \rfloor, with some similar conditions. One of them is that the original problem is defined by one symmetric function. In the proof, we utilize elementary matchgate transformations instead of matchgate identities.