The problem of discriminating between many quantum channels with certainty is analyzed under the assumption of prior knowledge of algebraic relations among possible channels. It is shown, by explicit construction of a novel family of quantum algorithms, that when the set of possible channels faithfully represents a finite subgroup of SU(2) (e.g., ${C}_{n}, {D}_{2n}, {A}_{4}, {S}_{4}, {A}_{5}$) the recently developed techniques of quantum signal processing can be modified to constitute subroutines for quantum hypothesis testing. These algorithms, for group quantum hypothesis testing, intuitively encode discrete properties of the channel set in SU(2) and improve query complexity at least quadratically in $n$, the size of the channel set and group, compared to na\"{\i}ve repetition of binary hypothesis testing. Intriguingly, performance is completely defined by explicit group homomorphisms; these in turn inform simple constraints on polynomials embedded in unitary matrices. These constructions demonstrate a flexible technique for mapping questions in quantum inference to the well-understood subfields of functional approximation and discrete algebra. Extensions to larger groups and noisy settings are discussed, as well as paths by which improved protocols for quantum hypothesis testing against structured channel sets have application in the transmission of reference frames, proofs of security in quantum cryptography, and algorithms for property testing.
The problem of discriminating between many quantum channels with certainty is analyzed under the assumption of prior knowledge of algebraic relations among possible channels. It is shown, by explicit construction of a novel family of quantum algorithms, that when the set of possible channels faithfully represents a finite subgroup of SU(2) (e.g., Cn,D2n,A4,S4,A5) the recently developed techniques of quantum signal processing can be modified to constitute subroutines for quantum hypothesis testing. These algorithms, for group quantum hypothesis testing, intuitively encode discrete properties of the channel set in SU(2) and improve query complexity at least quadratically in n, the size of the channel set and group, compared to na"{\i}ve repetition of binary hypothesis testing. Intriguingly, performance is completely defined by explicit group homomorphisms; these in turn inform simple constraints on polynomials embedded in unitary matrices. These constructions demonstrate a flexible technique for mapping questions in quantum inference to the well-understood subfields of functional approximation and discrete algebra. Extensions to larger groups and noisy settings are discussed, as well as paths by which improved protocols for quantum hypothesis testing against structured channel sets have application in the transmission of reference frames, proofs of security in quantum cryptography, and algorithms for property testing.
Quantum hypothesis testing is a central task in the entire field of quantum information theory. Understanding its ultimate limits will give insight into a wide range of quantum protocols and applications, from sensing to communication. Although the limits of hypothesis testing between quantum states have been completely clarified by the pioneering works of Helstrom in the 1970s, the more difficult problem of hypothesis testing with quantum channels, i.e., channel discrimination, is less understood. This is mainly due to the complications coming from the use of input entanglement and the possibility of employing adaptive strategies. In this Letter, we establish a lower limit for the ultimate error probability affecting the discrimination of an arbitrary number of quantum channels. We also show that this lower bound is achievable when the channels have certain symmetries. As an example, we apply our results to the problem of channel position finding, where the goal is to identify the location of a target channel among multiple background channels. In this general setting, we find that the use of entanglement offers a great advantage over strategies without entanglement, with nontrivial implications for data readout, target detection, and quantum spectroscopy.
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.
In this paper, we systematically study property testing of unitary operators. We first introduce a distance measure that reflects the average difference between unitary operators. Then we show that, with respect to this distance measure, the orthogonal group, quantum juntas (i.e., unitary operators that only nontrivially act on a few qubits of the system), and the Clifford group can be all efficiently tested. In fact, their testing algorithms have query complexities independent of the system's size and have only one-sided error. Then we give an algorithm that tests any finite subset of the unitary group, and demonstrate an application of this algorithm to the permutation group. This algorithm also has one-sided error and polynomial query complexity, but it is unknown whether it can be efficiently implemented in general.
In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.
When classifying a collection of finite algebras (for instance, in the computational classification of finite semifields), an important task is the determination of substructures such as the right, middle, and left nuclei, the nucleus, and the center. Finding these structures may become computationally expensive when there is no additional information about the algebra properties. In this paper, we introduce quantum algorithms than solve this task efficiently, by formulating it as an instance of the Hidden Subgroup Problem (HSP) {over Abelian groups}. We give detailed constructions of the quantum circuits involved in the process and prove that the overall (quantum) complexity of our algorithm is polynomial in the dimension of the algebra, while a similar approach with classical computers would require an exponential number of queries to the HSP function
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.