Abstract Having spent almost an entire book on working out that Hopfield nets and adiabatic quantum computing are closely related concepts, this chapter departs from our main story line of problem solving as energy minimization and concludes our study with an outlook to the possibilities of quantum gate computing. Indeed, the central ideas behind quantum gate computing differ from most of what we studied so far but our study still has us prepared for getting to grips with the basics of this paradigm. As this paradigm posits that quantum algorithms are sequences of unitary operators which each act on the joint state of a qubit system, we will look at the circuit model of quantum computing and see that quantum circuits consist of quantum gates which are interconnected by quantum wires where the latter represent the states of qubits on which the former perform unitary operations. As a practical example, we discuss how such circuits could compute univariate Boolean functions. This then seamlessly allows us to finally study Deutsch’s problem and algorithm and therefore to see an instance of a computational problem for which quantum computing algorithms can be exponentially faster than their classical counterparts.
Abstract Having spent almost an entire book on working out that Hopfield nets and adiabatic quantum computing are closely related concepts, this chapter departs from our main story line of problem solving as energy minimization and concludes our study with an outlook to the possibilities of quantum gate computing. Indeed, the central ideas behind quantum gate computing differ from most of what we studied so far but our study still has us prepared for getting to grips with the basics of this paradigm. As this paradigm posits that quantum algorithms are sequences of unitary operators which each act on the joint state of a qubit system, we will look at the circuit model of quantum computing and see that quantum circuits consist of quantum gates which are interconnected by quantum wires where the latter represent the states of qubits on which the former perform unitary operations. As a practical example, we discuss how such circuits could compute univariate Boolean functions. This then seamlessly allows us to finally study Deutsch’s problem and algorithm and therefore to see an instance of a computational problem for which quantum computing algorithms can be exponentially faster than their classical counterparts.
We are now ready to see how computing with qubits can be done. In this book, we will mainly use the circuit model for computation which was first introduced by Deutsch [25]. We will represent by quantum “wires,” the qubits upon which manipulations. The length of the wire is to be interpreted as the time axis. Manipulations on qubits can be done using basic unitary operators that are the equivalents of logic “gates.” An algorithm, or a complete set of steps for achieving a processing task, is a combination of wires and gates representing a quantum circuit. This circuit must be thought of as a time sequence of events with every wire a way of representing qubit states, and with gates representing processing of those states.
Abstract In this chapter, we finally have our first look at quantum computing. In particular, we consider adiabatic quantum computing which is a paradigm tailored to the general problem of bipolar QUBO solving. Given our study up to this point, its basic principles will be easy to understand since Hopfield nets for problem solving and adiabatic quantum computing are closely related concepts. Indeed, we already know about tensor products, Hopfield energies and their representation in terms of Hamiltonians, annealing, the axioms of quantum mechanics, the Schrödinger equation, and quantum superposition. All these concepts will now be jointly put to use and brought together with yet another quantum mechanical principle, namely the adiabatic theorem. Based on two examples of simple QUBO problems, we demonstrate how adiabatic quantum computers can explore their exponentially large search spaces in parallel and thus achieve quadratic speedup over classical exhaustive search procedures.
This lecture continues Lectures One and Two, where we introduced the basic concepts of quantum computing and reviewed the essential linear algebra background for undergraduate students. In this lecture, we focus on the basic computational units of quantum computation, known as quantum gates. Quantum gates play a central role in quantum algorithms, as each quantum algorithm can be implemented as a sequence of quantum gate operations. This idea has a close analogy with classical computing, where computations can be represented by Boolean circuits constructed from elementary logic gates. In principle, classical algorithms can be implemented through combinations of such logic gates. To establish this connection, we first review several fundamental logic gates in classical computing, including the AND, OR, and NOT gates. These elementary Boolean gates provide a useful foundation for understanding quantum gates and how classical computational concepts are extended into the quantum domain. In general, a quantum processing unit (QPU), which executes quantum gate operations, can be viewed as the quantum counterpart of a classical central processing unit (CPU), where computations are carried out through logical operations and circuits. This lecture establishes the foundation for understanding the quantum circuit model and for designing and analyzing quantum algorithms in subsequent lectures. To provide a smooth transition to the topics that follow, we also introduce several tiny quantum algorithms and examples in this lecture. These examples illustrate how quantum gates can be combined to perform meaningful computational tasks and prepare students for the more advanced quantum algorithms discussed later.
In Section 1.3, we introduced the circuit model of (classical) computation. We restricted attention to reversible circuits since they can simulate any non-reversible circuit with modest overhead. This model can be generalized to a model of quantum circuits. In the quantum circuit model, we have logical qubits carried along ‘wires’, and quantum gates that act on the qubits. A quantum gate acting on n qubits has the input qubits carried to it by n wires, and n other wires carry the output qubits away from the gate. A quantum circuit is often illustrated schematically by a circuit diagram as shown in Figure 4.1. The wires are shown as horizontal lines, and we imagine the qubits propagating along the wires from left to right in time. The gates are shown as rectangular blocks. For convenience, we will restrict attention to unitary quantum gates (which are also reversible). Recall from Section 3.5.3 that non-unitary (non-reversible) quantum operations can be simulated by unitary (reversible) quantum gates if we allow the possibility of adding an ancilla and of discarding some output qubits. A circuit diagram describing a superoperator being implemented using a unitary operator is illustrated in Figure 4.2. In the example of Figure 4.1, the 4-qubit state |ψi⟩= |0⟩⊗ |0⟩⊗ |0⟩⊗ |0⟩ enters the circuit at the left (recall we often write this state as |ψi⟩ = |0⟩|0⟩|0⟩|0⟩ or |ψi⟩ = |0000⟩.) These qubits are processed by the gates U1, U2, U3, and U4. At the output of the circuit we have the collective (possibly entangled) 4-qubit state |ψf⟩. A measurement is then made of the resulting state. The measurement will often be a simple qubit-by-qubit measurement in the computational basis, but in some cases may be a more general measurement of the joint state. A measurement of a single qubit in the computational basis is denoted on a circuit diagram by a small triangle, as shown in Figure 4.1 (there are other symbols used in the literature, but we adopt this one). The triangle symbol will be modified for cases in which there is a need to indicate different types of measurements.R50
Summary form only given, as follows. Gives a system theoretic approach to the concept of quantum computing. A quantum computer is envisaged to be a system of quantum circuits, acting on a state space, which is a finite-say 2/sup n/-dimensional-complex Hilbert space. The circuitry is a sequence of unitary transforms U/sub t/ /spl epsiv/ SU(2/sup n/) followed by a measurement. These transforms, so-called quantum gates, are controlled by a classical computer, usually especially electromagnetic fields. The state space of a quantum computer has the structure of a Hermitian vector space. Thus it allows "simultaneous" superposition of orthogonal basis states (corresponding to classical states) with the possibility of constructive and destructive interference between different paths of computation. This principle allows the usage of so-called entangled states by preparing the superposition of special "bent" configurations of basis vectors in the product Hilbert space, e.g., as they are known from error control and cryptography. This latter "entanglement" not only promises to make a quantum computer much more powerful than a probabilistic one, but it also allows a method of parallelism. The reason for this lies not only in the fact that the 2/sup n/ dimensional Hilbert space is the n-fold tensor product of 2-dimensional spaces as it is given by spin-1/2-particles, like photons, representing a quantum bit. First of all, we shall address the fact that the power of quantum computing lies in the properties of entangled states as opposed to those of separable states which essentially would resemble classical circuits without giving the feature of exponential speed-up. We shall briefly describe possible physical realisations of quantum (optic, electronic, magnetic,...) devices allowing the engineering of Hamiltonians needed for quantum systems. Basic quantum gates, especially the quantum Horner-Toffoli gate will be discussed to display the principles and methodology for designing quantum circuits. An outlook towards the possible availability of nano- and mesoscopic technologies supporting this new architecture in future generations concludes based on a speculative worst/best case forecast of possible applications, e.g., in public key and conventional cryptography.
Abstract In this chapter, we shift our perspective from seeing the unitary evolution of a quantum state as a physical process that ‘just happens’ to instead seeing it as an executable operation in a programmable computer. To do this, we introduce the quantum circuit (or gate) model, which subsequently allows us to present and analyse quantum algorithms and quantum communication protocols. The universality of quantum computing – that every quantum mechanical system (composed of qubits) can be represented as such – is established, as is the closely related notion of universal gatesets. The chapter also briefly introduces some important topics in quantum compilation, in which some quantum circuit is rewritten as a functionally equivalent alternative that is more suitable (in some sense) for running on a particular quantum computer.