Measurement-based quantum computation (MBQC) has emerged as a new approach to quantum computation where the notion of measurement is the main driving force of computation. This is in contrast with the more traditional circuit model that takes unitary operations as fundamental. Among measurement-based quantum computation methods the recently introduced one-way quantum computer stands out as basic and fundamental. The key idea is to start from an entangled state and then use measurements and one-qubit unitaries, which may be dependent on the outcomes of measurements, to guide the computation. The main point is that one never has to perform unitaries on more than one qubit at a time after the initial preparation of an entangled state. The “programs” that one writes in this model are traditionally called “patterns.” In this chapter, we develop a rigorous mathematical model underlying measurement-based quantum computation. We give syntax, operational semantics, denotational semantics, and an algebra of programs derived from the denotational semantics. We also present a rewrite theory and prove a general standardization theorem that allows all programs to be put in a semantically equivalent standard form. Standardization has far-reaching consequences: a new physical architecture based on performing all the entanglement in the beginning, parallelization by exposing the dependency structure of measurements, and expressiveness theorems. We use our general measurement calculus not just to formalize the one-way model but also several other measurement-based models, e.g., Teleportation, Phase, and Pauli models, and present compositional embeddings of them into and from the one-way model.
Measurement-based quantum computing (MBQC) is a promising quantum computing paradigm that performs computation through "one-way" measurements on entangled quantum qubits. It is widely used in photonic quantum computing (PQC), where the computation is carried out on photonic cluster states (i.e., a 2-D mesh of entangled photons). In MBQC-based PQC, the cluster state depth (i.e., the length of one-way measurements) plays an important role in the overall execution time and circuit error. In this paper, we propose FMCC, a compilation framework that employs dynamic programming with heuristics to efficiently minimize the cluster state depth. Experimental results on six quantum applications show that FMCC achieves 51.7%, 57.4%, and 56.8% average depth reductions in small, medium, and large qubit counts compared to the state-of-the-art MBQC compilations.
Photonic quantum computers, programed within the framework of the measurement-based quantum computing (MBQC), and gate-based platforms are racing toward useful quantum advantage, and some algorithms have emerged as main candidates to reach this goal in the near term. The majority of these algorithms are only expressed in the gate-based model of computation, which is incompatible with photonic platforms. Methods to translate gate-based algorithms into the MBQC framework exist, but they are not always optimal in terms of resource cost. In our work, we propose an MBQC algorithm to run the quantum approximate optimization algorithm (QAOA). Furthermore, we apply the MBQC-QAOA algorithm to the Max
K-Cut problem, for all values of
K, expressing the cost Hamiltonian and its constraints in a form easily implementable in the MBQC model. We conclude by analyzing the resource cost of our algorithm, compared to the case of translating a gate-based QAOA algorithm into MBQC rules, and show up to a 30-fold improvement. With our work, we contribute to closing the gap between gate-based and MBQC near-term algorithms, a gap not reflecting the current status of the hardware development.