Universal Quantum Computing

Junya Kasahara

Dongsheng Wang

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.

C. S. Vijay, Vishal Gupta

Dongsheng Wang

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.

Dongsheng Wang

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.

Juraj Šibík