A central problem in quantum computing is to identify computational tasks which can be solved substantially faster on a quantum computer than on any classical computer. By studying the hardest such tasks, known as BQP-complete problems, we deepen our understanding of the power and limitations of quantum computers. We present several BQP-complete problems, including Local Hamiltonian Eigenvalue Sampling and Phase Estimation Sampling. Different than the previous known BQP-complete problems (the Quadratically Signed Weight Enumerator problem [KL01] and the Approximation of Jones Polynomials [FKW02, FLW02, AJL06]), our problems are of a basic linear algebra nature and are closely related to the well-known quantum algorithm and quantum complexity theories.
A central problem in quantum computing is to identify computational tasks which can be solved substantially faster on a quantum computer than on any classical computer. By studying the hardest such tasks, known as BQP-complete problems, we deepen our understanding of the power and limitations of quantum computers. We present several BQP-complete problems, including Local Hamiltonian Eigenvalue Sampling and Phase Estimation Sampling. Different than the previous known BQP-complete problems (the Quadratically Signed Weight Enumerator problem [KL01] and the Approximation of Jones Polynomials [FKW02, FLW02, AJL06]), our problems are of a basic linear algebra nature and are closely related to the well-known quantum algorithm and quantum complexity theories.
The computational complexity of simulating the dynamics of physical quantum systems is a central question at the interface of quantum physics and computer science. In this work, we address this question for the simulation of exponentially large bosonic Hamiltonians with quadratic interactions. We present two results: First, we introduce a broad class of quadratic bosonic problems for which we prove that they are BQP-complete. Importantly, this class includes two known BQP-complete problems as special cases: Classical oscillator networks and continuous-time quantum walks. Second, we show that extending the aforementioned class to even more general quadratic Hamiltonians results in a PostBQP-complete problem, which constitutes a jump in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers.
The quantum algorithm of AJL [3] (following the work of Freedman et al. [10]) to approximate the Jones polynomial, is of a new type: rather than using the quantum Fourier transform, it encodes the local combinatorial structure of the problem by the relations of an algebra, called the Temperley-Lieb algebra, whose matrix representation is then applied, using a quantum computer. By the results of [11], the problems this algorithm solves are the first non trivial BQP-complete problems. A natural question is whether it is possible to generalize this algorithm to other points of the famous Tutte polynomial, of which the Jones polynomial is a special case. However, the only points for which
In this dissertation, we investigate three different problems in the field of Quantum computation. First, we discuss the quantum complexity of evaluating the Tutte polynomial of a planar graph. Furthermore, we devise a new quantum algorithm for approximating the phase of a unitary matrix. Finally, we provide quantum tools that can be utilized to extract the structure of black-box modules and algebras. While quantum phase estimation (QPE) is at the core of many quantum algorithms known to date, its physical implementation (algorithms based on quantum Fourier transform (QFT) ) is highly constrained by the requirement of high-precision controlled phase shift operators, which remain difficult to realize. In the second part of this dissertation, we introduce an alternative approach to approximately implement QPE with arbitrary constantprecision controlled phase shift operators. The new quantum algorithm bridges the gap between QPE algorithms based on QFT and Kitaev’s original approach. For approximating the eigenphase precise to the nth bit, Kitaev’s original approach does not require any controlled phase shift operator. In contrast, QPE algorithms based on QFT or approximate QFT require controlled phase shift operators with precision of at least Pi/2n. The new approach fills the gap and requires only arbitrary constant-precision controlled phase shift operators. From a physical implementation viewpoint, the new algorithm outperforms Kitaev’s approach. iii The other problem we investigate relates to approximating the Tutte polynomial. We show that the problem of approximately evaluating the Tutte polynomial of triangular graphs at the points (q, 1/q) of the Tutte plane is BQP-complete for (most) roots of unity q. We also consider circular graphs and show that the problem of approximately evaluating the Tutte polynomial of these graphs at the point (e 2πi/5 ,e−2πi/5 ) is DQC1-complete and at points (q k , 1 + 1−q−k (q 1/2−q−1/2) 2 ) for some integer k is in BQP. To show that these problems can be solved by a quantum computer, we rely on the relation of the Tutte polynomial of a planar G graph with the Jones and HOMFLY polynomial of the alternating link D(G) given by the medial graph of G. In the case of our graphs the corresponding links are equal to the plat and trace closures of braids. It is known how to evaluate the Jones and HOMFLY polynomial for closures of braids. To establish the hardness results, we use the property that the images of the generators of the braid group under the irreducible Jones-Wenzl representations of the Hecke algebra have finite order. We show that for each braid b we can efficiently construct a braid ˜b such that the evaluation of the Jones and HOMFLY polynomials of their closures at a fixed root of unity leads to the same value and that the closures of ˜b are alternating links. The final part of the dissertation focuses on finding the structure of a black-box module or algebra. Suppose we are given black-box access to a finite module M or algebra over a finite ring R, and a list of generators for M and R. We show how to find a linear basis and structure constants for M in quantum poly(log |M|) time. This generalizes a recent quantum algorithm of Arvind et al. which finds a basis representation for rings. We then show that iv our algorithm is a useful primitive allowing quantum computers to determine the structure of a finite associative algebra as a direct sum of simple algebras. Moreover, it solves a wide variety of problems regarding finite modules and rings. Although our quantum algorithm is based on Abelian Fourier transforms, it solves problems regarding the multiplicative structure of modules and algebras, which need not be commutative. Examples include finding the intersection and quotient of two modules, finding the additive and multiplicative identities in a module, computing the order of an module, solving linear equations over modules, deciding whether an ideal is maximal, finding annihilators, and testing the injectivity and surjectivity of ring homomorphisms. These problems appear to be exponentially hard classically.
Quantum computing has attracted a lot of attention in different research fields, such as mathematics, physics and computer science. Quantum algorithms can solve certain problems significantly faster than classical algorithms. There are many numerical problems, especially those arising from quantum systems, which are notoriously difficult to solve using classical computers, since the computational time required often scales exponentially with the size of the problem. However, quantum computers have the potential to solve these problems efficiently, which is also one of the founding ideas of the field of quantum computing. In this thesis, we explore five computational problems, designing innovative quantum algorithms and studying their computational complexity. First, we design an adiabatic quantum algorithm based on the Berry phases for the counting problem. For the running time, it is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result should be robust to decoherence and resilient to certain kinds of noise. Since the counting problem is the foundation of many other numerical problems, such as high-dimensional integration and path integration, our adiabatic algorithms can be directly generalized to these kinds of problems. In addition, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. The lower bound is very close to the best lower bound on query complexity known for the classical PAC learning model. We also study the algorithms and the cost of simulating a system evolving under a given Hamiltonian. We consider high order splitting methods that are particularly applicable in quantum simulation and obtain bounds on the number of exponentials required. Moreover, we derive the optimal order of convergence given the required error bound. We compare our complexity estimates to previously known ones and show the resulting speedup. Furthermore, we consider randomized algorithms for Hamiltonian simulation. The evolution is simulated by a product of exponentials in a random sequence and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. We provide a scheme to bound the error of the final quantum state in a randomized algorithm, and obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement. We also apply Hamiltonian simulation in estimating the ground state energy of a multiparticle system, which is also known as the multivariate Sturm-Liouville eigenvalue problem. Since the cost of this problem grows exponentially with the number of particles using deterministic classical algorithms, it suffers from the curse of dimensionality. Quantum computers can vanquish the curse, and we exhibit a quantum algorithm whose total cost are linear in the number of particles.
In this chapter we examine one of two main classes of algorithms: quantum algorithms that solve problems with a complexity that is superpolynomially less than the complexity of the best-known classical algorithm for the same problem. That is, the complexity of the best-known classical algorithm cannot be bounded above by any polynomial in the complexity of the quantum algorithm. The algorithms we will detail all make use of the quantum Fourier transform (QFT). We start off the chapter by studying the problem of quantum phase estimation, which leads us naturally to the QFT. Section 7.1 also looks at using the QFT to find the period of periodic states, and introduces some elementary number theory that is needed in order to post-process the quantum algorithm. In Section 7.2, we apply phase estimation in order to estimate eigenvalues of unitary operators. Then in Section 7.3, we apply the eigenvalue estimation algorithm in order to derive the quantum factoring algorithm, and in Section 7.4 to solve the discrete logarithm problem. In Section 7.5, we introduce the hidden subgroup problem which encompasses both the order finding and discrete logarithm problem as well as many others. This chapter by no means exhaustively covers the quantum algorithms that are superpolynomially faster than any known classical algorithm, but it does cover the most well-known such algorithms. In Section 7.6, we briefly discuss other quantum algorithms that appear to provide a superpolynomial advantage. To introduce the idea of phase estimation, we begin by noting that the final Hadamard gate in the Deutsch algorithm, and the Deutsch–Jozsa algorithm, was used to get at information encoded in the relative phases of a state. The Hadamard gate is self-inverse and thus does the opposite as well, namely it can be used to encode information into the phases. To make this concrete, first consider H acting on the basis state |x⟩ (where x ∊ {0, 1}). It is easy to see that You can think about the Hadamard gate as having encoded information about the value of x into the relative phases between the basis states |0⟩ and |1⟩.