Extending Matchgate Simulation Methods to Universal Quantum Circuits Article Swipe

PDF

Avinash Mocherla , Lingling Lao , Dan E. Browne ·

YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2302.02654

Matchgates are a family of parity-preserving two-qubit gates, nearest-neighbour circuits of which are known to be classically simulable in polynomial time. In this work, we present a simulation method to classically simulate an $\boldsymbol{n}$-qubit circuit containing $\boldsymbol{N}$ gates, $\boldsymbol{m}$ of which are universality-enabling gates and $\boldsymbol{N-m}$ of which are matchgates, in the setting of single-qubit Pauli measurements and product state inputs. The universality-enabling gates we consider include the SWAP, CZ, and CPhase gates. For fixed $\boldsymbol{m}$ as $\boldsymbol{n} \rightarrow \boldsymbol{\infty}$, the resource cost, $\boldsymbol{T}$, scales as $\boldsymbol{\mathcal{O}\left(\left(\frac{en}{m+1}\right)^{2m+2}\right)}$. For $\boldsymbol{m}$ scaling as a linear function of $\boldsymbol{n}$, however, $\boldsymbol{T}$ scale as $\boldsymbol{\mathcal{O}\left(2^{2nH\left(\frac{m+1}{n}\right)}\right)}$, where $\boldsymbol{H}(λ)$ is the binary entropy function.

Related Topics

Combinatorics

Physics

Pauli Exclusion Principle

Mathematical Analysis

Geometry

Concepts

Qubit Universality (dynamical systems) Combinatorics Physics Scaling Exponential function Pauli exclusion principle Mathematics Quantum circuit Discrete mathematics Quantum Quantum mechanics Mathematical physics Mathematical analysis Quantum error correction Geometry

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2302.02654
PDF: https://arxiv.org/pdf/2302.02654
OA Status: green
Cited By: 2
Related Works: 10
OpenAlex ID: https://openalex.org/W4319453391

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4319453391

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2302.02654

Digital Object Identifier
Title: Extending Matchgate Simulation Methods to Universal Quantum Circuits

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2023

Year of publication
Publication date: 2023-02-06

Full publication date if available
Authors: Avinash Mocherla, Lingling Lao, Dan E. Browne

List of authors in order
Landing page: https://arxiv.org/abs/2302.02654

Publisher landing page
PDF URL: https://arxiv.org/pdf/2302.02654

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2302.02654

Direct OA link when available
Concepts: Qubit, Universality (dynamical systems), Combinatorics, Physics, Scaling, Exponential function, Pauli exclusion principle, Mathematics, Quantum circuit, Discrete mathematics, Quantum, Quantum mechanics, Mathematical physics, Mathematical analysis, Quantum error correction, Geometry

Top concepts (fields/topics) attached by OpenAlex
Cited by: 2

Total citation count in OpenAlex
Citations by year (recent): 2025: 1, 2023: 1

