Quantum Property Testing

We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex. In the classical unidirectional model, the problem of testing $k$ -star-freeness, and more generally $k$ -source-subgraph-freeness, is almost maximally hard for large $k$ . We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we show that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the $k$ -collision problem that was not studied before. To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of $3$ -colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex. In the classical unidirectional model, the problem of testing $k$-star-freeness, and more generally $k$-source-subgraph-freeness, is almost maximally hard for large $k$. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we show that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the $k$-collision problem that was not studied before. To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of $3$-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.

arXiv:2410.05001Leibniz international proceedings in informaticsOct 7, 20240 citations

Quantum Property Testing for Solvable Groups

Yoshifumi Inui

Property testing has been extensively studied and its target is to determine whether a given object satisfies a certain property or it is far from the property. In this paper, we construct an efficient quantum algorithm which tests if a given quantum oracle performs the group multiplication of a solvable group. Our work is strongly based on the efficient classical testing algorithm for Abelian groups proposed by Friedl, Ivanyos and Santha. Since every Abelian group is a solvable group, our result is in a sense a generalization of their result.Property testing has been extensively studied and its target is to determine whether a given object satisfies a certain property or it is far from the property. In this paper, we construct an efficient quantum algorithm which tests if a given quantum oracle performs the group multiplication of a solvable group. Our work is strongly based on the efficient classical testing algorithm for Abelian groups proposed by Friedl, Ivanyos and Santha. Since every Abelian group is a solvable group, our result is in a sense a generalization of their result.

arXiv:quant-ph/0610013Oct 3, 20060 citations

k

-star-freeness, and more generally

k

-source-subgraph-freeness, is almost maximally hard for large

k

. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we show that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the

k

-collision problem that was not studied before. To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of

3

-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.