Abstract
Graph states have become a key class of states within quantum computation. They form a basis for universal quantum computation, capture key properties of entanglement, are related to quantum error correction, establish links to graph theory, violate Bell inequalities, and have elegant and short graph-theoretical descriptions. We give here a rigorous analysis of the resources required for producing graph states. Using a novel graph-contraction procedure, we show that any graph state can be prepared by a linear-size constant-depth quantum circuit, and we establish trade-offs between depth and width. We show that any minimal-width quantum circuit requires gates that acts on several qubits, regardless of the depth. We relate the complexity of preparing graph states to a new graph-theoretical concept, the local minimum degree, and show that it captures basic properties of graph states.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aliferis, P., Leung, D.W.: Computation by measurements: A unifying picture. Physical Review A 70, 062314 (2004)
Bouchet, A.: Diagraph decompositions and eulerian systems. SIAM J. Algebraic Discrete Methods 8, 323–337 (1987)
Bouchet, A.: Connectivity of isotropic systems. In: Combinatorial Mathematics: Proc. of the Third International Conference. Ann. New York Acad. Sci., vol. 555, pp. 81–93 (1989)
Bouchet, A.: κ-transformations, local complementations and switching. In: Cycles and rays: Basic structures in finite and infinite graphs. NATO Adv. Sci. Inst. Ser., vol. C 301, pp. 41–50. Kluwer Acad. Publ., Dordrecht (1990)
Bouchet, A.: Circle graph obstructions. J. Comb. Theory Ser. B 60(1), 107–144 (1994)
Duan, L.M., Raussendorf, R.: Efficient quantum computation with probabilistic quantum gates. Phys. Rev. Lett. 95, 080503 (2005)
Eisert, J., Gross, D.: Multi-particle entanglement. In: Lectures on Quantum Information, Wiley-VCH, Berlin (2006)
de Fraysseix, H.: Local complementation and interlacement graphs. Discrete Mathematics 33(1), 29–35 (1981)
Geelen, J.F.: Matchings, Matroids and Unimodular Matrices. PhD thesis, Univ. Waterloo (1995)
Goyal, K., McCauley, A., Raussendorf, R.: Purification of large bi-colorable graph states (May 2006) quant-ph/0605228
Hein, M., Dür, W., Eisert, J., Raussendorf, R., Van den Nest, M., Briegel, H.J.: Entanglement in graph states and its applications. In: Proc. of the Int. School of Physics Enrico Fermi on Quantum Computers, Algorithms and Chaos (July 2005) quant-ph/0602096
Markov, I., Shi, Y.: Simulating quantum computation by contracting tensor networks. In: Ninth Workshop on Quantum Information Processing (January 2006) (No proceedings)
Oum, S.-i.: Approximating rank-width and clique-width quickly. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 49–58. Springer, Heidelberg (2005)
Perdrix, S.: State transfer instead of teleportation in measurement-based quantum computation. International Journal of Quantum Information 3(1), 219–224 (2005)
Raussendorf, R., Briegel, H.J.: A one-way quantum computer. Physical Review Letters 86, 5188–5191 (2001)
Shi, Y., Duan, L.M., Vidal, G.: Classical simulation of quantum many-body systems with a tree tensor network (in completion) (February 2006)
Van den Nest, M.: Local equivalence of stabilizer states and codes. PhD thesis, Faculty of Engineering, K.U. Leuven, Belgium (May 2005)
Van den Nest, M., Miyake, A., Dür, W., Briegel, H.J.: Universal resources for measurement–based quantum computation (April 2006) quant-ph/0604010
Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Metody Diskret. Analiz. 3, 25–30 (1964) (in Russian)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Høyer, P., Mhalla, M., Perdrix, S. (2006). Resources Required for Preparing Graph States. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_64
Download citation
DOI: https://doi.org/10.1007/11940128_64
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)