TY - GEN
T1 - New Lower-Bounds for Quantum Computation with Non-Collapsing Measurements
AU - Miloschewsky, David
AU - Podder, Supartha
N1 - Publisher Copyright:
© David Miloschewsky and Supartha Podder.
PY - 2025/7/29
Y1 - 2025/7/29
N2 - Aaronson, Bouland, Fitzsimons and Lee [5] introduced the complexity class PDQP (which was original labeled naCQP), an alteration of BQP enhanced with the ability to obtain non-collapsing measurements, samples of quantum states without collapsing them. Although SZK ⊆ PDQP, it still requires Ω(N1/4) queries to solve unstructured search. We formulate an alternative equivalent definition of PDQP, which we use to prove the positive weighted adversary lower-bounding method, establishing multiple tighter bounds and a trade-off between queries and non-collapsing measurements. We utilize the technique in order to analyze the query complexity of the well-studied majority and element distinctness problems. Additionally, we prove a tight Θ̃(N1/3) bound on search. Furthermore, we use the lower-bound to explore PDQP under query restrictions, finding that when combined with non-adaptive queries, we limit the speed-up in several cases.
AB - Aaronson, Bouland, Fitzsimons and Lee [5] introduced the complexity class PDQP (which was original labeled naCQP), an alteration of BQP enhanced with the ability to obtain non-collapsing measurements, samples of quantum states without collapsing them. Although SZK ⊆ PDQP, it still requires Ω(N1/4) queries to solve unstructured search. We formulate an alternative equivalent definition of PDQP, which we use to prove the positive weighted adversary lower-bounding method, establishing multiple tighter bounds and a trade-off between queries and non-collapsing measurements. We utilize the technique in order to analyze the query complexity of the well-studied majority and element distinctness problems. Additionally, we prove a tight Θ̃(N1/3) bound on search. Furthermore, we use the lower-bound to explore PDQP under query restrictions, finding that when combined with non-adaptive queries, we limit the speed-up in several cases.
KW - Non-collapsing measurements
KW - Quantum adversary method
KW - Quantum lower-bounds
UR - https://www.scopus.com/pages/publications/105012189172
U2 - 10.4230/LIPIcs.CCC.2025.12
DO - 10.4230/LIPIcs.CCC.2025.12
M3 - Conference contribution
AN - SCOPUS:105012189172
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 40th Computational Complexity Conference, CCC 2025
A2 - Srinivasan, Srikanth
A2 - Srinivasan, Srikanth
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 40th Computational Complexity Conference, CCC 2025
Y2 - 5 August 2025 through 8 August 2025
ER -