Quantum Software

Quantum Software

Current progress in the field of quantum computer hardware makes it credible that, in just a few years, quantum computers will outperform classical ones. Many research groups and companies are working on the hardware, but the key questions of what a realistically-sized quantum computer can achieve, how to do this, and how to verify the results refer to quantum software. In this article, we stress the importance of quantum software and illustrate a few meaningful examples.


The importance of quantum software

A quantum computer is a device that harnesses the laws of quantum mechanics to solve certain tasks using fewer computational resources than classical computers. The fundamental information-carrying components of a quantum computer are the quantum bits (qubits). A qubit is a quantum-mechanical system (e.g., a particle) whose state can be the superposition of 0 and 1 at the same time.
At least as important as building quantum computers is the quest to establish which problems are prone to quantum speed-ups and to develop quantum algorithms that can achieve such speed-ups. Quantum software addresses the key questions of what a realistically-sized quantum computer can achieve, how to do this, and how to verify the results [QSManifesto]. The broad and multidisciplinary field of quantum software includes a wide range of topics, such as quantum algorithms and protocols, quantum information theory and verification of quantum devices.
In this article, we present our research activity on quantum software, encompassing the design and development of highly efficient quantum compilers, quantum algorithms and quantum protocols. Our code is usually released under an open source license and published on GitHub (https://github.com/qis-unipr).


Quantum Compiling

Current quantum computers are noisy intermediate-scale quantum (NISQ) devices [Preskill2018], characterized by a reduced number of qubits (5-50) with non-uniform quality and highly constrained connectivity. Such devices may be able to perform tasks which surpass the capabilities of today's most powerful classical digital computers, but noise in quantum gates limits the size of quantum circuits that can be executed reliably.
Quantum compilation, i.e., device-aware implementation of quantum algorithms, is a challenging problem. A good quantum compiler must translate an input quantum algorithm, defined as a quantum circuit, into the most efficient equivalent of itself, getting the most out of the available hardware. In general, the quantum compilation problem is NP-Hard [Botea2018]. On NISQ devices, quantum compilation is declined in the following tasks: gate synthesis, which is the decomposition of an arbitrary unitary operation into a sequence of gates from a discrete set; compliance with the hardware architecture; and noise awareness. Quality indicators of the compiled quantum algorithm are, for example, circuit depth, gate count and fidelity of quantum states.
Recently, some noteworthy quantum compiling techniques have been proposed. For example, Zulehner et al. [Zulehner2019] proposed a strategy based on the A* search algorithm [Hart1968] for mapping the logical qubits (of the quantum circuit) to the physical qubits (of the device). The proposed approach is efficient in terms of running time and output depth, but may not be scalable because of the exponential space complexity of A*. SABRE by Li et al. [Li2019] is apparently more efficient, but its code has not been released.
In general, most compiling approaches have two common features: 1) they rely on randomized algorithms and 2) they are general purpose, but they are not able to make assumptions on circuit structure or characteristics. These kind of solutions, although effective in many cases, are not as much efficient when facing circuits characterized by well-defined peculiar sequences, i.e., patterns, of two-qubit operators. This is particularly true if those patterns repeat themselves many times in a circuit and are not compliant with the quantum device connectivity.
In a research work with Davide Ferrari [Ferrari2018], we started the investigation of deterministic algorithms for compiling recurrent quantum circuit patterns. The proposed strategy focused on quantum circuits for generating Greenberger–Horne–Zeilinger (GHZ) entangled states. It is well known that GHZ states have several practical applications, including quantum machine learning. We integrated the resulting compiler with Qiskit, IBM’s open source software development kit for working with OpenQASM and the IBM Q quantum processors.
Later, with Davide Ferrari and Ivano Tavernelli [Ferrari2019], we developed ChainSwap, a software tool implementing new deterministic algorithms that cope with a larger set of quantum circuit patterns. In particular, such patterns appear in quantum circuits that are used to compute the ground state properties of molecular systems using the VQE algorithm together with a wavefunction Ansätz like the Coupled-Cluster expansion. Some experimental results are illustrated in Table 1, where ChainSwap is compared to IBM Qiskit’s Basic, Stochastic and Lookahead compilers. Ideally, the depth of the compiled circuit should be less or equal to the depth of the input circuit. In practice, this is quite unlikely. ChainSwap produces circuits whose depth is generally very good, and in some cases is ideal.


