Abstract Unravelling the source of quantum computing power has been a major goal in the field of quantum information science. In recent years, the quantum resource theory (QRT) has been established to characterize various quantum resources, yet their roles in quantum computing tasks still require investigation. The so-called universal quantum computing model (UQCM), e.g. the circuit model, has been the main framework to guide the design of quantum algorithms, creation of real quantum computers etc. In this work, we combine the study of UQCM together with QRT. We find, on one hand, using QRT can provide a resource-theoretic characterization of a UQCM, the relation among models and inspire new ones, and on the other hand, using UQCM offers a framework to apply resources, study relation among these resources and classify them. We develop the theory of universal resources in the setting of UQCM, and find a rich spectrum of UQCMs and the corresponding universal resources. Depending on a hierarchical structure of resource theories, we find models can be classified into families . In this work, we study three natural families of UQCMs in detail: the amplitude family, the quasi-probability family, and the Hamiltonian family. They include some well known models, like the measurement-based model and adiabatic model, and also inspire new models such as the contextual model that we introduce. Each family contains at least a triplet of models, and such a succinct structure of families of UQCMs offers a unifying picture to investigate resources and design models. It also provides a rigorous framework to resolve puzzles, such as the role of entanglement versus interference, and unravel resource-theoretic features of quantum algorithms.
Abstract Unravelling the source of quantum computing power has been a major goal in the field of quantum information science. In recent years, the quantum resource theory (QRT) has been established to characterize various quantum resources, yet their roles in quantum computing tasks still require investigation. The so-called universal quantum computing model (UQCM), e.g. the circuit model, has been the main framework to guide the design of quantum algorithms, creation of real quantum computers etc. In this work, we combine the study of UQCM together with QRT. We find, on one hand, using QRT can provide a resource-theoretic characterization of a UQCM, the relation among models and inspire new ones, and on the other hand, using UQCM offers a framework to apply resources, study relation among these resources and classify them. We develop the theory of universal resources in the setting of UQCM, and find a rich spectrum of UQCMs and the corresponding universal resources. Depending on a hierarchical structure of resource theories, we find models can be classified into families . In this work, we study three natural families of UQCMs in detail: the amplitude family, the quasi-probability family, and the Hamiltonian family. They include some well known models, like the measurement-based model and adiabatic model, and also inspire new models such as the contextual model that we introduce. Each family contains at least a triplet of models, and such a succinct structure of families of UQCMs offers a unifying picture to investigate resources and design models. It also provides a rigorous framework to resolve puzzles, such as the role of entanglement versus interference, and unravel resource-theoretic features of quantum algorithms.
Quantum computing has been proven to be powerful, however, there are still great challenges for building real quantum computers due to the requirements of both fault-tolerance and universality. There is still no systematic method to design fast quantum algorithms and identify the key quantum resources. In this work, we develop a resource-theoretic approach to characterize universal quantum computing models and the universal resources for quantum computing. Our theory combines the framework of universal quantum computing model (UQCM) and the quantum resource theory (QRT). The former has played major roles in quantum computing, while the later was developed mainly for quantum information theory. Putting them together proves to be ‘win-win’: on one hand, using QRT can provide a resource-theoretic characterization of a UQCM, the relation among models and inspire new ones, and on the other hand, using UQCM offers a framework to apply resources, study relation among resources and classify them. In quantum theory, we mainly study states, evolution, observable, and probability from measurements, and this motivates the introduction of different families of UQCMs. A family also includes generations depending on a hierarchical structure of resource theories. We introduce a table of UQCMs by first classifying two categories of models: one referring to the format of information, and one referring to the logical evolution of information requiring quantum error-correction codes. Each category contains a few families of models, leading to more than one hundred of them in total. Such a rich spectrum of models include some well-known ones that people use, such as the circuit model, the adiabatic model, but many of them are relatively new and worthy of more study in the future. Among them are the models of quantum von Neumann architectures established recently. This type of architecture or model circumvents the no-go theorems on both the quantum program storage and quantum control unit, enabling the construction of more complete quantum computer systems and high-level programming. Correspondingly, each model is captured by a unique quantum resource. For instance, in the state family, the universal resource for the circuit model is coherence, for the local quantum Turing machine is bipartite entanglement, and for the cluster-state based, also known as measurement-based model is a specific type of entanglement relevant to symmetry-protected topological order. As program-storage is a central feature of the quantum von Neumann architecture, we find the quantum resources for it are quantum memories, which are dynamical resources closely related to entanglement. In other words, our classification of UQCMs also serves as a computational classification of quantum resources. This can be used to resolve the dispute over the computing power of resources, such as interference, entanglement, or contextuality. In all, we believe our theory lays down a solid framework to study computing models, resources, and design algorithms.
Quantum computing has been a fascinating research field in quantum physics. Recent progresses motivate us to study in depth the universal quantum computing models (UQCMs), which lie at the foundation of quantum computing and have tight connections with fundamental physics. Although being developed decades ago, a physically concise principle or picture to formalize and understand UQCM is still lacking. This is challenging given the diversity of still-emerging models, but important to understand the difference between classical and quantum computing. In this work, we carried out a primary attempt to unify UQCM by classifying a few of them as two categories, hence making a table of models. With such a table, some known models or schemes appear as hybridization or combination of models, and more importantly, it leads to new schemes that have not been explored yet. Our study of UQCM also leads to some insights into quantum algorithms. This work reveals the importance and feasibility of systematic study of computing models.
Abstract We develop universal quantum computing models that form a family of quantum von Neumann architectures, with modular units of memory, control, CPU, and internet, besides input and output. This family contains three generations characterized by dynamical quantum resource theory, and it also circumvents no-go theorems on quantum programming and control. Besides universality, such a family satisfies other desirable engineering requirements on system and algorithm design, such as modularity and programmability, hence serves as a unique approach to building universal quantum computers.
This chapter introduces quantum resource theories (QRTs), tracing their evolution and key principles, starting from physics’ quest to unify distinct phenomena into a single framework. It highlights the unification of electricity and magnetism as a pivotal advancement, setting a precedent for QRTs in quantum information science. Quantum resource theories categorize physical system attributes as “resources,” notably transforming the role of quantum entanglement from mere theoretical interest to a crucial element in quantum communication and computation. The chapter further describes the book’s layout and educational strategy, designed to offer a comprehensive understanding of QRTs. It explores the application of quantum resources in fields like quantum computing and thermodynamics, presenting a unique viewpoint on subjects such as entropy and nonlocality. Emphasizing on axiomatic beginning followed by practical uses, the book serves as a vital resource for both beginners and experts in quantum information science, preparing readers to navigate the complex terrain of QRTs and highlighting their potential to advance quantum science and technology.
A quantum computer is similar to an ordinary computer, except that instead of bits it uses two-level quantum systems (qubits), and the usual logical operations on bits are replaced with noiseless quantum dynamics in the form of unitary gates or Hamiltonian interactions. Many sets of resources that are universal for quantum computation (that is, capable of implementing any quantum computation) have been found, but general conditions for universality are still only partially understood. Improving our understanding of these conditions contributes to two broad goals. On the one hand, understanding what class of physical systems is suitable for quantum computation allows us choose the systems that are most easily controlled or built in the laboratory. On the other hand, identifying the unifying characteristics of such a class provides insight into the fundamental physics responsible for the much greater computational power of quantum computers. The original results presented in this thesis are a contribution to our understanding of the physical requirements for universal quantum computation. These results lead to the identification of a new, large class of universal dynamics. More specifically, the main problem that is addressed is the following: consider a physical system that is made up of a finite number of qubits that are subject to a natural, fixed interaction described by a two-body Hamiltonian. Suppose we have the ability to control the system only by applying fast one-qubit operations. Under what conditions is this system capable of universal quantum computation? The first original result of the thesis is to prove that universal quantum computation is possible under these conditions given the single extra constraint that the Hamiltonian must entangle, or connect, all of the qubits. In other words, since a two-body Hamiltonian is expressible as a sum of coupling terms each of which acts nontrivially on a pair of qubits, consider the graph whose vertices correspond to qubits and whose edges connect qubits that are coupled by a term in the Hamiltonian. Then this Hamiltonian, together with fast one-qubit unitaries, is universal for quantum computation precisely when the corresponding graph is connected. This result suggests many potential generalizations, three of which are explored in this thesis. The first generalization is to show that the same result holds for a two-body Hamiltonian that acts on D-dimensional quantum systems (qudits), given fast one-qudit unitaries. A second extension is to the case of a many-body Hamiltonian, that is, a Hamiltonian that has coupling terms that act on more than two qubits. Again, we find that under mild restrictions, such Hamiltonians are universal provided they are connected and that arbitrary one-qubit unitaries are available. We also discover and explore some surprising structure in many-body Hamiltonians that is associated with the parity of the couplings. A third related problem that is addressed is the question of what two-qubit unitaries are universal for quantum computation. This problem was originally solved by J.-L. and R. Brylinski [BB02], who gave a technical proof of the universality of any two-qudit gate that is not the swap gate or a product of one-qudit unitaries, given one-qudit unitaries as a free resource. We develop an elementary and constructive proof for the case of qubits, and prove that our construction is very close to optimal in the number of uses of the two-qubit gate. Given a qualitative understanding of what dynamical resources are universal for quantum computation, it is natural to consider developing a quantitative measure of the usefulness of quantum dynamics for quantum information processing. This is done in the final chapter of the thesis, in which the beginnings of a quantitative theory of quantum dynamics are developed.
In this paper, we build a framework allowing for a systematic investigation of the fundamental issue: ' Which quantum states serve as universal resources for measurement-based (one-way) quantum computation? ' We start our study by re-examining what is exactly meant by 'universality' in quantum computation, and what the implications are for universal one-way quantum computation. Given the framework of a measurement-based quantum computer, where quantum information is processed by local operations only, we find that the most general universal one-way quantum computer is one which is capable of accepting arbitrary classical inputs and producing arbitrary quantum outputs—we refer to this property as CQ-universality. We then show that a systematic study of CQ-universality in one-way quantum computation is possible by identifying entanglement features that are required to be present in every universal resource. In particular, we find that a large class of entanglement measures must reach its supremum on every universal resource. These insights are used to identify several families of states as being not universal, such as one-dimensional (1D) cluster states, Greenberger–Horne–Zeilinger (GHZ) states, W states, and ground states of non-critical 1D spin systems. Our criteria are strengthened by considering the efficiency of a quantum computation, and we find that entanglement measures must obey a certain scaling law with the system size for all efficient universal resources. This again leads to examples of non-universal resources, such as, e.g. ground states of critical 1D spin systems. On the other hand, we provide several examples of efficient universal resources, namely graph states corresponding to hexagonal, triangular and Kagome lattices. Finally, we consider the more general notion of encoded CQ-universality, where quantum outputs are allowed to be produced in an encoded form. Again we provide entanglement-based criteria for encoded universality. Moreover, we present a general procedure to construct encoded universal resources.