Advances in Optimization and Decision Science for Society, Services and Enterprises by Massimo Paolucci & Anna Sciomachen & Pierpaolo Uberti

Author:Massimo Paolucci & Anna Sciomachen & Pierpaolo Uberti
Language: eng
Format: epub
ISBN: 9783030349608
Publisher: Springer International Publishing

2 Background and Problem Definition

The basic difference between classical and quantum computing paradigm is in the computing unit, i.e., the bit and the quantum bit (qubit), respectively. A bit can exist in one of two states 0 or 1, instead, a qubit can exist in multiple states that can be expressed as a linear combination (superposition) of them. In other words, a qubit is a mathematical object representing a two level quantum system described by a two dimensional complex Hilbert space, where the two orthogonal quantum states, (ground state) and (excited state), are used to represent the Boolean values 0 and 1. Using the bra-ket notation |⋅〉, introduced by Dirac, any state of a qubit may be written as |ψ〉 = α|0〉 + β|1〉, where α and β, referred to as amplitudes, are complex numbers such that |α|2 + |β|2 = 1. The peculiarity of the superposition is in the measurement phase, since it returns the value |0〉 and |1〉 with probability |α|2 and |β|2, respectively. Two qubits can interact in complex ways due to the superposition and the entanglement, i.e., the physical phenomenon occurring when pairs or groups of particles interact in ways such that the state of each particle cannot be described independently of the state of the others.

Quantum computing relies on manipulating qubits by performing the so called quantum gates, mathematically expressed as unitary operations. Hence, in other words, an n-qubit quantum gate performs a specific 2n × 2n unitary operation on n qubits implementing the tensor product of related matrices. Details on these gates and matrices are not relevant in the remainder of this work, but can be found in [14].

A quantum algorithm is described by a quantum circuit, i.e., a set of quantum gates applied in sequence to transform the initial state of the quantum system into a final state. Each gate can involve an arbitrary number of qubits. The resulting circuit is then compiled into another equivalent quantum circuit based on a library of primitive one- and two-qubit gates [12]. A two-qubit gate is identified by a couple of qubits, referred to as control and target qubit, respectively. Hence, it implicitly defines a direction of the operation from the first qubit to the second. This equivalent quantum circuit is the input to our problem. Moreover a quantum circuit can be decomposed in a series of layers, where each layer includes a set of quantum gates such that any two pair of gates in the same level do not operate on any common qubit. Hence all the gates of a layer can be executed in parallel.

Given a quantum algorithm with only primitive gates, one should map the related quantum circuit into a quantum apparatus, i.e., a physical implementation (architecture) of the experiment realizing the circuit. The quantum circuit can be modelled by graph, referred to as interaction graph (IG), where nodes denote qubits of the circuit and arcs the two-qubit gates to be implemented. The architecture of a quantum computing system can be described by graph as well, referred to as connectivity graph (CG), where nodes represent qubits and arcs represent adjacent qubit pairs where gates can be implemented on.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.