Table 1 – Depth of different quantum circuits compiled with ChainSwap and IBM Qiskit’s compilers.

Enhancing distributed functional monitoring with quantum protocols

Scalability concerns are motivating distributed quantum computing architectures, and experimental efforts have demonstrated some of the building blocks for such a design [VanMeter2016]. With the network and communications functionalities provided by the Quantum Internet [Wehner2018], remote quantum processing units can communicate and cooperate for executing computational tasks that each NISQ device cannot handle by itself. The main idea of the Quantum Internet is to enable quantum communication between any two points on Earth, in synergy with the “classical” Internet, in order to achieve unmatched capabilities, as well as levels of resiliency and trustworthiness that are impossible by using only classical information. Over long distances, the primary method of operating the Quantum Internet is to leverage optical networks (re-using existing optical fiber) and photon-based qubits.
In a joint work with Mattia Pizzoni and Stefano Carretta [Amoretti2019], we proposed the quantum geometric monitoring (QGM) protocol to solve threshold monitoring problems, where N players are located at different sites, each observing a stream of items and communicating with one coordinator, whose goal is to know when a function of the union of the streams exceeds a given threshold. QGM enhances the classical geometric monitoring (GM) protocol [Giatrakos2016] with quantum communication and entanglement.
An entangled state is a special state of a group of qubits, such that the state of each qubit cannot be described independently of the state of the others. For example, Bell states are maximally entangled states of two qubits. In QGM, Bell states are used to encode bit pairs and the supporting qubits are moved back and forth between the coordinator and the N players. The QGM protocol leverages the special properties of Bell states to reduce the communication cost, with respect to the GM protocol.
Generally speaking, the QGM protocol defines two roles: Parent and Child (Figure 1). Then, there are two specializations of QGM, namely QGM-Flat, where the coordinator interacts with all the N players, and QGM-Tree, where the N players assume a tree structure (Figure 2). In QGM-flat, the coordinator is the Parent and the N players are its Children. In QGM-Tree, the N players are both Children and Parents (with the exception of those corresponding to the leaves of the tree, which are just Children).


Figure 1 – QGM protocol: state machines of parent and child nodes.


Figure 2 – Examples of QGM system configurations for solving the threshold monitoring problem.

We implemented the QGM protocol with SimulaQron [Dahlberg2019], a Python library for the development and simulation of quantum networking applications. Simulation results confirmed that the average communication cost in QGM-based systems is lower than in GM-based ones, with the same error rate.


Entanglement verification in quantum networks with tampered nodes

In general, entanglement is a precious resource in quantum networks. Entangled states exhibit correlations that have no classical analog and may be used, e.g., to solve leader election problems, to perform distributed computing tasks, to share secrets, or to perform remote synchronization of clocks.
Recently, in a joint work with Stefano Carretta [Amoretti2020], we proposed two protocols for entanglement verification across the quantum memories of any two nodes of a quantum network. The proposed protocols (denoted as AC1 and AC2) cope with the highly disruptive attack scenario where an attacker physically captures a node and takes full control of its operations. Interacting with the local quantum memory, the attacker reconfigures the states of the qubits (e.g., breaking entangled states shared with  other nodes, by measuring local qubits) either to make a denial-of-service attack or to reprogram the node to a behavior in accordance with her own plans.
Both AC1 and AC2 rely on local operations and classical communication (LOCC), with simple quantum circuits characterized by only a few H, Z, X and CNOT quantum gates (Figure 3). The execution of the protocols requires that some of the Bell states 00 shared by the Verifier and the Prover are sacrificed. Both protocols are randomized, reason why the Prover, challenged by the Verifier, cannot trick.


