Measurement-based quantum computation (MBQC) offers a fundamentally unique paradigm to design quantum algorithms. Indeed, due to the inherent randomness of quantum measurements, the natural operations in MBQC are not deterministic and unitary, but are rather augmented with probabilistic by-products. Yet, the main algorithmic use of MBQC so far has been to completely counteract this probabilistic nature in order to simulate unitary computations expressed in the circuit model. In this work, we propose designing MBQC algorithms that embrace this inherent randomness and treat the random by-products in MBQC as a resource for computation. As a natural application where randomness can be beneficial, we consider generative modeling, a task in machine learning centered around generating complex probability distributions. To address this task, we propose a variational MBQC algorithm equipped with control parameters that allow one to directly adjust the degree of randomness to be admitted in the computation. Our algebraic and numerical findings indicate that this additional randomness can lead to significant gains in expressivity and learning performance for certain generative modeling tasks, respectively. These results highlight the potential advantages in exploiting the inherent randomness of MBQC and motivate further research into MBQC-based algorithms.
Measurement-based quantum computation (MBQC) offers a fundamentally unique paradigm to design quantum algorithms. Indeed, due to the inherent randomness of quantum measurements, the natural operations in MBQC are not deterministic and unitary, but are rather augmented with probabilistic by-products. Yet, the main algorithmic use of MBQC so far has been to completely counteract this probabilistic nature in order to simulate unitary computations expressed in the circuit model. In this work, we propose designing MBQC algorithms that embrace this inherent randomness and treat the random by-products in MBQC as a resource for computation. As a natural application where randomness can be beneficial, we consider generative modeling, a task in machine learning centered around generating complex probability distributions. To address this task, we propose a variational MBQC algorithm equipped with control parameters that allow one to directly adjust the degree of randomness to be admitted in the computation. Our algebraic and numerical findings indicate that this additional randomness can lead to significant gains in expressivity and learning performance for certain generative modeling tasks, respectively. These results highlight the potential advantages in exploiting the inherent randomness of MBQC and motivate further research into MBQC-based algorithms.
Measurement-based quantum computation (MBQC) is a framework for quantum information processing in which a computational task is carried out through one-qubit measurements on a highly entangled resource state. Due to the indeterminacy of the outcomes of a quantum measurement, the random outcomes of these operations, if not corrected, yield a variational quantum channel family. Traditionally, this randomness is corrected through classical processing in order to ensure deterministic unitary computations. Recently, variational measurement-based quantum computation (VMBQC) has been introduced to exploit this measurement-induced randomness to gain an advantage in generative modeling. A limitation of this approach is that the corresponding channel model has twice as many parameters compared to the unitary model, scaling as N×D, where N is the number of logical qubits (width) and D is the depth of the VMBQC model. This can often make optimization more difficult and may lead to poorly trainable models. In this paper, we present a restricted VMBQC model that extends the unitary setting to a channel-based one using only a single additional trainable parameter. We show, both numerically and algebraically, that this minimal extension is sufficient to generate probability distributions that cannot be learned by the corresponding unitary model.
Abstract Variational quantum algorithms are considered one of the most promising methods for obtaining near-term quantum advantages; however, most of these algorithms are only expressed in the conventional quantum circuit scheme. The roadblock to developing quantum algorithms with the measurement-based quantum computation (MBQC) scheme is resource cost. Recently, we discovered that the realization of multi-qubit rotation operations only requires a constant number of single-qubit measurements with the MBQC scheme, providing a potential advantage in terms of resource cost. The structure of the Hamiltonian variational ansatz aligns well with this characteristic. Thus, we propose an efficient measurement-based quantum algorithm for quantum many-body system simulation tasks, called measurement-based Hamiltonian variational ansatz (MBHVA). We then demonstrate its effectiveness, efficiency, and advantages with the two-dimensional Heisenberg model and the Fermi–Hubbard chain. Numerical experiments show that MBHVA can have similar performance as circuit-based ansatz, and is expected to reduce operation counts during execution compared to quantum circuits, bringing the advantage of running time. We conclude that the MBQC scheme is potentially feasible for achieving near-term quantum advantages in the noisy intermediate-scale quantum era, especially in the presence of large multi-qubit rotation operations.
This thesis considers various paradigms of quantum computation in an attempt to understand the nature of the underlying physics. A standard approach is to consider unitary computation on pure input states, such that the outcome of the computation is determined by single computational basis measurement on the output state. It has been shown that there exists equivalent models of computation, such as measurement based quantum computing (MBQC), which provide insight into the role of entanglement and measurement. Furthermore, constraining or relaxing available resources can directly impacts the power of the computation, allowing one to gauge their role in the process. Here, we first extend known constructions such as Matrix Product States, MBQC and the oneclean qubit model to a mixed state formalism, in an attempt to develop computational models where noise acting on the physical resources, as might be experienced in laboratory settings, may be mapped to logical noise on the computation. Next, we introduce Measurement-Based Classical Computing, an essentially classical model of computation, wherein the complexity hard wired into probability distributions generated via quantum means yields surprising non classical results. Finally, we consider postselection the ability to discard displeasing measurement outcomes and argue that it may be used in a tame way, which does not provide a dramatic increase in computational power. From here, we develop a new Hamiltonian, based on a circuit to Hamiltonian construction, presenting evidence of QMA-hardness.
This thesis is focused on the generation and understanding of particular kinds of quantum randomness. Randomness is useful for many tasks in physics and information processing, from randomized benchmarking , to black hole physics , as well demonstrating a so-called quantum speedup , and many other applications. On the one hand we explore how to generate a particular form of random evolution known as a t-design. On the other we show how this can also give instances for quantum speedup - where classical computers cannot simulate the randomness efficiently. We also show that this is still possible in noisy realistic settings. More specifically, this thesis is centered around three main topics. The first of these being the generation of epsilon-approximate unitary t-designs. In this direction, we first show that non-adaptive, fixed measurements on a graph state composed of poly(n,t,log(1/epsilon)) qubits, and with a regular structure (that of a brickwork state) effectively give rise to a random unitary ensemble which is a epsilon-approximate t-design. This work is presented in Chapter 3. Before this work, it was known that non-adaptive fixed XY measurements on a graph state give rise to unitary t-designs , however the graph states used there were of complicated structure and were therefore not natural candidates for measurement based quantum computing (MBQC), and the circuits to make them were complicated. The novelty in our work is showing that t-designs can be generated by fixed, non-adaptive measurements on graph states whose underlying graphs are regular 2D lattices. These graph states are universal resources for MBQC. Therefore, our result allows the natural integration of unitary t-designs, which provide a notion of quantum pseudorandomness which is very useful in quantum algorithms, into quantum algorithms running in MBQC. Moreover, in the circuit picture this construction for t-designs may be viewed as a constant depth quantum circuit, albeit with a polynomial number of ancillas. We then provide new constructions of epsilon-approximate unitary t-designs both in the circuit model and in MBQC which are based on a relaxation of technical requirements in previous constructions. These constructions are found in Chapters 4 and 5.
Circuit-based quantum computing (CBQC), also known as the gate model, is currently regarded as the leading paradigm for performing quantum computation and has garnered widespread interest due to its relatively better-established implementation and close intuitive resemblance to classical computation. However, an alternative model that solely utilizes single-qubit measurements on entangled states to perform computation, namely the measurement-based quantum computing (MBQC), has started to attract further research interest as it is deemed more naturally suited for certain quantum hardware architectures, though its actual implementation remains largely underexplored. Recently, there have been preliminary efforts to characterize the specific regimes in which MBQC may potentially be more advantageous compared to CBQC. Nevertheless, a more systematic assessment is necessary to assess the suitability of each model across a broader range of more practical cases. In this work, we present a detailed comparative analysis of CBQC and MBQC, beginning with reviewing the theoretical foundations of each model before highlighting its distinguishing features that set the two paradigms apart. Furthermore, building on previous work, we propose a generalized regime analysis that more accurately captures the conditions under which a given quantum algorithm is more favorably executed in MBQC or CBQC. Subsequently, we identify critical parameters that likely determine whether a quantum algorithm is better suited to CBQC or MBQC, categorizing detailed key factors and performance metrics into layers of quantum computation. Next, we propose a decision flow that, given specific hardware constraints and algorithm requirements, guides the selection to the most appropriate model, discussing suitability in two representative worked examples of quantum algorithm applications: Quantum Fourier Transform (QFT) and Variational Quantum Algorithm (VQE). Last, we discuss the potential to combine both models as a hybrid approach to leverage the best of both worlds and explore its benefits for practical quantum computing applications.
The generation of true randomness remains a significant challenge in computer science, particularly when relying solely on classical algorithms. Many current approaches employ pseudo-random number generators (PRNGs), which, despite their computational efficiency, are inherently predictable and lack genuine randomness. This paper proposes a novel method for algorithmic randomness generation leveraging the principles of quantum walks. We demonstrate that the inherent uncertainty and superposition properties of quantum systems provide a robust mechanism for generating truly random numbers. Specifically, we outline a framework for designing quantum walks on graphs, where the evolution of the walker's state is fundamentally probabilistic and unpredictable. The core of our approach resides in exploiting the quantum walk's non-deterministic nature to produce sequences of numbers that exhibit statistical properties consistent with true randomness. The theoretical framework is presented, including a detailed description of the mathematical formalism underlying the quantum walk and the probability distribution of the walker's positions. We highlight the potential advantages of this approach, particularly in scenarios demanding high-quality randomness for cryptographic applications or simulations. The key concept is to translate a classical problem into a quantum one, where the inherent probabilistic nature of quantum mechanics offers a superior solution to the problem of generating genuine randomness.