Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0708.3396 · Lecture notes in computer science

Optimal Quantum Adversary Lower Bounds for Ordered Search

Andrew M. Childs, Troy Lee

Published Jan 1, 2008• 20 citations
arXivHTMLPDF
DOI
10.1007/978-3-540-70575-8_71

Related papers

A lower bound for quantum search of an ordered list

Harry Buhrman, Ronald de Wolf

Information Processing Letters•Jun 1, 1999•18 citations

Symmetry-Assisted Adversaries for Quantum State Generation

Andris Ambainis, Loïck Magnin, Martin Roetteler +1 more

We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum state generation might be a route to tackle the GRAPH-ISOMORPHISM problem. We show that for the related problem of INDEX-ERASURE our method leads to a lower bound of square root of N which matches an upper bound obtained via reduction to quantum search on N elements. This closes an open problem first raised by Shi [FOCS'02]. Our approach is based on two ideas: (i) on the one hand we generalize the known additive and multiplicative adversary methods to the case of quantum state generation, (ii) on the other hand we show how the symmetries of the underlying problem can be leveraged for the design of optimal adversary matrices and dramatically simplify the computation of adversary bounds. Taken together, these two ideas give the new result for INDEX-ERASURE by using the representation theory of the symmetric group. Also, the method can lead to lower bounds even for small success probability, contrary to the standard adversary method. Furthermore, we answer an open question due to Spalek [CCC'08] by showing that the multiplicative version of the adversary method is stronger than the additive one for any problem. Finally, we prove that the multiplicative bound satisfies a strong direct product theorem, extending a result by Spalek to quantum state generation problems.

arXiv:1012.2112•IEEE Conference on Computational Complexity (CCC)•Jun 1, 2011•66 citations

Adversary Lower Bounds for Nonadaptive Quantum Algorithms

Pascal Koiran, Jürgen Landes, Natacha Portier +1 more

Lecture notes in computer science•Jan 1, 2008•0 citations

Certifying Adversarial Robustness of Quantum Classifiers under Known-Readout Query Access

Ji Guan, Mingyu Huang

A quantum classifier assigns labels by evolving an input quantum state and measuring the output, so repeated executions reveal only a distribution over labels. We study certified adversarial robustness for such classifiers under known-readout query access (KRQA), where an evaluator can prepare inputs, knows the quantum measurement, and observes finite-shot outcomes but cannot inspect the internal evolution, parameters, or gradients. We give a measurement-only framework that returns two complementary guarantees for each input: a lower bound ruling out untargeted errors within a radius, and an attack-independent upper bound witnessing an adversarial state within a radius. Both are estimable from the known readout measurement and sampled outcomes, require no tomography or circuit description, and have finite-sample control of probability-estimation error. The upper bound uses gap operators induced by the quantum measurement; the lower bound relaxes state-space search to an efficient optimization over outcome distributions with operator-spectrum constraints, yielding certificates that are never weaker than prior probability-only certificates and can be strictly stronger when the spectral constraints are active. On tractable instances, we compare the lower bound with numerical white-box reference estimates; across multiple classifiers, the upper bound remains informative when standard attacks fail. We further demonstrate real-device feasibility on IBM Quantum hardware: from 40 executions of two 8-qubit quantum neural networks, our method estimates both bounds, with the expected lower-upper ordering on every tested input. Taken together, these results show that robustness claims for quantum classifiers can be audited directly from observable statistics under KRQA.

quant-pharXiv:2609.11637•ACM SIGSAC Conference on Computer and Communications Security (CCS)•Sep 11, 2026•0 citations

Adversary lower bounds for nonadaptive quantum algorithms

Pascal Koiran, Jürgen Landes, Natacha Portier +1 more

arXiv:0804.1440•Journal of Computer and System Sciences•Oct 17, 2009•8 citations

A new quantum lower bound method, with an application to strong direct product theorem for quantum search

Andris Ambainis

We present a new method for proving lower bounds on quantum query algorithms. The new method is an extension of adversary method, by analyzing the eigenspace structure of the problem. Using the new method, we prove a strong direct product theorem for quantum search. This result was previously proven by Klauck, Spalek and de Wolf (quant-ph/0402123) using polynomials method. No proof using adversary method was known before.

arXiv:quant-ph/0508200•Aug 26, 2005•19 citations
We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum state generation might be a route to tackle the GRAPH-ISOMORPHISM problem. We show that for the related problem of INDEX-ERASURE our method leads to a lower bound of square root of N which matches an upper bound obtained via reduction to quantum search on N elements. This closes an open problem first raised by Shi [FOCS'02]. Our approach is based on two ideas: (i) on the one hand we generalize the known additive and multiplicative adversary methods to the case of quantum state generation, (ii) on the other hand we show how the symmetries of the underlying problem can be leveraged for the design of optimal adversary matrices and dramatically simplify the computation of adversary bounds. Taken together, these two ideas give the new result for INDEX-ERASURE by using the representation theory of the symmetric group. Also, the method can lead to lower bounds even for small success probability, contrary to the standard adversary method. Furthermore, we answer an open question due to Spalek [CCC'08] by showing that the multiplicative version of the adversary method is stronger than the additive one for any problem. Finally, we prove that the multiplicative bound satisfies a strong direct product theorem, extending a result by Spalek to quantum state generation problems.
A quantum classifier assigns labels by evolving an input quantum state and measuring the output, so repeated executions reveal only a distribution over labels. We study certified adversarial robustness for such classifiers under known-readout query access (KRQA), where an evaluator can prepare inputs, knows the quantum measurement, and observes finite-shot outcomes but cannot inspect the internal evolution, parameters, or gradients. We give a measurement-only framework that returns two complementary guarantees for each input: a lower bound ruling out untargeted errors within a radius, and an attack-independent upper bound witnessing an adversarial state within a radius. Both are estimable from the known readout measurement and sampled outcomes, require no tomography or circuit description, and have finite-sample control of probability-estimation error. The upper bound uses gap operators induced by the quantum measurement; the lower bound relaxes state-space search to an efficient optimization over outcome distributions with operator-spectrum constraints, yielding certificates that are never weaker than prior probability-only certificates and can be strictly stronger when the spectral constraints are active. On tractable instances, we compare the lower bound with numerical white-box reference estimates; across multiple classifiers, the upper bound remains informative when standard attacks fail. We further demonstrate real-device feasibility on IBM Quantum hardware: from 40 executions of two 8-qubit quantum neural networks, our method estimates both bounds, with the expected lower-upper ordering on every tested input. Taken together, these results show that robustness claims for quantum classifiers can be audited directly from observable statistics under KRQA.