In this paper we raise questions about the reality of computational quantum parallelism. Such questions are important because while quantum theory is rigorously established, the hypothesis that it supports a more powerful model of computation remains speculative. More specifically, we suggest the possibility that the seeming computational parallelism offered by quantum superpositions is actually effected by gate-level parallelism in the reversible implementation of the quantum operator. In other words, when the total number of logic operations is analyzed, quantum computing may not be more powerful than classical. This fact has significant public policy implications with regard to the relative levels of effort that are appropriate for the development of quantumparallel algorithms and associated hardware (i.e., qubit-based) versus quantum-scale classical hardware.
In this paper we raise questions about the reality of computational quantum parallelism. Such questions are important because while quantum theory is rigorously established, the hypothesis that it supports a more powerful model of computation remains speculative. More specifically, we suggest the possibility that the seeming computational parallelism offered by quantum superpositions is actually effected by gate-level parallelism in the reversible implementation of the quantum operator. In other words, when the total number of logic operations is analyzed, quantum computing may not be more powerful than classical. This fact has significant public policy implications with regard to the relative levels of effort that are appropriate for the development of quantumparallel algorithms and associated hardware (i.e., qubit-based) versus quantum-scale classical hardware.
After some remarks on the fundamental physical nature of information, Bennett and Fredkin’s ideas reversible computation are introduced. This leads to the suggestions of Benioff and Feynman as to the possibility of a new type of essentially ‘quantum computer’. If we happen to build such devices, Deutsch scientists showed that‘quantum parallelism’ leads to new algorithms and new complexity classes. This is dramatically illustrated by Shor's quantum algorithm for factorization which is polynomial in time in contrast to algorithms for factorization on a classical Turing computer. This discovery has potentially important implications for the security of many modern cryptographic systems. The fundamentals of quantum computing are then introduced - reversible logic gates, qubits and quantum registers. The key quantum property of ‘entanglement’ is described, with due homage to Einstein and Bell. As an illustration of a quantum program, Grover's database search algorithm is described in some detail. After all this theory, the status of experimental attempts to build a quantum computer is reviewed: it will become evident that we have a long way to go before we can factorize even small numbers. Finally, we end with some thoughts about the process of ‘quantum compilation’ - translating a quantum algorithm into actual physical operations on a quantum system - and some comments on prospects for future progress.
Quantum computing is based on the exploitation of quantum effects to perform some important computations more efficiently than ever possible on classical computers. Well known quantum algorithms are Shors polynomial time factoring algorithm and Grovers data base search scheme. Their potential is due to the parallelism of a quantum computation increasing exponentially with the size of the computing device. IBM has succeeded in building a first working quantum computing device with up to 7 qubits based on NMR technology, however, the construction of large multi-qubit systems appears to become extremely difficult due to the loss of coherence of the quantum states. Like the design process of modern microprocessors which is carried out by means of sophisticated software, modelling and simulation of the entire QC device is even more relevant. Simulation is required in order to understand the functioning of quantum algorithms, to construct novel quantum algorithms, to write quantum programs, to teach quantum computing, to construct real quantum computers, to understand and fight de-coherence and to understand and control the influence of the environment. Since quantum parallelism increases exponentially with the size of the quantum computer, parallel supercomputers are required for realistic simulations. I intend to give an introduction into the simulation of quantum computers using conventional computers. The simulation is based on a generic physical model of quantum computer hardware. Issues like parallel gate level simulators, modelling of QCs, simulators for physical quantum computers are addressed.
Quantum parallelism, a fundamental feature of quantum computing, enables the simultaneous evaluation of multiple inputs in a quantum superposition state. This paper explores the theoretical foundation, practical implementation challenges, and algorithmic implications of quantum parallelism. We examine how it empowers quantum algorithms such as the Deutsch-Jozsa and Grover's algorithms to achieve exponential speedups over classical counterparts. The paper concludes with a discussion on the current limitations and future potential of quantum parallelism in real-world quantum processors.
Is the universe computable? If yes, is it computationally a polynomial place? In standard quantum mechanics, which permits infinite parallelism and the infinitely precise specification of states, a negative answer to both questions is not ruled out. On the other hand, empirical evidence suggests that NP‐complete problems are intractable in the physical world. Likewise, computational problems known to be algorithmically uncomputable do not seem to be computable by any physical means. We suggest that this close correspondence between the efficiency and power of abstract algorithms on the one hand, and physical computers on the other, finds a natural explanation if the universe is assumed to be algorithmic; that is, that physical reality is the product of discrete sub‐physical information processing equivalent to the actions of a probabilistic Turing machine. This assumption can be reconciled with the observed exponentiality of quantum systems at microscopic scales, and the consequent possibility of implementing Shor’s quantum polynomial time algorithm at that scale, provided the degree of superposition is intrinsically, finitely upper‐bounded. If this bound is associated with the quantum‐classical divide (the Heisenberg cut), a natural resolution to the quantum measurement problem arises. From this viewpoint, macroscopic classicality is an evidence that the universe is in BPP, and both questions raised above receive affirmative answers. A recently proposed computational model of quantum measurement, which relates the Heisenberg cut to the discreteness of Hilbert space, is briefly discussed. A connection to quantum gravity is noted. Our results are compatible with the philosophy that mathematical truths are independent of the laws of physics.
Central to the power of quantum computing is the concept of quantum parallelism: quantum systems can explore and process multiple computational paths simultaneously. In this paper, we discuss the elusive nature of quantum parallelism, drawing parallels with classical parallel computing models to elucidate its fundamental characteristics and implications for algorithmic performance. We begin by defining quantum parallelism as arising from the superposition of quantum states, allowing for the exploration of multiple computational paths in parallel. To quantify and visualize quantum parallelism, we introduce the concept of quantum dataflow diagrams, which provide a graphical representation of quantum algorithms and their parallel execution paths. We demonstrate how quantum parallelism can be measured and assessed by analyzing quantum algorithms such as the Quantum Fourier Transform (QFT) and Amplitude Amplification (AA) iterations using quantum dataflow diagrams. Furthermore, we examine the interplay between quantum parallelism and classical parallelism laws, including Amdahl's and Gustafson's laws. While these laws were originally formulated for classical parallel computing systems, we reconsider their applicability in the quantum computing domain. We argue that while classical parallelism laws offer valuable insights, their direct application to quantum computing is limited due to the unique characteristics of quantum parallelism, including the role of destructive interference and the inherent limitations of classical-quantum I/O. Our analysis highlights the need for an increased understanding of quantum parallelism and its implications for algorithm design and performance.
Currently, the theory of quantum computing is actively developing. Despite the fact that a quantum computer has some features, any algorithm designed for a classical computer can be implemented for a quantum one. The relevance of the topic of quantum computers is confirmed by the fact that even now banking systems, cryptography and encryption of information require enormous resources of computing systems, these are just some examples, but the most important and vivid ones that relate to the everyday life of a huge part of the world's population. A hardware computing core has been developed and simulated, which is the main part of an accelerator based on field-programmable gate array with computer aided design Altera Quartus. Considering the obtained time dependence of the number of cycles required for the impact of a single-qubit quantum gate on a quantum register on the number of qubits and parallel arithmetic logic units in the hardware computing core, when simulating quantum computing, a method was developed to determine the increase in hardware performance and ways to improve the performance of an accelerator based on a hardware computing core were developed. based on field-programmable gate array.