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

Lecture notes in computer science

The Quantum Query Complexity of Algebraic Properties

Sebastian Dörn, Thomas Thierauf

Published Aug 27, 2007• 20 citations
Publisher
DOI
10.1007/978-3-540-74240-1_22

Related papers

Parameterized query complexity in quantum computation

Parijat Prashun Purohit

•Jan 1, 2017•0 citations

The Quantum Query Complexity of Algebraic Properties

Sebastian Doern, Thomas Thierauf

We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation on S, we consider the decision problem whether $S$ is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.

arXiv:0705.1446•May 10, 2007•15 citations

Quantum Query Complexity in Computational Geometry

Abhinav Bahadur, Christoph Dürr, Raghav Kulkarni +1 more

•Jan 1, 2006•1 citation

Algebraic Methods in Query and Proof Complexity

Adrian She

Algebraic methods have become a powerful tool for analyzing the complexity of various computational models, including low-depth circuits, algebraic proofs, and quantum query algorithms. In particular, the complexity of computing a function in these models is related to whether or not the function admits a low-degree polynomial approximation. In this thesis, we present two novel applications of algebraic methods in computational complexity theory. In the first part of the thesis, we study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether or not it satisfies some property. In addition to containing the classical query complexity model as a special case, this model also contains "inherently quantum" problems that have no classical analogue. Our main contribution is a generalized polynomial method for analyzing the complexity of unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a subspace, and approximating the entanglement entropy of a state. We also present a candidate problem towards an oracle separation of QMA and QMA(2), a long standing open question in quantum complexity theory. In the second part of the thesis, we study the tensor isomorphism problem (TI), which has recently emerged as having connections to multiple areas of research, including quantum information theory, post-quantum cryptography, and computational algebra. However, the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, the study of tensor isomorphism naturally lends itself to algebraic and semi-algebraic proof systems such as the polynomial calculus (PC) and sum-of-squares (SoS). We show a linear degree lower bound on PC degree or SoS degree for tensor isomorphism and a non-trivial upper bound for testing isomorphism of tensors of bounded rank. Along the way, we also show that PC cannot perform basic linear algebra in sublinear degree, such as comparing the rank of two matrices. We introduce a strictly stronger proof system, called PC + Inv, which enables linear algebra to be done in low degree. We conjecture that even PC + Inv cannot solve TI in polynomial time either, and highlight many other open questions about proof complexity approaches to TI.

•Nov 1, 2024•0 citations

Quantum Testers for Hidden Group Properties

Katalin Friedl, Miklós Sántha, Frédéric Magniez +1 more

We construct efficient or query efficient quantum property testers for two existential group properties which have exponential query complexity both for their decision problem in the quantum and for their testing problem in the classical model of computing. These are periodicity in groups and the common coset range property of two functions having identical ranges within each coset of some normal subgroup. Our periodicity tester is efficient in Abelian groups and generalizes, in several aspects, previous periodicity testers. This is achieved by introducing a technique refining the majority correction process widely used for proving robustness of algebraic properties. The periodicity tester in non-Abelian groups and the common coset range tester are query efficient.

arXiv:quant-ph/0208184•Fundamenta Informaticae•Jan 1, 2009•16 citations

On Exact Quantum Query Complexity

Ashley Montanaro, Richard Jozsa, Graeme Mitchison

arXiv:1111.0475•Algorithmica•Aug 29, 2013•48 citations
We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation on S, we consider the decision problem whether SSS is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.
Algebraic methods have become a powerful tool for analyzing the complexity of various computational models, including low-depth circuits, algebraic proofs, and quantum query algorithms. In particular, the complexity of computing a function in these models is related to whether or not the function admits a low-degree polynomial approximation. In this thesis, we present two novel applications of algebraic methods in computational complexity theory. In the first part of the thesis, we study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether or not it satisfies some property. In addition to containing the classical query complexity model as a special case, this model also contains "inherently quantum" problems that have no classical analogue. Our main contribution is a generalized polynomial method for analyzing the complexity of unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a subspace, and approximating the entanglement entropy of a state. We also present a candidate problem towards an oracle separation of QMA and QMA(2), a long standing open question in quantum complexity theory. In the second part of the thesis, we study the tensor isomorphism problem (TI), which has recently emerged as having connections to multiple areas of research, including quantum information theory, post-quantum cryptography, and computational algebra. However, the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, the study of tensor isomorphism naturally lends itself to algebraic and semi-algebraic proof systems such as the polynomial calculus (PC) and sum-of-squares (SoS). We show a linear degree lower bound on PC degree or SoS degree for tensor isomorphism and a non-trivial upper bound for testing isomorphism of tensors of bounded rank. Along the way, we also show that PC cannot perform basic linear algebra in sublinear degree, such as comparing the rank of two matrices. We introduce a strictly stronger proof system, called PC + Inv, which enables linear algebra to be done in low degree. We conjecture that even PC + Inv cannot solve TI in polynomial time either, and highlight many other open questions about proof complexity approaches to TI.
We construct efficient or query efficient quantum property testers for two existential group properties which have exponential query complexity both for their decision problem in the quantum and for their testing problem in the classical model of computing. These are periodicity in groups and the common coset range property of two functions having identical ranges within each coset of some normal subgroup. Our periodicity tester is efficient in Abelian groups and generalizes, in several aspects, previous periodicity testers. This is achieved by introducing a technique refining the majority correction process widely used for proving robustness of algebraic properties. The periodicity tester in non-Abelian groups and the common coset range tester are query efficient.