Combinatorics and Optimization
http://hdl.handle.net/10012/9928
2024-02-28T03:02:17ZGraph-Theoretic Techniques for Optimizing NISQ Algorithms
http://hdl.handle.net/10012/20343
Graph-Theoretic Techniques for Optimizing NISQ Algorithms
Jena, Andrew
Entering the NISQ era, the search for useful yet simple quantum algorithms is perhaps of more importance now than it may ever be in the future. In place of quantum walks, the quantum Fourier transform, and asymptotic results about far-term advantages of quantum computation, the real-world applications of today involve nitty-gritty details and optimizations which make the most use of our limited resources. These priorities pervade the research presented in this thesis, which focuses on combinatorial techniques for optimizing NISQ algorithms.
With variational algorithms directing the discussion, we investigate methods for reducing Hamiltonians, reducing measurement errors, and reducing entangling gates. All three of these reductions bring us ever closer to demonstrating the utility of quantum devices, by improving some of the major bottlenecks of the NISQ era, and all of them do so while rarely ever leaving the combinatorial framework provided by stabilizer states. The qubit tapering approach to Hamiltonian simplification which we present was developed independently of the work by Bravyi et al., who discovered how to reduce qubit counts by parallelizing the computation of the ground state. The measurement scheme we describe, AEQuO, is built upon years of research and dozens of articles detailing, comparing, and contrasting a plethora of schemes. The circuit optimization technique we introduce answers a question posed by Adcock et al., and our ideas and proofs are fundamentally grounded in the literature of isotropic systems and the graph-based results which have followed from it.
2024-02-15T00:00:00ZFormalizing the Excluded Minor Characterization of Binary Matroids in the Lean Theorem Prover
http://hdl.handle.net/10012/20273
Formalizing the Excluded Minor Characterization of Binary Matroids in the Lean Theorem Prover
Gusakov, Alena
A matroid is a mathematical object that generalizes the notion of linear independence of a set of vectors to an abstract independence of sets, with applications to optimization, linear algebra, graph theory, and algebraic geometry. Matroid theorists are often concerned with representations of matroids over fields. Tutte's seminal theorem proven in 1958 characterizes matroids representable over GF(2) by noncontainment of U2,4 as a matroid minor. In this thesis, we document a formalization of the theorem and its proof in the Lean Theorem Prover, building on its community-built mathematics library, mathlib.
2024-01-23T00:00:00ZImplementing the Castryck-Decru attack on SIDH with general primes
http://hdl.handle.net/10012/20220
Implementing the Castryck-Decru attack on SIDH with general primes
Laflamme, Jeanne
With the rapid progress of quantum computers in recent years, efforts have been made to standardize new public-key cryptographic protocols which would be secure against them. One of the schemes in contention was Supersingular Isogeny Diffie-Hellman (SIDH). This scheme relied on the assumed hardness of the isogeny problem on supersingular elliptic curves. However, in the SIDH protocol extra information on the secret isogenies is transmitted. In July 2022, Castryck and Decru found a way to exploit this information to completely break the scheme. They gave an implementation of their attack which allows to recover Bob’s secret key in a few seconds on a laptop. Usually, Alice and Bob’s secret isogenies are taken to have degree 2^a and 3^b respectively. This thesis gives a more general implementation of the attack in Magma which works even if Alice and Bob’s secret isogenies have degrees lA^a and lB^b for more general primes lA and lB.
2024-01-09T00:00:00ZGraphical CSS Code Transformation Using ZX Calculus
http://hdl.handle.net/10012/20193
Graphical CSS Code Transformation Using ZX Calculus
Li, Sarah Meng
In this work, we present a generic approach to transform CSS codes by building upon their equivalence to phase-free ZX diagrams. Using the ZX calculus, we demonstrate diagrammatic transformations between encoding maps associated with different codes. As a motivating example, we give explicit transformations between the Steane code and the quantum Reed-Muller code, since by switching between these two codes, one can obtain a fault-tolerant universal gate set. To this end, we propose a bidirectional rewrite rule to find a (not necessarily transversal) physical implementation for any logical ZX diagram in
any CSS code. We then focus on two code transformation techniques: code morphing, a procedure that transforms a code while retaining its fault-tolerant gates, and gauge fixing, where complimentary codes can be obtained from a common subsystem code (e.g., the Steane and the quantum Reed-Muller codes from the [[15, 1, 3, 3]] code). We provide explicit graphical derivations for these techniques and show how ZX and graphical encoder maps relate several equivalent perspectives on these code-transforming operations.
2023-12-21T00:00:00Z