Per-year citation counts (last 5 years)
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4319453391
doi	https://doi.org/10.48550/arxiv.2302.02654
ids.doi	https://doi.org/10.48550/arxiv.2302.02654
ids.openalex	https://openalex.org/W4319453391
fwci
type	preprint
title	Extending Matchgate Simulation Methods to Universal Quantum Circuits
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10682
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9998999834060669
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Quantum Computing Algorithms and Architecture
topics[1].id	https://openalex.org/T10382
topics[1].field.id	https://openalex.org/fields/31
topics[1].field.display_name	Physics and Astronomy
topics[1].score	0.9950000047683716
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/3107
topics[1].subfield.display_name	Atomic and Molecular Physics, and Optics
topics[1].display_name	Quantum and electron transport phenomena
topics[2].id	https://openalex.org/T10020
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9940000176429749
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1702
topics[2].subfield.display_name	Artificial Intelligence
topics[2].display_name	Quantum Information and Cryptography
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C203087015
concepts[0].level	3
concepts[0].score	0.6240348815917969
concepts[0].wikidata	https://www.wikidata.org/wiki/Q378201
concepts[0].display_name	Qubit
concepts[1].id	https://openalex.org/C183992945
concepts[1].level	2
concepts[1].score	0.5859686136245728
concepts[1].wikidata	https://www.wikidata.org/wiki/Q2495574
concepts[1].display_name	Universality (dynamical systems)
concepts[2].id	https://openalex.org/C114614502
concepts[2].level	1
concepts[2].score	0.5588739514350891
concepts[2].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[2].display_name	Combinatorics
concepts[3].id	https://openalex.org/C121332964
concepts[3].level	0
concepts[3].score	0.5253159999847412
concepts[3].wikidata	https://www.wikidata.org/wiki/Q413
concepts[3].display_name	Physics
concepts[4].id	https://openalex.org/C99844830
concepts[4].level	2
concepts[4].score	0.5148157477378845
concepts[4].wikidata	https://www.wikidata.org/wiki/Q102441924
concepts[4].display_name	Scaling
concepts[5].id	https://openalex.org/C151376022
concepts[5].level	2
concepts[5].score	0.48392611742019653
concepts[5].wikidata	https://www.wikidata.org/wiki/Q168698
concepts[5].display_name	Exponential function
concepts[6].id	https://openalex.org/C110340908
concepts[6].level	2
concepts[6].score	0.4728686511516571
concepts[6].wikidata	https://www.wikidata.org/wiki/Q131594
concepts[6].display_name	Pauli exclusion principle
concepts[7].id	https://openalex.org/C33923547
concepts[7].level	0
concepts[7].score	0.4253047704696655
concepts[7].wikidata	https://www.wikidata.org/wiki/Q395
concepts[7].display_name	Mathematics
concepts[8].id	https://openalex.org/C124148022
concepts[8].level	5
concepts[8].score	0.41132283210754395
concepts[8].wikidata	https://www.wikidata.org/wiki/Q2122210
concepts[8].display_name	Quantum circuit
concepts[9].id	https://openalex.org/C118615104
concepts[9].level	1
concepts[9].score	0.3857659697532654
concepts[9].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[9].display_name	Discrete mathematics
concepts[10].id	https://openalex.org/C84114770
concepts[10].level	2
concepts[10].score	0.3841206431388855
concepts[10].wikidata	https://www.wikidata.org/wiki/Q46344
concepts[10].display_name	Quantum
concepts[11].id	https://openalex.org/C62520636
concepts[11].level	1
concepts[11].score	0.37699106335639954
concepts[11].wikidata	https://www.wikidata.org/wiki/Q944
concepts[11].display_name	Quantum mechanics
concepts[12].id	https://openalex.org/C37914503
concepts[12].level	1
concepts[12].score	0.35649216175079346
concepts[12].wikidata	https://www.wikidata.org/wiki/Q156495
concepts[12].display_name	Mathematical physics
concepts[13].id	https://openalex.org/C134306372
concepts[13].level	1
concepts[13].score	0.12751176953315735
concepts[13].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[13].display_name	Mathematical analysis
concepts[14].id	https://openalex.org/C51003876
concepts[14].level	4
concepts[14].score	0.11652854084968567
concepts[14].wikidata	https://www.wikidata.org/wiki/Q1536431
concepts[14].display_name	Quantum error correction
concepts[15].id	https://openalex.org/C2524010
concepts[15].level	1
concepts[15].score	0.10354766249656677
concepts[15].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[15].display_name	Geometry
keywords[0].id	https://openalex.org/keywords/qubit
keywords[0].score	0.6240348815917969
keywords[0].display_name	Qubit
keywords[1].id	https://openalex.org/keywords/universality
keywords[1].score	0.5859686136245728
keywords[1].display_name	Universality (dynamical systems)
keywords[2].id	https://openalex.org/keywords/combinatorics
keywords[2].score	0.5588739514350891
keywords[2].display_name	Combinatorics
keywords[3].id	https://openalex.org/keywords/physics
keywords[3].score	0.5253159999847412
keywords[3].display_name	Physics
keywords[4].id	https://openalex.org/keywords/scaling
keywords[4].score	0.5148157477378845
keywords[4].display_name	Scaling
keywords[5].id	https://openalex.org/keywords/exponential-function
keywords[5].score	0.48392611742019653
keywords[5].display_name	Exponential function
keywords[6].id	https://openalex.org/keywords/pauli-exclusion-principle
keywords[6].score	0.4728686511516571
keywords[6].display_name	Pauli exclusion principle
keywords[7].id	https://openalex.org/keywords/mathematics
keywords[7].score	0.4253047704696655
keywords[7].display_name	Mathematics
keywords[8].id	https://openalex.org/keywords/quantum-circuit
keywords[8].score	0.41132283210754395
keywords[8].display_name	Quantum circuit
keywords[9].id	https://openalex.org/keywords/discrete-mathematics
keywords[9].score	0.3857659697532654
keywords[9].display_name	Discrete mathematics
keywords[10].id	https://openalex.org/keywords/quantum
keywords[10].score	0.3841206431388855
keywords[10].display_name	Quantum
keywords[11].id	https://openalex.org/keywords/quantum-mechanics
keywords[11].score	0.37699106335639954
keywords[11].display_name	Quantum mechanics
keywords[12].id	https://openalex.org/keywords/mathematical-physics
keywords[12].score	0.35649216175079346
keywords[12].display_name	Mathematical physics
keywords[13].id	https://openalex.org/keywords/mathematical-analysis
keywords[13].score	0.12751176953315735
keywords[13].display_name	Mathematical analysis
keywords[14].id	https://openalex.org/keywords/quantum-error-correction
keywords[14].score	0.11652854084968567
keywords[14].display_name	Quantum error correction
keywords[15].id	https://openalex.org/keywords/geometry
keywords[15].score	0.10354766249656677
keywords[15].display_name	Geometry
language	en
locations[0].id	pmh:oai:arXiv.org:2302.02654
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2302.02654
locations[0].version	submittedVersion
locations[0].raw_type
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2302.02654
locations[1].id	doi:10.48550/arxiv.2302.02654
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2302.02654
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5053851880
authorships[0].author.orcid
authorships[0].author.display_name	Avinash Mocherla
authorships[0].author_position	first
authorships[0].raw_author_name	Mocherla, Avinash
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5022996325
authorships[1].author.orcid	https://orcid.org/0000-0001-6870-5670
authorships[1].author.display_name	Lingling Lao
authorships[1].author_position	middle
authorships[1].raw_author_name	Lao, Lingling
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5058916700
authorships[2].author.orcid	https://orcid.org/0000-0003-3001-158X
authorships[2].author.display_name	Dan E. Browne
authorships[2].author_position	last
authorships[2].raw_author_name	Browne, Dan E.
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2302.02654
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Extending Matchgate Simulation Methods to Universal Quantum Circuits
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10682
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9998999834060669
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Quantum Computing Algorithms and Architecture
related_works	https://openalex.org/W3006983566, https://openalex.org/W2052382920, https://openalex.org/W2024371448, https://openalex.org/W1611230162, https://openalex.org/W2352949123, https://openalex.org/W2951304272, https://openalex.org/W2747066503, https://openalex.org/W1572121409, https://openalex.org/W3100342955, https://openalex.org/W2016252684
cited_by_count	2
counts_by_year[0].year	2025
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2023
counts_by_year[1].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2302.02654
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2302.02654
best_oa_location.version	submittedVersion
best_oa_location.raw_type
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2302.02654
primary_location.id	pmh:oai:arXiv.org:2302.02654
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2302.02654
primary_location.version	submittedVersion
primary_location.raw_type
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2302.02654
publication_date	2023-02-06
publication_year	2023
referenced_works_count	0
abstract_inverted_index.a	2, 26, 91
abstract_inverted_index.In	21
abstract_inverted_index.an	32
abstract_inverted_index.as	76, 85, 90, 99
abstract_inverted_index.be	15
abstract_inverted_index.in	18, 50
abstract_inverted_index.is	103
abstract_inverted_index.of	4, 10, 39, 46, 53, 94
abstract_inverted_index.to	14, 29
abstract_inverted_index.we	24, 64
abstract_inverted_index.CZ,	69
abstract_inverted_index.For	73, 87
abstract_inverted_index.The	61
abstract_inverted_index.and	44, 57, 70
abstract_inverted_index.are	1, 12, 41, 48
abstract_inverted_index.the	51, 67, 80, 104
abstract_inverted_index.this	22
abstract_inverted_index.Pauli	55
abstract_inverted_index.SWAP,	68
abstract_inverted_index.cost,	82
abstract_inverted_index.fixed	74
abstract_inverted_index.gates	43, 63
abstract_inverted_index.known	13
abstract_inverted_index.scale	98
abstract_inverted_index.state	59
abstract_inverted_index.time.	20
abstract_inverted_index.where	101
abstract_inverted_index.which	11, 40, 47
abstract_inverted_index.work,	23
abstract_inverted_index.CPhase	71
abstract_inverted_index.binary	105
abstract_inverted_index.family	3
abstract_inverted_index.gates,	7, 37
abstract_inverted_index.gates.	72
abstract_inverted_index.linear	92
abstract_inverted_index.method	28
abstract_inverted_index.scales	84
abstract_inverted_index.circuit	34
abstract_inverted_index.entropy	106
abstract_inverted_index.include	66
abstract_inverted_index.inputs.	60
abstract_inverted_index.present	25
abstract_inverted_index.product	58
abstract_inverted_index.scaling	89
abstract_inverted_index.setting	52
abstract_inverted_index.circuits	9
abstract_inverted_index.consider	65
abstract_inverted_index.function	93
abstract_inverted_index.however,	96
abstract_inverted_index.resource	81
abstract_inverted_index.simulate	31
abstract_inverted_index.function.	107
abstract_inverted_index.simulable	17
abstract_inverted_index.two-qubit	6
abstract_inverted_index.Matchgates	0
abstract_inverted_index.containing	35
abstract_inverted_index.polynomial	19
abstract_inverted_index.simulation	27
abstract_inverted_index.\rightarrow	78
abstract_inverted_index.classically	16, 30
abstract_inverted_index.matchgates,	49
abstract_inverted_index.measurements	56
abstract_inverted_index.single-qubit	54
abstract_inverted_index.$\boldsymbol{n}	77
abstract_inverted_index.$\boldsymbol{N}$	36
abstract_inverted_index.$\boldsymbol{T}$	97
abstract_inverted_index.$\boldsymbol{m}$	38, 75, 88
abstract_inverted_index.$\boldsymbol{T}$,	83
abstract_inverted_index.$\boldsymbol{n}$,	95
abstract_inverted_index.nearest-neighbour	8
abstract_inverted_index.parity-preserving	5
abstract_inverted_index.$\boldsymbol{N-m}$	45
abstract_inverted_index.$\boldsymbol{H}(λ)$	102
abstract_inverted_index.\boldsymbol{\infty}$,	79
abstract_inverted_index.universality-enabling	42, 62
abstract_inverted_index.$\boldsymbol{n}$-qubit	33
abstract_inverted_index.$\boldsymbol{\mathcal{O}\left(2^{2nH\left(\frac{m+1}{n}\right)}\right)}$,	100
abstract_inverted_index.$\boldsymbol{\mathcal{O}\left(\left(\frac{en}{m+1}\right)^{2m+2}\right)}$.	86
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile