Simulating quantum computations with Tutte polynomials

Abstract We establish a classical heuristic algorithm for exactly computing quantum probability amplitudes. Our algorithm is based on mapping output probability amplitudes of quantum circuits to evaluations of the Tutte polynomial of graphic matroids. The algorithm evaluates the Tutte polynomial rec...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Ryan L. Mann
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2021
Materias:	Physics QC1-999 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/ecb6f1c26e1647fd959ce18e1493a380
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:ecb6f1c26e1647fd959ce18e1493a380
record_format	dspace
spelling	oai:doaj.org-article:ecb6f1c26e1647fd959ce18e1493a3802021-12-02T15:14:37ZSimulating quantum computations with Tutte polynomials10.1038/s41534-021-00477-02056-6387https://doaj.org/article/ecb6f1c26e1647fd959ce18e1493a3802021-09-01T00:00:00Zhttps://doi.org/10.1038/s41534-021-00477-0https://doaj.org/toc/2056-6387Abstract We establish a classical heuristic algorithm for exactly computing quantum probability amplitudes. Our algorithm is based on mapping output probability amplitudes of quantum circuits to evaluations of the Tutte polynomial of graphic matroids. The algorithm evaluates the Tutte polynomial recursively using the deletion–contraction property while attempting to exploit structural properties of the matroid. We consider several variations of our algorithm and present experimental results comparing their performance on two classes of random quantum circuits. Further, we obtain an explicit form for Clifford circuit amplitudes in terms of matroid invariants and an alternative efficient classical algorithm for computing the output probability amplitudes of Clifford circuits.Ryan L. MannNature PortfolioarticlePhysicsQC1-999Electronic computers. Computer scienceQA75.5-76.95ENnpj Quantum Information, Vol 7, Iss 1, Pp 1-8 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Physics QC1-999 Electronic computers. Computer science QA75.5-76.95
spellingShingle	Physics QC1-999 Electronic computers. Computer science QA75.5-76.95 Ryan L. Mann Simulating quantum computations with Tutte polynomials
description	Abstract We establish a classical heuristic algorithm for exactly computing quantum probability amplitudes. Our algorithm is based on mapping output probability amplitudes of quantum circuits to evaluations of the Tutte polynomial of graphic matroids. The algorithm evaluates the Tutte polynomial recursively using the deletion–contraction property while attempting to exploit structural properties of the matroid. We consider several variations of our algorithm and present experimental results comparing their performance on two classes of random quantum circuits. Further, we obtain an explicit form for Clifford circuit amplitudes in terms of matroid invariants and an alternative efficient classical algorithm for computing the output probability amplitudes of Clifford circuits.
format	article
author	Ryan L. Mann
author_facet	Ryan L. Mann
author_sort	Ryan L. Mann
title	Simulating quantum computations with Tutte polynomials
title_short	Simulating quantum computations with Tutte polynomials
title_full	Simulating quantum computations with Tutte polynomials
title_fullStr	Simulating quantum computations with Tutte polynomials
title_full_unstemmed	Simulating quantum computations with Tutte polynomials
title_sort	simulating quantum computations with tutte polynomials
publisher	Nature Portfolio
publishDate	2021
url	https://doaj.org/article/ecb6f1c26e1647fd959ce18e1493a380
work_keys_str_mv	AT ryanlmann simulatingquantumcomputationswithtuttepolynomials
_version_	1718387605982150656

Simulating quantum computations with Tutte polynomials

Ejemplares similares