Ryan Mann

Quantum Physics, Complexity Theory, & Combinatorics



  • Efficient Algorithms for Approximating Quantum Partition Functions

    Ryan L. Mann and Tyler Helmuth, arXiv e-prints (2020). arXiv Post

    We establish a polynomial-time approximation algorithm for partition functions of quantum spin models at high temperature. Our algorithm is based on the quantum cluster expansion of Netočný and Redig and the cluster expansion approach to designing algorithms due to Helmuth, Perkins, and Regts. Similar results have previously been obtained by related methods, and our main contribution is a simple and slightly sharper analysis for the case of pairwise interactions on bounded-degree graphs.

  • On the Parameterised Complexity of Induced Multipartite Graph Parameters

    Ryan L. Mann, Luke Mathieson, and Catherine Greenhill, arXiv e-prints (2020). arXiv Post

    We introduce a family of graph parameters, called induced multipartite graph parameters, and study their computational complexity. First, we consider the following decision problem: an instance is an induced multipartite graph parameter \(p\) and a given graph \(G\), and for natural numbers \(k\geq2\) and \(\ell\), we must decide whether the maximum value of \(p\) over all induced \(k\)-partite subgraphs of \(G\) is at most \(\ell\). We prove that this problem is \(\text{W[1]-hard}\). Next, we consider a variant of this problem, where we must decide whether the given graph \(G\) contains a sufficiently large induced \(k\)-partite subgraph \(H\) such that \(p(H)\leq\ell\). We show that for certain parameters this problem is \(\text{para-NP-hard}\), while for others it is fixed-parameter tractable.

  • Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs

    Ryan L. Mann and Michael J. Bremner, Quantum 3, 162 (2019). arXiv Post Journal

    We study the problem of approximating the Ising model partition function with complex parameters on bounded degree graphs. We establish a deterministic polynomial-time approximation scheme for the partition function when the interactions and external fields are absolutely bounded close to zero. Furthermore, we prove that for this class of Ising models the partition function does not vanish. Our algorithm is based on an approach due to Barvinok for approximating evaluations of a polynomial based on the location of the complex zeros and a technique due to Patel and Regts for efficiently computing the leading coefficients of graph polynomials on bounded degree graphs. Finally, we show how our algorithm can be extended to approximate certain output probability amplitudes of quantum circuits.

  • On the Complexity of Random Quantum Computations and the Jones Polynomial

    Ryan L. Mann and Michael J. Bremner, arXiv e-prints (2018). arXiv Post

    There is a natural relationship between Jones polynomials and quantum computation. We use this relationship to show that the complexity of evaluating relative-error approximations of Jones polynomials can be used to bound the classical complexity of approximately simulating random quantum computations. We prove that random quantum computations cannot be classically simulated up to a constant total variation distance, under the assumption that (1) the Polynomial Hierarchy does not collapse and (2) the average-case complexity of relative-error approximations of the Jones polynomial matches the worst-case complexity over a constant fraction of random links. Our results provide a straightforward relationship between the approximation of Jones polynomials and the complexity of random quantum computations.

  • Efficient Recycling Strategies for Preparing Large Fock States from Single-Photon Sources — Applications to Quantum Metrology

    Keith R. Motes, Ryan L. Mann, Jonathan P. Olson, Nicholas M. Studer, E. Annelise Bergeron, Alexei Gilchrist, Jonathan P. Dowling, Dominic W. Berry, and Peter P. Rohde, Physical Review A 94, 012344 (2016). arXiv Journal

    Fock states are a fundamental resource for many quantum technologies such as quantum metrology. While much progress has been made in single-photon source technologies, preparing Fock states with large photon number remains challenging. We present and analyze a bootstrapped approach for non-deterministically preparing large photon-number Fock states by iteratively fusing smaller Fock states on a beamsplitter. We show that by employing state recycling we are able to exponentially improve the preparation rate over conventional schemes, allowing the efficient preparation of large Fock states. The scheme requires single-photon sources, beamsplitters, number-resolved photo-detectors, fast-feedforward, and an optical quantum memory.