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

Springer eBooks

The quantum case

Stephen Bruce Sontz

Published Jan 1, 2015• 0 citations
OpenAlex

Related papers

Query Complexity: Worst-Case Quantum Versus Average-Case Classical

Scott Aaronson

In this note we investigate the relationship between worst-case quantum query complexity and average-case classical query complexity. Specifically, we show that if a quantum computer can evaluate a total Boolean function f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^5) queries in the average case, under a uniform distribution of inputs. If f is monotone, we show furthermore that only O(T^3) queries are needed. Previously, Beals et al. (1998) showed that if a quantum computer can evaluate f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^6) queries in the worst case, or O(T^4) if f is monotone. The optimal bound is conjectured to be O(T^2), but improving on O(T^6) remains an open problem. Relating worst-case quantum complexity to average-case classical complexity may suggest new ways to reduce the polynomial gap in the ordinary worst-case versus worst-case setting.

arXiv:cs/0001013•Jan 19, 2000•0 citations

Enter the quantum

Princeton University Press eBooks•Jan 17, 2023•0 citations

Quantum-mechanical cases

Arif Ahmed

Cambridge University Press eBooks•Aug 6, 2014•0 citations

quantum Case-Based Reasoning (qCBR)

Parfait Atchade-Adelomou, Daniel Casado-Faulí, Elisabet Golobardes-Ribe +1 more

Case-Based Reasoning (CBR) is an artificial intelligence approach to problem-solving with a good record of success. This article proposes using Quantum Computing to improve some of the key processes of CBR, such that a Quantum Case-Based Reasoning (qCBR) paradigm can be defined. The focus is set on designing and implementing a qCBR based on the variational principle that improves its classical counterpart in terms of average accuracy, scalability and tolerance to overlapping. A comparative study of the proposed qCBR with a classic CBR is performed for the case of the Social Workers' Problem as a sample of a combinatorial optimization problem with overlapping. The algorithm's quantum feasibility is modelled with docplex and tested on IBMQ computers, and experimented on the Qibo framework.

arXiv:2104.00409•Apr 1, 2021•1 citation

Quantum question

The New Scientist•Oct 1, 2013•0 citations

Worst-case Harrow-Hassidim-Lloyd algorithm with average-case correct quantum Fourier transform

Changpeng Shao

In [\href{https://quantum-journal.org/papers/q-2022-12-07-872/}{Quantum 6, 872, 2022}], Linden and de Wolf proposed a lightweight protocol for verifying average-case correctness of the quantum Fourier transform (QFT). They showed that good average-case QFT performance is sufficient for good worst-case performance in several quantum information-processing tasks. In this work, we study whether such average-case guarantees are also sufficient when the QFT is used coherently inside the Harrow--Hassidim--Lloyd algorithm. We show that the original average-case condition is not quite strong enough for this purpose, due to possible relative phase errors between different eigenspaces. To address this, we introduce a strengthened Linden--de Wolf-type verification condition that controls the relevant coherences, and prove that it guarantees worst-case correctness of the HHL algorithm in several natural settings.

quant-pharXiv:2604.10428•Apr 14, 2026•0 citations
In this note we investigate the relationship between worst-case quantum query complexity and average-case classical query complexity. Specifically, we show that if a quantum computer can evaluate a total Boolean function f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^5) queries in the average case, under a uniform distribution of inputs. If f is monotone, we show furthermore that only O(T^3) queries are needed. Previously, Beals et al. (1998) showed that if a quantum computer can evaluate f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^6) queries in the worst case, or O(T^4) if f is monotone. The optimal bound is conjectured to be O(T^2), but improving on O(T^6) remains an open problem. Relating worst-case quantum complexity to average-case classical complexity may suggest new ways to reduce the polynomial gap in the ordinary worst-case versus worst-case setting.
Case-Based Reasoning (CBR) is an artificial intelligence approach to problem-solving with a good record of success. This article proposes using Quantum Computing to improve some of the key processes of CBR, such that a Quantum Case-Based Reasoning (qCBR) paradigm can be defined. The focus is set on designing and implementing a qCBR based on the variational principle that improves its classical counterpart in terms of average accuracy, scalability and tolerance to overlapping. A comparative study of the proposed qCBR with a classic CBR is performed for the case of the Social Workers' Problem as a sample of a combinatorial optimization problem with overlapping. The algorithm's quantum feasibility is modelled with docplex and tested on IBMQ computers, and experimented on the Qibo framework.
In [\href{https://quantum-journal.org/papers/q-2022-12-07-872/}{Quantum 6, 872, 2022}], Linden and de Wolf proposed a lightweight protocol for verifying average-case correctness of the quantum Fourier transform (QFT). They showed that good average-case QFT performance is sufficient for good worst-case performance in several quantum information-processing tasks. In this work, we study whether such average-case guarantees are also sufficient when the QFT is used coherently inside the Harrow--Hassidim--Lloyd algorithm. We show that the original average-case condition is not quite strong enough for this purpose, due to possible relative phase errors between different eigenspaces. To address this, we introduce a strengthened Linden--de Wolf-type verification condition that controls the relevant coherences, and prove that it guarantees worst-case correctness of the HHL algorithm in several natural settings.