Figure 3 - Quantum circuits of the AC1 and AC2 protocols.

We proved that AC1 is (3/4)m-robust on any set of m Bell states sacrificed by the Verifier and the Prover, assuming that the Prover is controlled by an attacker that performs measurements either in the computational or diagonal basis. Moreover, we proved that AC2 is (3/8)m-robust on any set of 2m Bell states sacrificed by the Verifier and the Prover, with the same assumption as above. Here, ε-robustness means that the probability that the protocol aborts is at most ε. Furthermore, by means of simulations, we observed that the probability to detect the attacker in one round of the AC2 protocol, is greater than or equal to 1/2 for any possible choice of the measurement basis by the attacker.



Our current research on quantum compilers follows two main directions. On the one hand, we need to take into account not only the architecture of the hardware but also its noise profile. On the other hand, we are working on highly innovative quantum compilers for mapping any quantum algorithm to any distributed quantum computing architecture, in order to achieve high-quality distributed quantum computations.
Regarding QGM, we plan to integrate complementary protocols, such as quantum leader election ones, in order to cope with dynamic scenarios where the role of coordinator may not be assigned in advance.
Finally, we will investigate the possibility to extend our entanglement verification protocols to quantum systems that involve more than two qubits, to cope for example with GHZ states, W states and graph states.



[QSManifesto] Quantum Software EU Platform, Quantum Software Manifesto (2017)

[QIS] Quantum Software, University of Parma, http://www.qis.unipr.it/quantumsoftware.html

[Preskill2018] Preskill, J.: Quantum Computing in the NISQ era and beyond. Quantum 2(79) (2018)

[Botea2018] Botea, A., Kishimoto, A., Marinescu, R.: On the Complexity of Quantum Circuit Compilation. The Eleventh International Symposium on Combinatorial Search (SOCS 2018) (2018)

[Zulehner2019] Zulehner, A., Paler, A., Wille, R.: An ecient methodology for mapping quantum circuits to the IBM QX architectures. IEEE Trans. on CAD of Integrated Circuits and Systems 38(7), 1226-1236 (2019)

[Hart1968] Hart, P. E., Nilsson, N. J. and Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107 (1968)

[Li2019] Li, G., Ding, Y., Xie, Y.: Tackling the qubit mapping problem for NISQ-era quantum devices. Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '19, pp. 1001-1014 (2019)

[Ferrari2018] Ferrari, D., Amoretti, M., Efficient and effective quantum compiling for entanglement-based machine learning on IBM Q devices. International Journal of Quantum Information 16(08), 1840006 (2018)

[Ferrari2019] Ferrari, D., Tavernelli, I., Amoretti, M., Efficient Quantum Compiling for Quantum Chemistry Simulation on IBM Q. 1st European Quantum Technology Conference (EQTC), Grenoble, France (2019)

[VanMeter2016] Van Meter, R., Devitt, S.J.: The Path to Scalable Distributed Quantum Computing. Computer 49(9), pp. 31-42 (2016)

[Wehner2018] Wehner, S., Elkouss, D., Hanson, R.: Quantum internet: A vision for the road ahead. Science 362(6412) (2018)

[Amoretti2019] Amoretti, M., Pizzoni, M., Carretta, S: Enhancing distributed functional monitoring with quantum protocols. Quantum Information Processing 18(21), 371 (2019)

[Giatrakos2016] Giatrakos, N., Deligiannakis, A., Garofalakis, M.: Scalable approximate query tracking over highly distributed data streams. ACM SIGMOD ‘16. ACM (2016)

[Dahlberg2019] Dahlberg, A.,Wehner, S.: Simulaqron—A simulator for developing quantum internet software. Quantum Science and Technology 4, 015001 (2019)

[Amoretti2020] Amoretti, M., Carretta, S.: Entanglement Verification in Quantum Networks With Tampered Nodes. IEEE Journal on Selected Areas in Communications 38 (3), pp. 598-604 (2020)