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.

1 aLackey, Brad uhttps://arxiv.org/abs/1810.1000501529nas a2200109 4500008004100000245005800041210005700099520118800156100002101344700001701365856003701382 2018 eng d00aMathematical methods for resource-based type theories0 aMathematical methods for resourcebased type theories3 aWith 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'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.

1 aSundaram, Aarthi1 aLackey, Brad uhttps://arxiv.org/abs/1812.0872600683nas a2200109 4500008004100000245004600041210004600087520036300133100001700496700002300513856003700536 2018 eng d00aMorphisms in categories of nonlocal games0 aMorphisms in categories of nonlocal games3 aSynchronous 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.

1 aLackey, Brad1 aRodrigues, Nishant uhttps://arxiv.org/abs/1810.1007402027nas a2200133 4500008004100000245005400041210005400095520164000149100002001789700001701809700001401826700001601840856003701856 2018 eng d00aQuantum adiabatic optimization without heuristics0 aQuantum adiabatic optimization without heuristics3 aQuantum 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.

1 aJarret, Michael1 aLackey, Brad1 aLiu, Aike1 aWan, Kianna uhttps://arxiv.org/abs/1810.0468601300nas a2200169 4500008004100000245006300041210006300104260001500167300001100182490000700193520081800200100001401018700002001032700002401052700001701076856003701093 2017 eng d00aFast optimization algorithms and the cosmological constant0 aFast optimization algorithms and the cosmological constant c2017/11/13 a1035120 v963 aDenef 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.

1 aBao, Ning1 aBousso, Raphael1 aJordan, Stephen, P.1 aLackey, Brad uhttps://arxiv.org/abs/1706.0850301239nas a2200121 4500008004100000245006800041210006600109260001500175520085000190100001701040700002301057856003701080 2017 eng d00aNonlocal games, synchronous correlations, and Bell inequalities0 aNonlocal games synchronous correlations and Bell inequalities c2017/09/213 aA 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'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's inequalities for synchronous correlations with three measurement settings and two outputs, provide an analogue of Tsirl'son's bound in this setting, and give explicit quantum correlations that saturate this bound.

1 aLackey, Brad1 aRodrigues, Nishant uhttps://arxiv.org/abs/1707.0620001001nas a2200109 4500008004100000245006100041210006100102260001500163520065900178100001700837856003700854 2017 eng d00aPenalty models for bitstrings of constant Hamming weight0 aPenalty models for bitstrings of constant Hamming weight c2017/04/243 aTo 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.

1 aLackey, Brad uhttps://arxiv.org/abs/1704.0729002646nas a2200241 4500008004100000245008200041210006900123260001500192520190700207100002902114700002302143700001802166700002302184700001502207700002002222700002702242700002402269700001902293700002002312700001702332700001802349856003702367 2017 eng d00aOn the readiness of quantum optimization machines for industrial applications0 areadiness of quantum optimization machines for industrial applic c2017/08/313 aThere 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.

1 aPerdomo-Ortiz, Alejandro1 aFeldman, Alexander1 aOzaeta, Asier1 aIsakov, Sergei, V.1 aZhu, Zheng1 aO'Gorman, Bryan1 aKatzgraber, Helmut, G.1 aDiedrich, Alexander1 aNeven, Hartmut1 ade Kleer, Johan1 aLackey, Brad1 aBiswas, Rupak uhttps://arxiv.org/abs/1708.0978003676nas a2200121 4500008004100000245004100041210004100082260001500123520334200138100002003480700001703500856003703517 2017 eng d00aSubstochastic Monte Carlo Algorithms0 aSubstochastic Monte Carlo Algorithms c2017/04/283 aIn 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.

1 aJarret, Michael1 aJordan, Stephen, P.1 aLackey, Brad uhttps://arxiv.org/abs/1607.0338902179nas a2200157 4500008004100000245010300041210006900144520165700213100002001870700001901890700001901909700001701928700002501945700001501970856003601985 2016 eng d00aMapping constrained optimization problems to quantum annealing with application to fault diagnosis0 aMapping constrained optimization problems to quantum annealing w3 aCurrent 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. In 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 D-Wave's QA hardware using the local mapping technique is significantly better than global embedding. We validate the approach by applying D-Wave's 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 1000N samples, using an annealing rate that is 25 times faster than a leading SAT-based sampling method. Further, 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.1 aBian, Zhengbing1 aChudak, Fabian1 aIsrael, Robert1 aLackey, Brad1 aMacready, William, G1 aRoy, Aidan uhttp://arxiv.org/abs/1603.0311103037nas a2200193 4500008004100000245010200041210006900143260001500212300000700227490000600234520240900240100002002649700001902669700002602688700001702714700002502731700001502756856007202771 2016 eng d00aMapping contrained optimization problems to quantum annealing with application to fault diagnosis0 aMapping contrained optimization problems to quantum annealing wi c2016/07/28 a140 v33 aCurrent 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.

