Halving the Cost of Quantum Algorithms with Randomization Article Swipe

PDF

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2409.03744

Quantum signal processing (QSP) provides a systematic framework for implementing a polynomial transformation of a linear operator, and unifies nearly all known quantum algorithms. In parallel, recent works have developed randomized compiling, a technique that promotes a unitary gate to a quantum channel and enables a quadratic suppression of error (i.e., $ε\rightarrow O(ε^2)$) at little to no overhead. Here we integrate randomized compiling into QSP through Stochastic Quantum Signal Processing. Our algorithm implements a probabilistic mixture of polynomials, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual polynomial. Because nearly all QSP-based algorithms exhibit query complexities scaling as $O(\log(1/ε))$ -- stemming from a result in functional analysis -- this error suppression reduces their query complexity by a factor that asymptotically approaches $1/2$. By the unifying capabilities of QSP, this reduction extends broadly to quantum algorithms, which we demonstrate on algorithms for real and imaginary time evolution, phase estimation, ground state preparation, and matrix inversion.

Related Topics

Randomized Controlled Trial

Concepts

Randomization Computer science Quantum Algorithm Physics Quantum mechanics Medicine Randomized controlled trial Surgery

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2409.03744
PDF: https://arxiv.org/pdf/2409.03744
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4403709456

All OpenAlex metadata

Raw OpenAlex JSON

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

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

Digital Object Identifier
Title: Halving the Cost of Quantum Algorithms with Randomization

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-09-05

Full publication date if available
Authors: John M. Martyn, Patrick Rall

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

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

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/2409.03744

