After decades of unhindered progress, classical computing has started facing significant hurdles both in terms of physical scalability and theoretical bounds of efficiency. Among the alternative models of computing, Quantum Computing, though proposed six decades ago, has recently started seeing potentials to progress beyond the limits of classical computing. This book discusses the theoretical bounds on the efficiency of low depth quantum circuits, one of the structurally simplest models of quantum computing. Three different properties are explored; universality in which one circuit can be used to simulate different circuits, fault detection in which certain kinds of faults in simple quantum gates can be detected and third, a fundamental theoretical limitation in the power of a popular quantum gate. These properties give us a better idea about simple quantum circuits, which are essentially building blocks for more complicated gadgets. The properties are analysed using novel techniques which will be useful to analyse other similar quantum circuits. Overall, this book will be useful to researchers of quantum circuit complexity and graduate students of theoretical computer science.
After decades of unhindered progress, classical computing has started facing significant hurdles both in terms of physical scalability and theoretical bounds of efficiency. Among the alternative models of computing, Quantum Computing, though proposed six decades ago, has recently started seeing potentials to progress beyond the limits of classical computing. This book discusses the theoretical bounds on the efficiency of low depth quantum circuits, one of the structurally simplest models of quantum computing. Three different properties are explored; universality in which one circuit can be used to simulate different circuits, fault detection in which certain kinds of faults in simple quantum gates can be detected and third, a fundamental theoretical limitation in the power of a popular quantum gate. These properties give us a better idea about simple quantum circuits, which are essentially building blocks for more complicated gadgets. The properties are analysed using novel techniques which will be useful to analyse other similar quantum circuits. Overall, this book will be useful to researchers of quantum circuit complexity and graduate students of theoretical computer science.
Quantum computation was proposed as an alternate computing process in the late-20th century, when classical computing models faced limitation in solving quantum mechanical problems. Major breakthroughs came in the 1990s, when quantum algorithms for integer factoring and black-box searching were invented that are faster than the best classical algorithms known even today. In this thesis, we look at quantum circuits with limited depth and size and analyse their power and limitations.
Computer Science is about the study of computational problems, many of which are motivated by real-world applications. We are interested as much in an actual method to solve a problem as in its unsolvability. In computational complexity theory we separate out the actual problem from the computing apparatus (e.g. a Turing machine, an AND-OR circuit) and analyse the hardness of the computation, due both to the intrinsic complexity of the problem and to the underlying model.
In this thesis, we consider quantum circuits built with a universal set of gates and show that non-constant depth is required to compute a particular function (parity) and other similar functions. The parity function, extensively studied previously, was shown to take non-constant depth for classical circuits too, thus providing an evidence of an inherent hardness in the function itself. On the other hand we show that the quantum circuit model is rich enough to build a universal circuit (one circuit that can simulate all circuits) that has roughly the same depth or size as the simulated circuit. We also consider a fault model in which some of the inputs to a gate might not be connected to the gate's output. We ask if we can detect the faulty inputs by testing the gate on different inputs. Our goal is to minimise the number of tests. We show that this is very hard for general gates but for certain gates it can be provably easier to detect faulty inputs. We even show that quantum algorithms can provably outperform classical algorithms for these gates. These results give us a sense of wherein lies the power of quantum computation and quantum circuits in particular.
This project focused on upper and lower bounds for quantum computability using constant depth quantum circuits, and on the complexity theory of such circuits. It established significant differences between resource bounded quantum and classical computation models, particularly emphasizing new examples of where quantum circuits are more powerful than their classical counterparts. A second focus and outgrowth of this work was the creation of efficient quantum algorithms for specific problems and central combinatorial functions. Recent finding include upper bounds for the computational power of constant depth circuits composed of single qubit and CNOT gates, and lower bounds for the computational power of constant depth circuits with single qubit, CNOT and fanout gates. These results represent the power and the limits of small, possibly realizable quantum circuits. Also examined were bounds on computations with additional storage qubits (ancillae), and natural simple functions (realized by small depth circuits) which require ancillae for their computation.
The quantum circuit model is the most widely used model of quantum computation. It provides both a framework for formulating quantum algorithms and an architecture for the physical construction of quantum computers. However, several other models of quantum computation exist which provide useful alternative frameworks for both discovering new quantum algorithms and devising new physical implementations of quantum computers. In this thesis, I first present necessary background material for a general physics audience and discuss existing models of quantum computation. Then, I present three results relating to various models of quantum computation: a scheme for improving the intrinsic fault tolerance of adiabatic quantum computers using quantum error detecting codes, a proof that a certain problem of estimating Jones polynomials is complete for the one clean qubit complexity class, and a generalization of perturbative gadgets which allows k-body interactions to be directly simulated using 2-body interactions. Lastly, I discuss general principles regarding quantum computation that I learned in the course of my research, and using these principles I propose directions for future research.
Quantum Computing The twenty-first century has witnessed remarkable advancements in computing technologies, transforming every aspect of modern society. As conventional computing systems approach their physical and computational limits, the search for new paradigms capable of solving increasingly complex problems has led to the emergence of Quantum Computing. By harnessing the principles of quantum mechanics, quantum computing represents a revolutionary approach that has the potential to redefine computation, communication, and information processing on an unprecedented scale. Quantum Computing is designed to provide readers with a comprehensive understanding of the concepts, principles, technologies, and applications that form the foundation of this rapidly evolving field. This book aims to bridge the gap between theoretical quantum mechanics and practical computational applications, enabling students, researchers, academicians, and professionals to explore the transformative potential of quantum technologies. The chapters in this book cover a broad spectrum of topics, including the fundamentals of quantum mechanics, quantum bits (qubits), quantum gates, superposition, entanglement, quantum circuits, quantum algorithms, quantum cryptography, quantum communication, and quantum error correction. The book also explores the architecture of quantum computers and examines the challenges involved in building scalable and fault-tolerant quantum systems. As industries increasingly seek innovative solutions to complex computational problems, quantum computing is emerging as a promising technology with applications in cryptography, artificial intelligence, machine learning, optimization, financial modeling, healthcare, pharmaceutical research, materials science, logistics, and climate modeling. The ability of quantum computers to process vast amounts of information simultaneously offers opportunities that were previously beyond the reach of classical computing systems. Special attention has been given to contemporary developments in quantum technologies, including quantum supremacy, hybrid quantum-classical computing, cloud-based quantum platforms, and the growing role of quantum computing in scientific discovery and industrial innovation. The book also discusses ethical, security, and societal implications associated with the advancement of quantum technologies. The primary objective of this book is to equip readers with both foundational knowledge and practical insights into the field of quantum computing. Through a balanced presentation of theory, applications, case studies, and emerging research trends, the book seeks to inspire curiosity, innovation, and further exploration in this transformative domain. We extend our sincere gratitude to the authors, reviewers, researchers, academicians, and industry experts whose valuable contributions have enriched the quality and relevance of this publication. Their dedication and expertise have helped create a resource that reflects the latest developments and future possibilities of quantum computing. We hope that Quantum Computing will serve as a valuable guide for students, educators, researchers, and technology professionals seeking to understand the next frontier of computational science. May this book inspire new ideas, foster innovation, and contribute to the advancement of knowledge in one of the most exciting technological revolutions of our time. Mr. M. Rajeshkumar Dr. R. Mariappan Mr. E.Janakiraman,
Quantum computing is an emerging technology that has the potential to change the perspectives and applications of computing in general. A wide range of applications are enabled: from faster algorithmic solutions of classically still difficult problems to theoretically more secure communication protocols. A quantum computer uses the quantum mechanical effects of particles or particle-like systems, and a major similarity between quantum and classical computers consists of both being abstracted as information processing machines. Whereas a classical computer operates on classical digital information, the quantum computer processes quantum information, which shares similarities with analog signals. One of the central differences between the two types of information is that classical information is more fault-tolerant when compared to its quantum counterpart. Faults are the result of the quantum systems being interfered by external noise, but during the last decades quantum error correction codes (QECC) were proposed as methods to reduce the effect of noise. Reliable quantum circuits are the result of designing circuits that operate directly on encoded quantum information, but the circuit’s reliability is also increased by supplemental redundancies, such as sub-circuit repetitions. Reliable quantum circuits have not been widely used, and one of the major obstacles is their vast associated resource overhead, but recent quantum computing architectures show promising scalabilities. Consequently the number of particles used for computing can be more easily increased, and that the classical control hardware (inherent for quantum computation) is also more reliable. Reliable quantum circuits haev been investigated for almost as long as general quantum computing, but their limited adoption (until recently) has not generated enough interest into their systematic design. The continuously increasing practical relevance of reliability motivates the present thesis to investigate some of the first answers to questions related to the background and the methods forming a reliable quantum circuit design stack. The specifics of quantum circuits are analysed from two perspectives: their probabilistic behaviour and their topological properties when a particular class of QECCs are used. The quantum phenomena, such as entanglement and superposition, are the computational resources used for designing quantum circuits. The discrete nature of classical information is missing for quantum information. An arbitrary quantum system can be in an infinite number of states, which are linear combinations of an exponential number of basis states. Any nontrivial linear combination of more than one basis states is called a state superposition. The effect of superpositions becomes evident when the state of the system is inferred (measured), as measurements are probabilistic with respect to their output: a nontrivial state superposition will collapse to one of the component basis states, and the measurement result is known exactly only after the measurement. A quantum system is, in general, composed from identical subsystems, meaning that a quantum computer (the complete system) operates on multiple similar particles (subsystems). Entanglement expresses the impossibility of separating the state of the subsystems from the state of the complete system: the nontrivial interactions between the subsystems result into a single indivisible state. Entanglement is an additional source of probabilistic behaviour: by measuring the state of a subsystem, the states of the unmeasured subsystems will probabilistically collapse to states from a well defined set of possible states. Superposition and entanglement are the building blocks of quantum information teleportation protocols, which in turn are used in state-of-the-art fault-tolerant quantum computing architectures. Information teleportation implies that the state of a subsystem is moved to a second subsystem without copying any information during the process. The probabilistic approach towards the design of quantum circuits is initiated by the extension of classical test and diagnosis methods. Quantum circuits are modelled similarly to classical circuits by defining gate-lists, and missing quantum gates are modelled by the single missing gate fault. The probabilistic approaches towards quantum circuits are facilitated by comparing these to stochastic circuits, which are a particular type of classical digital circuits. Stochastic circuits can be considered an emulation of analogue computing using digital components. A first proposed design method, based on the direct comparison, is the simulation of quantum circuits using stochastic circuits by mapping each quantum gate to a stochastic computing sub-circuit. The resulting stochastic circuit is compiled and simulated on FPGAs. The obtained results are encouraging and illustrate the capabilities of the proposed simulation technique. However, the exponential number of possible quantum basis states was translated into an exponential number of stochastic computing elements. A second contribution of the thesis is the proposal of test and diagnosis methods for both stochastic and quantum circuits. Existing verification (tomographic) methods of quantum circuits were targeting the reconstruction of the gate-lists. The repeated execution of the quantum circuit was followed by different but specific measurement at the circuit outputs. The similarities between stochastic and quantum circuits motivated the proposal of test and diagnosis methods that use a restricted set of measurement types, which minimise the number of circuit executions. The obtained simulation results show that the proposed validation methods improve the feasibility of quantum circuit tomography for small and medium size circuits. A third contribution of the thesis is the algorithmic formalisation of a problem encountered in teleportation-based quantum computing architectures. The teleportation results are probabilistic and require corrections represented as quantum gates from a particular set. However, there are known commutation properties of these gates with the gates used in the circuit. The corrections are not applied as dynamic gate insertions (during the circuit’s execution) into the gate-lists, but their effect is tracked through the circuit, and the corrections are applied only at circuit outputs. The simulation results show that the algorithmic solution is applicable for very large quantum circuits. Topological quantum computing (TQC) is based on a class of fault-tolerant quantum circuits that use the surface code as the underlying QECC. Quantum information is encoded in lattice-like structures and error protection is enabled by the topological properties of the lattice. The 3D structure of the lattice allows TQC computations to be visualised similarly to knot diagrams. Logical information is abstracted as strands and strand interactions (braids) represent logical quantum gates. Therefore, TQC circuits are abstracted using a geometrical description, which allows circuit input-output transformations (correlations) to be represented as geometric sub-structures. TQC design methods were not investigated prior to this work, and the thesis introduces the topological computational model by first analysing the necessary concepts. The proposed TQC design stack follows a top-down approach: an arbitrary quantum circuit is decomposed into the TQC supported gate set; the resulting circuit is mapped to a lattice of appropriate dimensions; relevant resulting topological properties are extracted and expressed using graphs and Boolean formulas. Both circuit representations are novel and applicable to TQC circuit synthesis and validation. Moreover, the Boolean formalism is broadened into a formal mechanism for proving circuit correctness. The thesis introduces TQC circuit synthesis, which is based on a novel logical gate geometric description, whose formal correctness is demonstrated. Two synthesis methods are designed, and both use a general planar representation of the circuit. Initial simulation results demonstrate the practicality and performance of the methods. An additional group of proposed design methods solves the problem of automatic correlation construction. The methods use validity criteria which were introduced and analysed beforehand in the thesis. Input-output correlations existing in the circuit are inferred using both the graph and the Boolean representation. The thesis extends the TQC state-of-the-art by recognising the importance of correlations in the validation process: correlation construction is used as a sub-routine for TQC circuit validation. The presented cross-layer validation procedure is useful when investigating both the QECC and the circuit, while a second proposed method is QECC-independent. Both methods are scalable and applicable even to very large circuits. The thesis completes with the analysis of TQC circuit identities, where the developed Boolean formalism is used. The proofs of former known circuit identities were either missing or complex, and the presented approach reduces the length of the proofs and represents a first step towards standardising them. A new identity is developed and detailed during the process of illustrating the known circuit identities. Reliable quantum circuits are a necessity for quantum computing to become reality, and specialised design methods are required to support the quest for scalable quantum computers. This thesis used a twofold approach towards this target: firstly by focusing on the probabilistic behaviour of quantum circuits, and secondly by considering the requirements of a promising quantum computing architecture, namely TQC. Both approaches resulted in a set of design methods enabling the investigation of reliable quantum circuits. The thesis contributes with the proposal of a new quantum simulation technique, no
Quantum computing has emerged as one of the most transformative technological developments of the twenty-first century. By exploiting the fundamental principles of quantum mechanics—namely superposition, entanglement, and measurement—quantum computers offer the potential to address problems that are beyond the practical reach of classical computing systems. As the field advances from theoretical exploration to real-world implementation, the demand for clear, structured, and comprehensive educational resources continues to grow. This book presents a systematic and accessible introduction to quantum computing, beginning with the essential concepts of classical information and computation and progressively advancing toward modern quantum algorithms and communication protocols. The initial chapters establish a strong foundation in classical bits, logic gates, Boolean algebra, reversible logic, and computational complexity, providing the conceptual bridge necessary to understand quantum computation. The discussion then moves to the quantum bit (qubit), examining its behavior through superposition, measurement, Bloch sphere representation, and physical realization. Special emphasis is placed on linear algebra as the mathematical framework underpinning quantum computing. Through this approach, readers are guided to develop an intuitive yet rigorous understanding of quantum states, quantum gates, and circuit-based computation. The text further extends these ideas to multi-qubit systems, quantum entanglement, universal gate sets, and quantum error correction, integrating theoretical principles with practical insights. To support experiential learning, the book incorporates hands-on exposure to leading quantum programming platforms, including IBM Quantum, OpenQASM, and Qiskit. These sections connect theory with practice, enabling readers to design, simulate, and execute quantum circuits on both simulators and real quantum hardware. Subsequent chapters explore key quantum communication protocols such as superdense coding, quantum teleportation, and quantum key distribution, followed by an in-depth treatment of foundational quantum algorithms including Deutsch–Jozsa, Grover’s search, Simon’s algorithm, and Shor’s factoring algorithm. This text is intended for undergraduate and postgraduate students, research scholars, and industry professionals seeking a coherent and structured pathway into quantum computing. No prior knowledge of quantum mechanics is assumed, although familiarity with linear algebra and classical computation will enhance comprehension. Each chapter is carefully organized to promote conceptual clarity, supported by illustrative examples, circuit diagrams, and concise summaries. Beyond explaining the principles and mechanisms of quantum computation, this book aims to inspire readers to engage with the future of the field—whether through academic research, industrial application, or interdisciplinary innovation. As quantum technologies continue to evolve, it is hoped that this text will serve as a dependable guide and a meaningful entry point into the quantum era.