A central result in the study of quantum Hamiltonian complexity is that the $k$-local Hamiltonian problem is quantum-Merlin-Arthur--complete. In that problem, we must decide if the lowest eigenvalue of a Hamiltonian is bounded below some value, or above another, promised one of these is true. Given the ground state of the Hamiltonian, a quantum computer can determine this question, even if the ground state itself may not be efficiently quantum preparable. Kitaev's proof of QMA-completeness encodes a unitary quantum circuit in QMA into the ground space of a Hamiltonian. However, we now have quantum computing models based on measurement instead of unitary evolution; furthermore, we can use postselected measurement as an additional computational tool. In this work, we generalize Kitaev's construction to allow for nonunitary evolution including postselection. Furthermore, we consider a type of postselection under which the construction is consistent, which we call tame postselection. We consider the computational complexity consequences of this construction and then consider how the probability of an event upon which we are postselecting affects the gap between the ground-state energy and the energy of the first excited state of its corresponding Hamiltonian. We provide numerical evidence that the two are not immediately related by giving a family of circuits where the probability of an event upon which we postselect is exponentially small, but the gap in the energy levels of the Hamiltonian decreases as a polynomial.
A central result in the study of quantum Hamiltonian complexity is that the k-local Hamiltonian problem is quantum-Merlin-Arthur--complete. In that problem, we must decide if the lowest eigenvalue of a Hamiltonian is bounded below some value, or above another, promised one of these is true. Given the ground state of the Hamiltonian, a quantum computer can determine this question, even if the ground state itself may not be efficiently quantum preparable. Kitaev's proof of QMA-completeness encodes a unitary quantum circuit in QMA into the ground space of a Hamiltonian. However, we now have quantum computing models based on measurement instead of unitary evolution; furthermore, we can use postselected measurement as an additional computational tool. In this work, we generalize Kitaev's construction to allow for nonunitary evolution including postselection. Furthermore, we consider a type of postselection under which the construction is consistent, which we call tame postselection. We consider the computational complexity consequences of this construction and then consider how the probability of an event upon which we are postselecting affects the gap between the ground-state energy and the energy of the first excited state of its corresponding Hamiltonian. We provide numerical evidence that the two are not immediately related by giving a family of circuits where the probability of an event upon which we postselect is exponentially small, but the gap in the energy levels of the Hamiltonian decreases as a polynomial.
The quantum adiabatic theorem ensures that a slowly changing system, initially prepared in its ground state, will evolve to its final ground state with arbitrary precision. As a first result this thesis extends the original theorem to projection operators keeping the statement valid for Hamiltonians with degenerate ground spaces. Yet the main focus of this work lies in studying the efficiency of quantum circuit simulations by adabatic quantum computation. The standard Hamiltonian construction by Kitaev is based on a path graph reflecting the L computation steps and influencing the scaling of the necessary evolution time by its spectral gap of O(L21). Aspiring to an improved running time we generalize Kitaev's Hamiltonian to so-called standard graph Hamiltonians based on graph families with a different spectral gap. In this generalized construction the first two time derivatives of the Hamiltonian and the fraction of initial vertices appear as additional parameters of running time. In a first step the time derivatives can be proven to be constant. Expansion results from spectral graph theory however impose a trade-off between the spectral gap and the fraction of initial vertices as well as the fraction of final vertices which corresponds to the probability for obtaining the correct computational output. Graphs with spectral gap O(Lk1), k<2, turn out to contradict very likely, graphs with k<1 even for sure at least one of the efficiency criterias for running time, output probability or Hamiltonian implementation. The above results may also be obstacles for a possible quantum PCP-theorem in complexity theory claiming the local Hamiltonian problem with constant gap to be QMA-complete since the very same Kitaev Hamiltonian is constructed in the QMA-hardness proof for the Local Hamiltonian problem.
Non-Hermitian (NH) quantum systems demonstrate striking differences from their Hermitian counterparts, leading to claims of NH advantage in areas ranging from metrology to entanglement generation. We show that in the context of quantum computation, any such NH advantage is unlikely to be scalable as an efficient computational resource: If coherent nonunitary evolution with renormalization could be realized with only polynomial overhead, then the resulting model could implement postselection, implying implausibly strong complexity-theoretic power under standard assumptions. We define NHBQP ( U ) as the computational power of polynomial-size quantum circuits that, in addition to a standard universal unitary gate set, may apply a fixed gate U on O ( 1 ) qubits that is not proportional to a unitary, with the state renormalized after each use of U . We prove that this model is powerful enough to decide every language in PostBQP (equivalently PP ). Moreover, in the standard uniform circuit-family model, this characterization is tight: For any fixed such nonunitary gate U , NHBQP ( U ) = PostBQP = PP . PostBQP is believed intractable, so this suggests that any scalable NH computational advantage must come with a compensating cost limiting its efficiency. Additionally, we study simulation complexity of restricted classes of nonunitary systems by purifying them to postselected unitary evolution in a form preserving system locality. Using this framework, we show that unitary gates with postselection can simulate not only evolution under NH Hamiltonians but arbitrary quantum trajectories. Any NH model whose purification lies in a strongly simulable unitary family (e.g., Clifford, matchgate, or low-bond-dimension tensor-network circuits) remains efficiently classically simulable, provided the relevant postselected events occur with probability Ω ( 2 − poly ( n ) ) . Thus, adding non-Hermiticity to a universal unitary system makes it infeasibly computationally powerful, while adding it to a strongly simulable system adds no computational power in this setting.
We present a collection of results about the clock in Feynman's computer construction and Kitaev's local Hamiltonian problem. First, by analyzing the spectra of quantum walks on a line with varying end-point terms, we find a better lower bound on the gap of the Feynman Hamiltonian, which translates into a less strict promise gap requirement for the quantum-Merlin-Arthur--complete local Hamiltonian problem. We also translate this result into the language of adiabatic quantum computation. Second, introducing an idling clock construction with a large state space but fast Cesaro mixing, we provide a way for achieving an arbitrarily high success probability of computation with Feynman's computer with only a logarithmic increase in the number of clock qubits. Finally, we tune and thus improve the costs (locality and gap scaling) of implementing a (pulse) clock with a single excitation.
Feynman's circuit-to-Hamiltonian construction connects quantum computation and ground states of many-body quantum systems. Kitaev applied this construction to demonstrate QMA-completeness of the local Hamiltonian problem, and Aharanov et al. used it to show the equivalence of adiabatic computation and the quantum circuit model. In this work, we analyze the low energy properties of a class of modified circuit Hamiltonians, which include features like complex weights and branching transitions. For history states with linear clocks and complex weights, we develop a method for modifying the circuit propagation Hamiltonian to implement any desired distribution over the time steps of the circuit in a frustration-free ground state, and show that this can be used to obtain a constant output probability for universal adiabatic computation while retaining the Ω(T−2) scaling of the spectral gap, and without any additional overhead in terms of numbers of qubits.Furthermore, we establish limits on the increase in the ground energy due to input and output penalty terms for modified tridiagonal clocks with non-uniform distributions on the time steps by proving a tight O(T−2) upper bound on the product of the spectral gap and ground state overlap with the endpoints of the computation. Using variational techniques which go beyond the Ω(T−3) scaling that follows from the usual geometrical lemma, we prove that the standard Feynman-Kitaev Hamiltonian already saturates this bound. We review the formalism of unitary labeled graphs which replace the usual linear clock by graphs that allow branching and loops, and we extend the O(T−2) bound from linear clocks to this more general setting. In order to achieve this, we apply Chebyshev polynomials to generalize an upper bound on the spectral gap in terms of the graph diameter to the context of arbitrary Hermitian matrices.
Feynman's circuit-to-Hamiltonian construction connects quantum computation and ground states of many-body quantum systems. Kitaev applied this construction to demonstrate QMA-completeness of the local Hamiltonian problem, and Aharanov et al. used it to show the equivalence of adiabatic computation and the quantum circuit model. In this work, we analyze the low energy properties of a class of modified circuit Hamiltonians, which include features like complex weights and branching transitions. For history states with linear clocks and complex weights, we develop a method for modifying the circuit propagation Hamiltonian to implement any desired distribution over the time steps of the circuit in a frustration-free ground state, and show that this can be used to obtain a constant output probability for universal adiabatic computation while retaining the Ω ( T − 2 ) scaling of the spectral gap, and without any additional overhead in terms of numbers of qubits.Furthermore, we establish limits on the increase in the ground energy due to input and output penalty terms for modified tridiagonal clocks with non-uniform distributions on the time steps by proving a tight O ( T − 2 ) upper bound on the product of the spectral gap and ground state overlap with the endpoints of the computation. Using variational techniques which go beyond the Ω ( T − 3 ) scaling that follows from the usual geometrical lemma, we prove that the standard Feynman-Kitaev Hamiltonian already saturates this bound. We review the formalism of unitary labeled graphs which replace the usual linear clock by graphs that allow branching and loops, and we extend the O ( T − 2 ) bound from linear clocks to this more general setting. In order to achieve this, we apply Chebyshev polynomials to generalize an upper bound on the spectral gap in terms of the graph diameter to the context of arbitrary Hermitian matrices.
Motivated by understanding the power of quantum computation with restricted number of qubits, we give two complete characterizations of unitary quantum space bounded computation. First we show that approximating an element of the inverse of a well-conditioned efficiently encoded 2k(n)×2k(n) matrix is complete for the class of problems solvable by quantum circuits acting on O(k(n)) qubits with all measurements at the end of the computation. Similarly, estimating the minimum eigenvalue of an efficiently encoded Hermitian 2k(n)×2k(n) matrix is also complete for this class. In the logspace case, our results improve on previous results of Ta-Shma [STOC '13] by giving new space-efficient quantum algorithms that avoid intermediate measurements, as well as showing matching hardness results. Additionally, as a consequence we show that PreciseQMA, the version of QMA with exponentially small completeness-soundess gap, is equal to PSPACE. Thus, the problem of estimating the minimum eigenvalue of a local Hamiltonian to inverse exponential precision is PSPACE-complete, which we show holds even in the frustration-free case. Finally, we can use this characterization to give a provable setting in which the ability to prepare the ground state of a local Hamiltonian is more powerful than the ability to prepare PEPS states. Interestingly, by suitably changing the parameterization of either of these problems we can completely characterize the power of quantum computation with simultaneously bounded time and space.