Direct OA link when available
Concepts: Randomization, Computer science, Quantum, Algorithm, Physics, Quantum mechanics, Medicine, Randomized controlled trial, Surgery

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

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4403709456
doi	https://doi.org/10.48550/arxiv.2409.03744
ids.doi	https://doi.org/10.48550/arxiv.2409.03744
ids.openalex	https://openalex.org/W4403709456
fwci	0.0
type	preprint
title	Halving the Cost of Quantum Algorithms with Randomization
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.9944999814033508
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
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C204243189
concepts[0].level	3
concepts[0].score	0.6949530839920044
concepts[0].wikidata	https://www.wikidata.org/wiki/Q1363085
concepts[0].display_name	Randomization
concepts[1].id	https://openalex.org/C41008148
concepts[1].level	0
concepts[1].score	0.538509726524353
concepts[1].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[1].display_name	Computer science
concepts[2].id	https://openalex.org/C84114770
concepts[2].level	2
concepts[2].score	0.5310811400413513
concepts[2].wikidata	https://www.wikidata.org/wiki/Q46344
concepts[2].display_name	Quantum
concepts[3].id	https://openalex.org/C11413529
concepts[3].level	1
concepts[3].score	0.5266211628913879
concepts[3].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[3].display_name	Algorithm
concepts[4].id	https://openalex.org/C121332964
concepts[4].level	0
concepts[4].score	0.12627840042114258
concepts[4].wikidata	https://www.wikidata.org/wiki/Q413
concepts[4].display_name	Physics
concepts[5].id	https://openalex.org/C62520636
concepts[5].level	1
concepts[5].score	0.09313958883285522
concepts[5].wikidata	https://www.wikidata.org/wiki/Q944
concepts[5].display_name	Quantum mechanics
concepts[6].id	https://openalex.org/C71924100
concepts[6].level	0
concepts[6].score	0.07300865650177002
concepts[6].wikidata	https://www.wikidata.org/wiki/Q11190
concepts[6].display_name	Medicine
concepts[7].id	https://openalex.org/C168563851
concepts[7].level	2
concepts[7].score	0.06917724013328552
concepts[7].wikidata	https://www.wikidata.org/wiki/Q1436668
concepts[7].display_name	Randomized controlled trial
concepts[8].id	https://openalex.org/C141071460
concepts[8].level	1
concepts[8].score	0.0
concepts[8].wikidata	https://www.wikidata.org/wiki/Q40821
concepts[8].display_name	Surgery
keywords[0].id	https://openalex.org/keywords/randomization
keywords[0].score	0.6949530839920044
keywords[0].display_name	Randomization
keywords[1].id	https://openalex.org/keywords/computer-science
keywords[1].score	0.538509726524353
keywords[1].display_name	Computer science
keywords[2].id	https://openalex.org/keywords/quantum
keywords[2].score	0.5310811400413513
keywords[2].display_name	Quantum
keywords[3].id	https://openalex.org/keywords/algorithm
keywords[3].score	0.5266211628913879
keywords[3].display_name	Algorithm
keywords[4].id	https://openalex.org/keywords/physics
keywords[4].score	0.12627840042114258
keywords[4].display_name	Physics
keywords[5].id	https://openalex.org/keywords/quantum-mechanics
keywords[5].score	0.09313958883285522
keywords[5].display_name	Quantum mechanics
keywords[6].id	https://openalex.org/keywords/medicine
keywords[6].score	0.07300865650177002
keywords[6].display_name	Medicine
keywords[7].id	https://openalex.org/keywords/randomized-controlled-trial
keywords[7].score	0.06917724013328552
keywords[7].display_name	Randomized controlled trial
language	en
locations[0].id	pmh:oai:arXiv.org:2409.03744
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/2409.03744
locations[0].version	submittedVersion
locations[0].raw_type	text
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/2409.03744
locations[1].id	doi:10.48550/arxiv.2409.03744
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
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article-journal
locations[1].license_id
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.2409.03744
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5048507381
authorships[0].author.orcid	https://orcid.org/0000-0002-4065-6974
authorships[0].author.display_name	John M. Martyn
authorships[0].author_position	first
authorships[0].raw_author_name	Martyn, John M.
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5065493775
authorships[1].author.orcid
authorships[1].author.display_name	Patrick Rall
authorships[1].author_position	last
authorships[1].raw_author_name	Rall, Patrick
authorships[1].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/2409.03744
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Halving the Cost of Quantum Algorithms with Randomization
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.9944999814033508
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/W4391375266, https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W2051487156, https://openalex.org/W2073681303, https://openalex.org/W2390279801, https://openalex.org/W4391913857, https://openalex.org/W2358668433, https://openalex.org/W4396701345, https://openalex.org/W2376932109
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2409.03744
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/2409.03744
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
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/2409.03744
primary_location.id	pmh:oai:arXiv.org:2409.03744
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/2409.03744
primary_location.version	submittedVersion
primary_location.raw_type	text
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/2409.03744
publication_date	2024-09-05
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	5, 10, 14, 32, 36, 40, 45, 73, 89, 118, 132
abstract_inverted_index.--	115, 123
abstract_inverted_index.By	138
abstract_inverted_index.In	24
abstract_inverted_index.an	93, 100
abstract_inverted_index.as	113
abstract_inverted_index.at	53
abstract_inverted_index.by	131
abstract_inverted_index.in	120
abstract_inverted_index.no	56
abstract_inverted_index.of	13, 48, 76, 88, 99, 142
abstract_inverted_index.on	154
abstract_inverted_index.so	80
abstract_inverted_index.to	39, 55, 86, 148
abstract_inverted_index.we	59, 152
abstract_inverted_index.Our	70
abstract_inverted_index.QSP	64
abstract_inverted_index.all	20, 106
abstract_inverted_index.and	17, 43, 158, 167
abstract_inverted_index.for	8, 156
abstract_inverted_index.the	82, 139
abstract_inverted_index.Here	58
abstract_inverted_index.QSP,	143
abstract_inverted_index.from	117
abstract_inverted_index.gate	38
abstract_inverted_index.have	28
abstract_inverted_index.into	63
abstract_inverted_index.real	157
abstract_inverted_index.than	97
abstract_inverted_index.that	34, 81, 87, 98, 134
abstract_inverted_index.this	124, 144
abstract_inverted_index.time	160
abstract_inverted_index.with	92
abstract_inverted_index.(QSP)	3
abstract_inverted_index.error	49, 94, 125
abstract_inverted_index.known	21
abstract_inverted_index.phase	162
abstract_inverted_index.query	110, 129
abstract_inverted_index.state	165
abstract_inverted_index.their	128
abstract_inverted_index.which	151
abstract_inverted_index.works	27
abstract_inverted_index.$1/2$.	137
abstract_inverted_index.(i.e.,	50
abstract_inverted_index.Signal	68
abstract_inverted_index.chosen	79
abstract_inverted_index.factor	133
abstract_inverted_index.ground	164
abstract_inverted_index.linear	15
abstract_inverted_index.little	54
abstract_inverted_index.matrix	168
abstract_inverted_index.nearly	19, 105
abstract_inverted_index.recent	26
abstract_inverted_index.result	119
abstract_inverted_index.signal	1
abstract_inverted_index.target	90
abstract_inverted_index.Because	104
abstract_inverted_index.Quantum	0, 67
abstract_inverted_index.average	83
abstract_inverted_index.broadly	147
abstract_inverted_index.channel	42
abstract_inverted_index.enables	44
abstract_inverted_index.exhibit	109
abstract_inverted_index.extends	146
abstract_inverted_index.mixture	75
abstract_inverted_index.quantum	22, 41, 149
abstract_inverted_index.reduces	127
abstract_inverted_index.scaling	112
abstract_inverted_index.smaller	96
abstract_inverted_index.through	65
abstract_inverted_index.unifies	18
abstract_inverted_index.unitary	37
abstract_inverted_index.analysis	122
abstract_inverted_index.promotes	35
abstract_inverted_index.provides	4
abstract_inverted_index.stemming	116
abstract_inverted_index.unifying	140
abstract_inverted_index.O(ε^2)$)	52
abstract_inverted_index.QSP-based	107
abstract_inverted_index.algorithm	71
abstract_inverted_index.compiling	62
abstract_inverted_index.converges	85
abstract_inverted_index.developed	29
abstract_inverted_index.evolution	84
abstract_inverted_index.framework	7
abstract_inverted_index.function,	91
abstract_inverted_index.imaginary	159
abstract_inverted_index.integrate	60
abstract_inverted_index.operator,	16
abstract_inverted_index.overhead.	57
abstract_inverted_index.parallel,	25
abstract_inverted_index.quadratic	46
abstract_inverted_index.reduction	145
abstract_inverted_index.technique	33
abstract_inverted_index.Stochastic	66
abstract_inverted_index.algorithms	108, 155
abstract_inverted_index.approaches	136
abstract_inverted_index.compiling,	31
abstract_inverted_index.complexity	130
abstract_inverted_index.equivalent	101
abstract_inverted_index.evolution,	161
abstract_inverted_index.functional	121
abstract_inverted_index.implements	72
abstract_inverted_index.individual	102
abstract_inverted_index.inversion.	169
abstract_inverted_index.polynomial	11
abstract_inverted_index.processing	2
abstract_inverted_index.randomized	30, 61
abstract_inverted_index.systematic	6
abstract_inverted_index.Processing.	69
abstract_inverted_index.algorithms,	150
abstract_inverted_index.algorithms.	23
abstract_inverted_index.demonstrate	153
abstract_inverted_index.estimation,	163
abstract_inverted_index.polynomial.	103
abstract_inverted_index.suppression	47, 126
abstract_inverted_index.capabilities	141
abstract_inverted_index.complexities	111
abstract_inverted_index.implementing	9
abstract_inverted_index.polynomials,	77
abstract_inverted_index.preparation,	166
abstract_inverted_index.probabilistic	74
abstract_inverted_index.quadratically	95
abstract_inverted_index.strategically	78
abstract_inverted_index.$ε\rightarrow	51
abstract_inverted_index.asymptotically	135
abstract_inverted_index.transformation	12
abstract_inverted_index.$O(\log(1/ε))$	114
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	2
citation_normalized_percentile.value	0.20251315
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False