1 aBian, Zhengbing1 aChudak, Fabian1 aIsrael, Robert, Brian1 aLackey, Brad1 aMacready, William, G1 aRoy, Aiden uhttp://journal.frontiersin.org/article/10.3389/fict.2016.00014/full01371nas a2200193 4500008004100000245007300041210006900114260002600183300000700209490000600216520073500222100002000957700001900977700001900996700001701015700002501032700001501057856010501072 2014 eng d00aDiscrete optimization using quantum annealing on sparse Ising models0 aDiscrete optimization using quantum annealing on sparse Ising mo bFrontiersc2014/09/01 a560 v23 aThis 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.1 aBian, Zhengbing1 aChudak, Fabian1 aIsrael, Robert1 aLackey, Brad1 aMacready, William, G1 aRoy, Aidan uhttps://quics.umd.edu/publications/discrete-optimization-using-quantum-annealing-sparse-ising-models01291nas a2200145 4500008004100000245005300041210005000094260002500144300001600169490000700185520083300192100002001025700001701045856008301062 2012 eng d00aOn Galilean connections and the first jet bundle0 aGalilean connections and the first jet bundle bSpringerc2012/10/01 a1889–18950 v103 aWe 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 — sometimes called KCC-theory. With certain regularity conditions, we show that any such Cartan connection induces “laboratory” coordinate systems, and the geodesic equations in this coordinates form a system of second-order ordinary differential equations. We then show the converse — the “fundamental theorem” — 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.1 aDE Grant, James1 aLackey, Brad uhttps://quics.umd.edu/publications/galilean-connections-and-first-jet-bundle-000923nas a2200133 4500008004100000245006400041210005700105260003700162300001400199490000700213520045100220100001700671856010100688 2002 eng d00aOn the Gauss–Bonnet Formula in Riemann–Finsler Geometry0 aGauss–Bonnet Formula in Riemann–Finsler Geometry bCambridge Univ Pressc2002/04/01 a329–3400 v343 aUsing Chern's method of transgression, the Euler class of a compact orientable Riemann–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–Levi–Civita connection in the Riemannian case), this result extends the Gauss–Bonnet formula of Bao and Chern to Finsler spaces whose indicatrices need not have constant volume.1 aLackey, Brad uhttps://quics.umd.edu/publications/gauss%E2%80%93bonnet-formula-riemann%E2%80%93finsler-geometry00982nas a2200121 4500008004100000245003800041210003800079260001500117490000600132520063500138100001700773856007000790 2000 eng d00aMetric Equivalence of Path Spaces0 aMetric Equivalence of Path Spaces c2000/01/010 v73 aLocal 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.1 aLackey, Brad uhttps://quics.umd.edu/publications/metric-equivalence-path-spaces01069nas a2200121 4500008004100000245005300041210005000094260001500144520070700159100002400866700001700890856004000907 1999 eng d00aOn Galilean connections and the first jet bundle0 aGalilean connections and the first jet bundle c1999/09/243 a 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. 1 aGrant, James, D. E.1 aLackey, Brad uhttp://arxiv.org/abs/math/9909148v100342nas a2200121 4500008004100000245003000041210002800071260002500099300001200124490000700136100001700143856006000160 1999 eng d00aA model of trophodynamics0 amodel of trophodynamics bPergamonc1999/01/01 a37–570 v351 aLackey, Brad uhttps://quics.umd.edu/publications/model-trophodynamics00458nas a2200121 4500008004100000245007000041210006900111300001200180490000700192100001500199700001700214856010500231 1999 eng d00aRanders surfaces whose Laplacians have completely positive symbol0 aRanders surfaces whose Laplacians have completely positive symbo a27–400 v381 aBao, David1 aLackey, Brad uhttps://quics.umd.edu/publications/randers-surfaces-whose-laplacians-have-completely-positive-symbol00387nas a2200109 4500008004100000245005500041210005300096260001300149300001400162100001700176856008400193 1998 eng d00aA Bochner Vanishing Theorem for Elliptic Complexes0 aBochner Vanishing Theorem for Elliptic Complexes bSpringer a199–2261 aLackey, Brad uhttps://quics.umd.edu/publications/bochner-vanishing-theorem-elliptic-complexes00468nas a2200121 4500008004100000245007500041210006900116260001300185300001400198100001500212700001700227856010200244 1998 eng d00aA geometric inequality and a Weitzenboeck formula for Finsler surfaces0 ageometric inequality and a Weitzenboeck formula for Finsler surf bSpringer a245–2751 aBao, David1 aLackey, Brad uhttps://quics.umd.edu/publications/geometric-inequality-and-weitzenboeck-formula-finsler-surfaces00390nas a2200109 4500008004100000245005600041210005400097260001300151300001400164100001700178856008500195 1998 eng d00aA Lichnerowicz Vanishing Theorem for Finsler Spaces0 aLichnerowicz Vanishing Theorem for Finsler Spaces bSpringer a227–2431 aLackey, Brad uhttps://quics.umd.edu/publications/lichnerowicz-vanishing-theorem-finsler-spaces00780nas a2200145 4500008004100000245005300041210005100094260002500145300001200170490000800182520033000190100001500520700001700535856008200552 1996 eng d00aA Hodge decomposition theorem for Finsler spaces0 aHodge decomposition theorem for Finsler spaces bElsevierc1996/01/01 a51–560 v3233 aSoit (M,F) une vari\e'té finslérienne compacte sans bord. On donne une condition nécessaire et suffisante, portant sur le tenseur fondamental, afin q'une forme différentielle extérieure de M soit harmonique. On introduit aussi le laplacien sur M et on démontre l'analoque du théorème de Hodge dans le cas finslérien.1 aBao, David1 aLackey, Brad uhttps://quics.umd.edu/publications/hodge-decomposition-theorem-finsler-spaces00436nas a2200121 4500008004100000245006600041210006600107300001200173490000800185100001500193700001700208856008900225 1996 eng d00aSpecial eigenforms on the sphere bundle of a Finsler manifold0 aSpecial eigenforms on the sphere bundle of a Finsler manifold a67–780 v1961 aBao, David1 aLackey, Brad uhttps://quics.umd.edu/publications/special-eigenforms-sphere-bundle-finsler-manifold