Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient optimization of perturbative gadgets
59
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Perturbative gadgets are general techniques for reducing many-body spin interactions to two-body ones using perturbation theory. This allows for potential realization of effective many-body interactions using more physically viable two-body ones. In parallel with prior work (arXiv:1311.2555 [quant-ph]), here we consider minimizing the physical resource required for implementing the gadgets initially proposed by Kempe, Kitaev and Regev (arXiv:quant-ph/0406180) and later generalized by Jordan and Farhi (arXiv:0802.1874v4). The main innovation of our result is a set of methods that efficiently compute tight upper bounds to errors in the perturbation theory. We show that in cases where the terms in the target Hamiltonian commute, the bounds produced by our algorithm are sharp for arbitrary order perturbation theory. We provide numerics which show orders of magnitudes improvement over gadget constructions based on trivial upper bounds for the error term in the perturbation series. We also discuss further improvement of our result by adopting the Schrieffer-Wolff formalism of perturbation theory and supplement our observation with numerical results.
rate research
Read More
Perturbative gadgets are used to construct a quantum Hamiltonian whose low-energy subspace approximates a given quantum $k$-body Hamiltonian up to an absolute error $epsilon$. Typically, gadget constructions involve terms with large interaction strengths of order $text{poly}(epsilon^{-1})$. Here we present a 2-body gadget construction and prove that it approximates a target many-body Hamiltonian of interaction strength $gamma = O(1)$ up to absolute error $epsilonllgamma$ using interactions of strength $O(epsilon)$ instead of the usual inverse polynomial in $epsilon$. A key component in our proof is a new condition for the convergence of the perturbation series, allowing our gadget construction to be applied in parallel on multiple many-body terms. We also show how to apply this gadget construction for approximating 3- and $k$-body Hamiltonians. The price we pay for using much weaker interactions is a large overhead in the number of ancillary qubits, and the number of interaction terms per particle, both of which scale as $O(text{poly}(epsilon^{-1}))$. Our strong-from-weak gadgets have their primary application in complexity theory (QMA hardness of restricted Hamiltonians, a generalized area law counterexample, gap amplification), but could also motivate practical implementations with many weak interactions simulating a much stronger quantum many-body interaction.
It was recently shown that, for solving NP-complete problems, adiabatic paths always exist without finite-order perturbative crossings between local and global minima, which could lead to anticrossings with exponentially small energy gaps if present. However, it was not shown whether such a path could be found easily. Here, we give a simple construction that deterministically eliminates all such anticrossings in polynomial time, space, and energy, for any Ising models with polynomial final gap. Thus, in order for adiabatic quantum optimization to require exponential time to solve any NP-complete problem, some quality other than this type of anticrossing must be unavoidable and necessitate exponentially long runtimes.
From celestial mechanics to quantum theory of atoms and molecules, perturbation theory has played a central role in natural sciences. Particularly in quantum mechanics, the amount of information needed for specifying the state of a many-body system commonly scales exponentially as the system size. This poses a fundamental difficulty in using perturbation theory at arbitrary order. As one computes the terms in the perturbation series at increasingly higher orders, it is often important to determine whether the series converges and if so, what is an accurate estimation of the total error that comes from the next order of perturbation up to infinity. Here we present a set of efficient algorithms that compute tight upper bounds to perturbation terms at arbitrary order. We argue that these tight bounds often take the form of symmetric polynomials on the parameter of the quantum system. We then use cellular automata as our basic model of computation to compute the symmetric polynomials that account for all of the virtual transitions at any given order. At any fixed order, the computational cost of our algorithm scales polynomially as a function of the system size. We present a non-trivial example which shows that our error estimation is nearly tight with respect to exact calculation.
Application of the adiabatic model of quantum computation requires efficient encoding of the solution to computational problems into the lowest eigenstate of a Hamiltonian that supports universal adiabatic quantum computation. Experimental systems are typically limited to restricted forms of 2-body interactions. Therefore, universal adiabatic quantum computation requires a method for approximating quantum many-body Hamiltonians up to arbitrary spectral error using at most 2-body interactions. Hamiltonian gadgets, introduced around a decade ago, offer the only current means to address this requirement. Although the applications of Hamiltonian gadgets have steadily grown since their introduction, little progress has been made in overcoming the limitations of the gadgets themselves. In this experimentally motivated theoretical study, we introduce several gadgets which require significantly more realistic control parameters than similar gadgets in the literature. We employ analytical techniques which result in a reduction of the resource scaling as a function of spectral error for the commonly used subdivision, 3- to 2-body and $k$-body gadgets. Accordingly, our improvements reduce the resource requirements of all proofs and experimental proposals making use of these common gadgets. Next, we numerically optimize these new gadgets to illustrate the tightness of our analytical bounds. Finally, we introduce a new gadget that simulates a $YY$ interaction term using Hamiltonians containing only ${X,Z,XX,ZZ}$ terms. Apart from possible implications in a theoretical context, this work could also be useful for a first experimental implementation of these key building blocks by requiring less control precision without introducing extra ancillary qubits.
An origami extrusion is a folding of a 3D object in the middle of a flat piece of paper, using 3D gadgets which create faces with solid angles. Our main concern is to make origami extrusions of polyhedrons using 3D gadgets with simple outgoing pleats, where a simple pleat is a pair of a mountain fold and a valley fold which are parallel to each other. In this paper we present a new type of 3D gadgets with simple outgoing pleats in origami extrusions and their construction. Our 3D gadgets are downward compatible with the conventional pyramid-supported gadgets developed by Calros Natan as a generalization of the cube gadget, in the sense that in many cases we can replace the conventional gadgets with the new ones with the same outgoing pleats while the converse is not always possible. We can also change angles of the outgoing pleats under certain conditions. Unlike the conventional pyramid-supported 3D gadgets, the new ones have flat back sides above the ambient paper, and thus we can make flat-foldable origami extrusions. Furthermore, since our new 3D gadgets are less interfering with adjacent gadgets than the conventional ones, we can use wider pleats at one time to make the extrusion higher. For example, we prove that the maximal height of the prism of any convex polygon (resp. any triangle) that can be extruded with our new gadgets is more than 4/3 times (resp. $sqrt{2}$ times) of that with the conventional ones. We also present explicit constructions of division/repetition and negati
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
