Quantum computing can solve problems that are difficult to solve in classical computing, expanding the range of problems that can be effectively computed within the allowable range of classical physical principles, and posing a challenge to the extended Church-Turing thesis in classical computing. Here, we discuss an interesting question: how to achieve more powerful computers by breaking through the limitations of physical principles, further enhancing the capabilities of quantum computers. To extend quantum computing, novel operations related to relativistic physics are a crucial candidate. Among them, the concept of closed time-like curve has aroused widespread interest, and it introduces the ability for time travel. Mathematically, quantum state along the closed time-like curve is determined through self-consistent equations, which has been demonstrated in simulations. Here, we consider a novel manipulation capability that allows quantum computing to achieve time-travelling quantum control gate. This is an intuitive extension of the graphical language of quantum circuits. Explaining quantum circuits as tensor networks, we first explain how to experimentally simulate the output of such a circuit in a system without time-travel capability. Then, we take an example to demonstrate an extended quantum algorithm that can efficiently solve SAT problems, indicating that with the involvement of time-travelling quantum gates, the computational complexity class P = NP. We also anticipate that the time-travelling quantum gates will play a facilitating role in accomplishing other quantum tasks, including achieving deterministic non-orthogonal quantum state discrimination, and quantum state cloning. Our results contribute to a more in-depth understanding of the relationship between computation and physical principles.
Quantum computing can solve problems that are difficult to solve in classical computing, expanding the range of problems that can be effectively computed within the allowable range of classical physical principles, and posing a challenge to the extended Church-Turing thesis in classical computing. Here, we discuss an interesting question: how to achieve more powerful computers by breaking through the limitations of physical principles, further enhancing the capabilities of quantum computers. To extend quantum computing, novel operations related to relativistic physics are a crucial candidate. Among them, the concept of closed time-like curve has aroused widespread interest, and it introduces the ability for time travel. Mathematically, quantum state along the closed time-like curve is determined through self-consistent equations, which has been demonstrated in simulations. Here, we consider a novel manipulation capability that allows quantum computing to achieve time-travelling quantum control gate. This is an intuitive extension of the graphical language of quantum circuits. Explaining quantum circuits as tensor networks, we first explain how to experimentally simulate the output of such a circuit in a system without time-travel capability. Then, we take an example to demonstrate an extended quantum algorithm that can efficiently solve SAT problems, indicating that with the involvement of time-travelling quantum gates, the computational complexity class P = NP. We also anticipate that the time-travelling quantum gates will play a facilitating role in accomplishing other quantum tasks, including achieving deterministic non-orthogonal quantum state discrimination, and quantum state cloning. Our results contribute to a more in-depth understanding of the relationship between computation and physical principles.
Abstract According to the Church-Turing Thesis, a Turing machine, and thus the programming languages and computers in existence, can simulate any reasonable computing device. However, there are physical devices that are exponentially more efficient than a Turing machine, and hence would prove exponentially difficult to simulate using such a machine. This chapter explores the concept of quantum computers and their potential not only to simulate quantum physics exponentially faster than classical computers but also to solve other problems exponentially faster. It considers algorithms that break cryptosystems, find needles in haystacks, and predict who can win a game. It first describes particles, waves, and amplitudes in quantum computation before turning to states and operators. It then examines how interference lets a quantum computer learn some things about a function, how quantum computers can solve factoring in polynomial time, the link between factoring and modern cryptography, graph isomorphism and the hidden subgroup problem, and quantum walks and scattering.
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.
A possible approach to tackling computationally demanding issues beyond the capabilities of conventional algorithms is the use of quantum circuits, which provide a fundamental foundation for utilizing the power of quantum computation. This abstract examines how quantum circuits are implemented, emphasizing important topics such as circuit optimization, gate operations, and qubit manipulation. We explore different methods of encoding quantum information into topological qubits, trapped ions, and superconducting circuits, among other physical qubit formats. Furthermore, we go over the function of gate operations in quantum circuits, emphasizing crucial gates like phase, Hadamard, and CNOT gates, which serve as the foundation for quantum algorithms. Additionally, we look at methods for maximizing the efficiency and dependability of quantum processing by designing quantum circuits to minimize gate counts, depth, and error rates. To enhance the capabilities of quantum computing, this abstract presents a novel synthesis of quantum neural networks (QNNs) and quantum parameterized circuits. Through the use of parameterized quantum circuits' inherent flexibility, our approach makes it easier to design and optimize quantum circuits with flexible parameters, providing a flexible foundation for a variety of quantum algorithms. Using this amalgamation, we unleash the capacity of quantum computers to address intricate optimization and machine learning assignments with unparalleled effectiveness and expandability. Our solution bridges the gap between traditional machine learning approaches and quantum computing paradigms by enabling the smooth integration of classical data processing techniques with quantum computation. We use quantum states as data representations in our implementation of quantum neural networks, and we optimize trainable parameters to meet predetermined goals. This new paradigm opens up the investigation of the inherent features of quantum states and provides new perspectives on their processing power compared to their classical counterparts. We show, by thorough testing and analysis, how effective quantum parameterized circuits and QNNs are at solving practical problems in a variety of fields. Our work sets the ground for revolutionary breakthroughs in quantum information processing by pushing the boundaries of quantum computation and machine learning integration, offering hitherto unseen insights and solutions to challenging challenges in science, engineering, and beyond.
Quantum computing promises an exponential speedup improvement in the time required to solve certain computational problems by leveraging the principles of quantum mechanics.While the potential power of quantum computers is well-established, their practical implementation poses significant challenges ranging from scalability to decoherence and noise.This paper presents QPy, a Python-based quantum circuit simulator that I programmed and designed to track the quantum state of a model quantum computer through the application of quantum gates to qubits.By performing the requisite matrix calculations, the simulator facilitates the understanding of quantum algorithms through the visualization of the underlying mathematics.This tool enables researchers to explore and implement various quantum protocols efficiently to test and build algorithms.
Quantum mechanics has proven its position as the primary theory for accurately describing microscopic domains. Numerous fields in physics utilize quantum mechanics to great effects, with one prominent application being quantum computing. Quantum computing extends the field of quantum mechanics to information theory, striving to perform computational tasks utilizing quantum phenomena with notably greater efficiency compared to classical alternatives. In this thesis, I will go through the basics required in the field of quantum computing. To understand quantum computing demands adapting a new type of matrix mechanical view. This involves considering Hilbert spaces, which are linear vector space having a well defined inner product. Hilbert spaces contain state vectors describing quantum states, as well as operators for altering and measuring these states. The dynamics of quantum systems are governed by three quantum postulates. These specify Hilbert spaces and state vectors as the fundamental components of quantum systems, Hermitian operators as providing the physical manifestation of these systems, and finally, the Schrödinger's equation to describe the time evolution of such systems. These notions are required in producing quantum computing. Quantum computing uses qubits as the computational basis, analogous to classical bits but with the added capability of quantum superposition. Qubits are represented as two-state vectors, and can be physically realized with any quantum-behaving binary-valued system, like the electron spins. Qubits can be combined into higher dimensional states with the use of tensor products, causing the system's Hilbert space to expand as 2^n with n being the number of qubits, allowing for exponential computational speedup. Computational logic can be constructed by acting on the qubits using unitary operators, known as quantum gates. The combinations of qubits and quantum gates can be visualized as quantum circuits, depicted using specialized circuit diagram notations. An essential part of quantum computing, and the phenomena enabling exponential computational speedup, is quantum entanglement. Entanglement arises in interacting qubits, intertwining them so that the individual states become correlated. Entanglement can be characterized by being unable to reduce a combined state into its pure constituents. The amount of entanglement in a system can be measured using von Neumann entropy, analogous to Shannon entropy in classical information theory. Entanglement serves various purposes in quantum computing and is a defining feature distinguishing it from the classical domain. In this thesis, the entanglement properties of a periodic four-qubit circuit with alternating quantum gates were simulated. The simulation was performed computationally, and measured entanglement entropy as a function of the amount of circuit periods. The results demonstrated different characteristics of entanglement depending on the parameters used for the quantum gates, with the entanglement either being periodic, non-occurring or chaotic in nature.
The extent to which the possibilities and limits of computability depend on the assumed mathematical formalism is particularly evident in quantum computing. Here, methods, algorithms, and basic concepts of classical digital computing must be translated into the mathematical formalism of quantum mechanics and new concepts of quantum formalism must be utilized in order to overcome the classical limits of computability. In the sense of Church’s thesis, a classical digital computer can also be understood as a circuit of Boolean gates that process bits. In quantum computing, they are replaced by quantum gates that represent the unitary operators of quantum mechanics and process quantum bits. The enormous computing advantages are due to the special features of quantum mechanical states such as superposition and entanglement. The calculation results of a quantum computer are explained by the quantum mechanical measurement process. Classical calculation methods such as fast Fourier transformations are translated into quantum formalism and thus enable the solution of difficult calculation problems in polynomial time (e.g., factorization with the Shor algorithm). However, in this case, it cannot be ruled out that there is also a classical digital solution in polynomial time. This distinguishes the result from the fundamental impossibility of a digital solution, which was shown for real computing in Chapter 7. Classical pattern recognition and classification of machine learning (ML) with neural networks can also be translated into quantum formalism and lead to a considerable increase in performance with superposition and entanglement. In quantum complexity theory, previous NP problems can be traced back to P problems. In quantum computing too, the theoretical possibilities and limits depend on the mathematical formalism assumed. The technical– physical realization of a quantum computer, on the contrary, is again an empirical question.