This note provides a detailed description and derivation of the domain decomposition algorithm that appears in previous works by the author. Given a large re-estimation problem, domain decomposition provides an iterative method for assembling Boltzmann distributions associated to small subproblems into an approximation of the Bayesian posterior of the whole problem. The algorithm is amenable to using Boltzmann sampling to approximate these Boltzmann distributions. In previous work, we have shown the capability of heuristic versions of this algorithm to solve LDPC decoding and circuit fault diagnosis problems too large to fit on quantum annealing hardware used for sampling. Here, we rigorously prove soundness of the method.

}, url = {https://arxiv.org/abs/1810.10005}, author = {Brad Lackey} } @article {2330, title = {Mathematical methods for resource-based type theories}, year = {2018}, abstract = {With the wide range of quantum programming languages on offer now, efficient program verification and type checking for these languages presents a challenge -- especially when classical debugging techniques may affect the states in a quantum program. In this work, we make progress towards a program verification approach using the formalism of operational quantum mechanics and resource theories. We present a logical framework that captures two mathematical approaches to resource theory based on monoids (algebraic) and monoidal categories (categorical). We develop the syntax of this framework as an intuitionistic sequent calculus, and prove soundness and completeness of an algebraic and categorical semantics that recover these approaches. We also provide a cut-elimination theorem, normal form, and analogue of Lambek\&$\#$39;s lifting theorem for polynomial systems over the logics. Using these approaches along with the Curry-Howard-Lambek correspondence for programs, proofs and categories, this work lays the mathematical groundwork for a type checker for some resource theory based frameworks, with the possibility of extending it other quantum programming languages.

}, url = {https://arxiv.org/abs/1812.08726}, author = {Aarthi Sundaram and Brad Lackey} } @article {2279, title = {Morphisms in categories of nonlocal games}, year = {2018}, abstract = {Synchronous correlations provide a class of nonlocal games that behave like functions between finite sets. In this work we examine categories whose morphisms are games with synchronous classical, quantum, or general nonsignaling correlations. In particular, we characterize when morphisms in these categories are monic, epic, sections, or retractions.

}, url = {https://arxiv.org/abs/1810.10074}, author = {Brad Lackey and Nishant Rodrigues} } @article {2281, title = {Quantum adiabatic optimization without heuristics}, year = {2018}, abstract = {Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian H(s) with spectral gap γ(s). Assuming the existence of an oracle Γ such that γ(s)=Θ(Γ(s)), we provide an algorithm that reliably performs QAO in time Oγ\−1minlog(γ\−1min) with Olog(γ\−1min) oracle queries, where γmin=minsγ(s). Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that dH/ds\≈γ(s) and chooses its own runtime T to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle Γ for the problem of finding a vertex m=argminuW(u) of the cost function W:V⟶[0,1], restricting ourselves to computational basis measurements and driving Hamiltonian H(0)=I\−V\−1\∑u,v\∈V|u\⟩\⟨v|, with V=|V|. Requiring only that W have a constant lower bound on its spectral gap and upper bound κ on its spectral ratio, our QAO algorithm returns m using Γ with probability (1\−ε)(1\−e\−1/ε) in time O\˜(ε\−1[V\−\−\√+(κ\−1)2/3V2/3]). This achieves a quantum advantage for all κ, and when κ\≈1, recovers Grover scaling up to logarithmic factors. We implement the algorithm as a subroutine in an optimization procedure that produces m with exponentially small failure probability and expected runtime O\˜(ε\−1[V\−\−\√+(κ\−1)2/3V2/3]), even when κ is not known beforehand.

}, url = {https://arxiv.org/abs/1810.04686}, author = {Michael Jarret and Brad Lackey and Aike Liu and Kianna Wan} } @article {1991, title = {Fast optimization algorithms and the cosmological constant}, journal = {Physical Review D}, volume = {96}, year = {2017}, month = {2017/11/13}, pages = {103512}, abstract = {Denef and Douglas have observed that in certain landscape models the problem of finding small values of the cosmological constant is a large instance of an NP-hard problem. The number of elementary operations (quantum gates) needed to solve this problem by brute force search exceeds the estimated computational capacity of the observable universe. Here we describe a way out of this puzzling circumstance: despite being NP-hard, the problem of finding a small cosmological constant can be attacked by more sophisticated algorithms whose performance vastly exceeds brute force search. In fact, in some parameter regimes the average-case complexity is polynomial. We demonstrate this by explicitly finding a cosmological constant of order 10\−120 in a randomly generated 109 -dimensional ADK landscape.

}, doi = {10.1103/PhysRevD.96.103512}, url = {https://arxiv.org/abs/1706.08503}, author = {Ning Bao and Raphael Bousso and Stephen P. Jordan and Brad Lackey} } @article {2049, title = {Nonlocal games, synchronous correlations, and Bell inequalities}, year = {2017}, month = {2017/09/21}, abstract = {A nonlocal game with a synchronous correlation is a natural generalization of a function between two finite sets, and has recently appeared in the context of quantum graph homomorphisms. In this work we examine analogues of Bell\&$\#$39;s inequalities for synchronous correlations. We show that, unlike general correlations and the CHSH inequality, there can be no quantum Bell violation among synchronous correlations with two measurement settings. However we exhibit explicit analogues of Bell\&$\#$39;s inequalities for synchronous correlations with three measurement settings and two outputs, provide an analogue of Tsirl\&$\#$39;son\&$\#$39;s bound in this setting, and give explicit quantum correlations that saturate this bound.

}, url = {https://arxiv.org/abs/1707.06200}, author = {Brad Lackey and Nishant Rodrigues} } @article {1993, title = {Penalty models for bitstrings of constant Hamming weight}, year = {2017}, month = {2017/04/24}, abstract = {To program a quantum annealer, one must construct objective functions whose minima encode hard constraints imposed by the underlying problem. For such \"penalty models,\" one desires the additional property that the gap in the objective value between such minima and states that fail the constraints is maximized amongst the allowable objective functions. In this short note, we prove the standard penalty model for the constraint that a bitstring has given Hamming weight is optimal with respect to objective value gap.

}, url = {https://arxiv.org/abs/1704.07290}, author = {Brad Lackey} } @article {2048, title = {On the readiness of quantum optimization machines for industrial applications}, year = {2017}, month = {2017/08/31}, abstract = {There have been multiple attempts to demonstrate that quantum annealing and, in particular, quantum annealing on quantum annealing machines, has the potential to outperform current classical optimization algorithms implemented on CMOS technologies. The benchmarking of these devices has been controversial. Initially, random spin-glass problems were used, however, these were quickly shown to be not well suited to detect any quantum speedup. Subsequently, benchmarking shifted to carefully crafted synthetic problems designed to highlight the quantum nature of the hardware while (often) ensuring that classical optimization techniques do not perform well on them. Even worse, to date a true sign of improved scaling with the number problem variables remains elusive when compared to classical optimization techniques. Here, we analyze the readiness of quantum annealing machines for real-world application problems. These are typically not random and have an underlying structure that is hard to capture in synthetic benchmarks, thus posing unexpected challenges for optimization techniques, both classical and quantum alike. We present a comprehensive computational scaling analysis of fault diagnosis in digital circuits, considering architectures beyond D-wave quantum annealers. We find that the instances generated from real data in multiplier circuits are harder than other representative random spin-glass benchmarks with a comparable number of variables. Although our results show that transverse-field quantum annealing is outperformed by state-of-the-art classical optimization algorithms, these benchmark instances are hard and small in the size of the input, therefore representing the first industrial application ideally suited for near-term quantum annealers.

}, url = {https://arxiv.org/abs/1708.09780}, author = {Alejandro Perdomo-Ortiz and Alexander Feldman and Asier Ozaeta and Sergei V. Isakov and Zheng Zhu and Bryan O{\textquoteright}Gorman and Helmut G. Katzgraber and Alexander Diedrich and Hartmut Neven and Johan de Kleer and Brad Lackey and Rupak Biswas} } @article {1992, title = {Substochastic Monte Carlo Algorithms}, year = {2017}, month = {2017/04/28}, abstract = {In this paper we introduce and formalize Substochastic Monte Carlo (SSMC) algorithms. These algorithms, originally intended to be a better classical foil to quantum annealing than simulated annealing, prove to be worthy optimization algorithms in their own right. In SSMC, a population of walkers is initialized according to a known distribution on an arbitrary search space and varied into the solution of some optimization problem of interest. The first argument of this paper shows how an existing classical algorithm, \"Go-With-The-Winners\" (GWW), is a limiting case of SSMC when restricted to binary search and particular driving dynamics.\

Although limiting to GWW, SSMC is more general. We show that (1) GWW can be efficiently simulated within the SSMC framework, (2) SSMC can be exponentially faster than GWW, (3) by naturally incorporating structural information, SSMC can exponentially outperform the quantum algorithm that first inspired it, and (4) SSMC exhibits desirable search features in general spaces. Our approach combines ideas from genetic algorithms (GWW), theoretical probability (Fleming-Viot processes), and quantum computing. Not only do we demonstrate that SSMC is often more efficient than competing algorithms, but we also hope that our results connecting these disciplines will impact each independently. An implemented version of SSMC has previously enjoyed some success as a competitive optimization algorithm for Max-

Most experimental and theoretical studies of adiabatic optimization use stoquastic Hamiltonians, whose ground states are expressible using only real nonnegative amplitudes. This raises a question as to whether classical Monte Carlo methods can simulate stoquastic adiabatic algorithms with polynomial overhead. Here, we analyze diffusion Monte Carlo algorithms. We argue that, based on differences between L1 and L2 normalized states, these algorithms suffer from certain obstructions preventing them from efficiently simulating stoquastic adiabatic evolution in generality. In practice however, we obtain good performance by introducing a method that we call Substochastic Monte Carlo. In fact, our simulations are good classical optimization algorithms in their own right, competitive with the best previously known heuristic solvers for MAX-k-SAT at k=2,3,4.

}, url = {https://arxiv.org/abs/1607.03389}, author = {Michael Jarret and Stephen P. Jordan and Brad Lackey} } @article {1859, title = {Mapping contrained optimization problems to quantum annealing with application to fault diagnosis}, journal = {Frontiers in ICT}, volume = {3}, year = {2016}, month = {2016/07/28}, pages = {14}, abstract = {Current quantum annealing (QA) hardware suffers from practical limitations such as finite\ temperature, sparse connectivity, small qubit numbers, and control error. We propose new algorithms for\ mapping Boolean constraint satisfaction problems (CSPs) onto QA hardware mitigating these limitations.\ In particular, we develop a new embedding algorithm for mapping a CSP onto a hardware Ising model with\ a fixed sparse set of interactions and propose two new decomposition algorithms for solving problems too\ large to map directly into hardware. The mapping technique is locally structured, as hardware compatible\ Ising models are generated for each problem constraint, and variables appearing in different constraints are\ chained together using ferromagnetic couplings. By contrast, global embedding techniques generate a\ hardware-independent Ising model for all the constraints, and then use a minor-embedding algorithm to\ generate\ a hardware compatible Ising model. We give an example of a class of CSPs for which the scaling\ performance\ of the D-Wave hardware using the local mapping technique is significantly better than global\ embedding. We validate\ the approach by applying D- Wave\’s QA hardware to circuit-based fault diagnosis.\ For circuits that embed directly, we\ find that the hardware is typically able to find all solutions from a\ min-fault diagnosis set of size N using 1000 N samples,\ using an annealing rate that is 25 times faster than\ a leading SAT-based sampling method. Furthermore, we apply\ decomposition algorithms to find min-cardinality\ faults for circuits that are up to 5 times larger than can be solved directly on current hardware.

}, url = {http://journal.frontiersin.org/article/10.3389/fict.2016.00014/full}, author = {Bian, Zhengbing and Chudak, Fabian and Robert Brian Israel and Brad Lackey and Macready, William G and Aiden Roy} } @article {bian2014discrete, title = {Discrete optimization using quantum annealing on sparse Ising models}, journal = {Frontiers in Physics}, volume = {2}, year = {2014}, month = {2014/09/01}, pages = {56}, publisher = {Frontiers}, abstract = {This paper discusses techniques for solving discrete optimization problems using quantum annealing. Practical issues likely to affect the computation include precision limitations, finite temperature, bounded energy range, sparse connectivity, and small numbers of qubits. To address these concerns we propose a way of finding energy representations with large classical gaps between ground and first excited states, efficient algorithms for mapping non-compatible Ising models into the hardware, and the use of decomposition methods for problems that are too large to fit in hardware. We validate the approach by describing experiments with D-Wave quantum hardware for low density parity check decoding with up to 1000 variables.}, author = {Bian, Zhengbing and Chudak, Fabian and Israel, Robert and Brad Lackey and Macready, William G and Roy, Aidan} } @article {grant2012galilean, title = {On Galilean connections and the first jet bundle}, journal = {Central European Journal of Mathematics}, volume = {10}, number = {5}, year = {2012}, month = {2012/10/01}, pages = {1889{\textendash}1895}, publisher = {Springer}, abstract = {We see how the first jet bundle of curves into affine space can be realized as a homogeneous space of the Galilean group. Cartan connections with this model are precisely the geometric structure of second-order ordinary differential equations under time-preserving transformations {\textemdash} sometimes called KCC-theory. With certain regularity conditions, we show that any such Cartan connection induces {\textquotedblleft}laboratory{\textquotedblright} coordinate systems, and the geodesic equations in this coordinates form a system of second-order ordinary differential equations. We then show the converse {\textemdash} the {\textquotedblleft}fundamental theorem{\textquotedblright} {\textemdash} that given such a coordinate system, and a system of second order ordinary differential equations, there exists regular Cartan connections yielding these, and such connections are completely determined by their torsion.}, author = {Grant, James DE and Brad Lackey} } @article {lackey2002gauss, title = {On the Gauss{\textendash}Bonnet Formula in Riemann{\textendash}Finsler Geometry}, journal = {Bulletin of the London Mathematical Society}, volume = {34}, number = {03}, year = {2002}, month = {2002/04/01}, pages = {329{\textendash}340}, publisher = {Cambridge Univ Press}, abstract = {Using Chern{\textquoteright}s method of transgression, the Euler class of a compact orientable Riemann{\textendash}Finsler space is represented by polynomials in the connection and curvature matrices of a torsion-free connection. When using the Chern connection (and hence the Christoffel{\textendash}Levi{\textendash}Civita connection in the Riemannian case), this result extends the Gauss{\textendash}Bonnet formula of Bao and Chern to Finsler spaces whose indicatrices need not have constant volume.}, author = {Brad Lackey} } @article {lackey2000metric, title = {Metric Equivalence of Path Spaces}, journal = {Nonlinear Studies}, volume = {7}, number = {2}, year = {2000}, month = {2000/01/01}, abstract = {Local equivalence and the invariants of systems of second order differential equations were studied in a series of papers by Kosambi, Cartan, and Chern. The resulting theory, deemed KCC-theory, is a rich geometric study which in many ways generalizes Riemannian and Finsler geometry. Yet, in many applications one requires a metric structure in addition to the systems of second order differential equations. We pose a geometry which is equipped with both of these structures, and solve the problem of local equivalence and thus determining a preferred connection and finding a generating set for all the invariants of the theory.}, author = {Brad Lackey} } @article {1266, title = {On Galilean connections and the first jet bundle}, year = {1999}, month = {1999/09/24}, abstract = { We express the first jet bundle of curves in Euclidean space as homogeneous spaces associated to a Galilean-type group. Certain Cartan connections on a manifold with values in the Lie algebra of the Galilean group are characterized as geometries associated to systems of second order ordinary differential equations. We show these Cartan connections admit a form of normal coordinates, and that in these normal coordinates the geodesic equations of the connection are second order ordinary differential equations. We then classify such connections by some of their torsions, extending a classical theorem of Chern involving the geometry associated to a system of second order differential equations. }, url = {http://arxiv.org/abs/math/9909148v1}, author = {James D. E. Grant and Brad Lackey} } @article {lackey1999model, title = {A model of trophodynamics}, journal = {Nonlinear Analysis: Theory, Methods \& Applications}, volume = {35}, number = {1}, year = {1999}, month = {1999/01/01}, pages = {37{\textendash}57}, publisher = {Pergamon}, doi = {10.1016/S0362-546X(98)00097-2}, author = {Brad Lackey} } @article {bao1996hodge, title = {A Hodge decomposition theorem for Finsler spaces}, journal = {Comptes rendus de l{\textquoteright}Acad{\'e}mie des sciences. S{\'e}rie 1, Math{\'e}matique}, volume = {323}, number = {1}, year = {1996}, month = {1996/01/01}, pages = {51{\textendash}56}, publisher = {Elsevier}, abstract = {Soit (M,F) une vari\e{\textquoteright}t{\'e} finsl{\'e}rienne compacte sans bord. On donne une condition n{\'e}cessaire et suffisante, portant sur le tenseur fondamental, afin q{\textquoteright}une forme diff{\'e}rentielle ext{\'e}rieure de M soit harmonique. On introduit aussi le laplacien sur M et on d{\'e}montre l{\textquoteright}analoque du th{\'e}or{\`e}me de Hodge dans le cas finsl{\'e}rien.}, author = {Bao, David and Brad Lackey} }