12 June 2018 in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
In the past years, quantum computers more and more have evolved from an academic idea to an upcoming reality. IBM’s project IBM Q can be seen as evidence of this progress. Launched in March 2017 with the goal to provide access to quantum computers for a broad audience, this allowed users to conduct quantum experiments on a 5-qubit and, since June 2017, also on a 16-qubit quantum computer (called IBM QX2 and IBM QX3, respectively). Revised versions of these 5-qubit and 16-qubit quantum computers (named IBM QX4 and IBM QX5, respectively) are available since September 2017. In order to use these, the desired quantum functionality (e.g. provided in terms of a quantum circuit) has to be properly mapped so that the underlying physical constraints are satisfied – a complex task. This demands solutions to automatically and efficiently conduct this mapping process. In this paper, we propose a methodology which addresses this problem, i.e. maps the given quantum functionality to a realization which satisfies all constraints given by the architecture and, at the same time, keeps the overhead in terms of additionally required quantum gates minimal. The proposed methodology is generic, can easily be configured for similar future architectures, and is fully integrated into IBM’s SDK. Experimental evaluations show that the proposed approach clearly outperforms IBM’s own mapping solution. In fact, for many quantum circuits, the proposed approach determines a mapping to the IBM architecture within minutes, while IBM’s solution suffers from long runtimes and runs into a timeout of 1 hour in several cases. As an additional benefit, the proposed approach yields mapped circuits with smaller costs (i.e. fewer additional gates are required). All implementations of the proposed methodology is publicly available at http://iic.jku.at/eda/research/ibmqxmapping.
8 May 2018 in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Quantum computation is a promising emerging technology which, compared to conventional computation, allows for substantial speed-ups e.g. for integer factorization or database search. However, since physical realizations of quantum computers are in their infancy, a significant amount of research in this domain still relies on simulations of quantum computations on conventional machines. This causes a significant complexity which current state-of-the-art simulators try to tackle with a rather straight forward array-based representation and by applying massive hardware power. There also exist solutions based on decision diagrams (i.e. graph-based approaches) that try to tackle the exponential complexity by exploiting redundancies in quantum states and operations. However, these existing approaches do not fully exploit redundancies that are actually present. In this work, we revisit the basics of quantum computation, investigate how corresponding quantum states and quantum operations can be represented even more compactly, and, eventually, simulated in a more efficient fashion. This leads to a new graph-based simulation approach which outperforms state-of-the-art simulators (array-based as well as graph-based). Experimental evaluations show that the proposed solution is capable of simulating quantum computations for more qubits than before, and in significantly less run-time (several magnitudes faster compared to previously proposed simulators). An implementation of the proposed simulator is publicly available online at http://www.jku.at/iic/eda/quantum_simulation.
19 July 2017 in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Reversible computation is a heavily investigated emerging technology due to its promising characteristics in low-power design, its application in quantum computations, and several further application areas. The currently established functional synthesis flow for reversible circuits is composed of two distinct steps. First, an embedding process is conducted which makes nonunique output patterns distinguishable by adding further variables. Then, this function is passed to a synthesis method which eventually yields a reversible circuit. However, the separate consideration of the embedding and synthesis tasks leads to significant drawbacks. In fact, embedding is not necessarily conducted in a fashion which is suited for the following synthesis process. In addition, embedding adds further variables to the function to be synthesized which exponentially increases its corresponding representation in the worst case. In this paper, we propose one-pass design of reversible circuits, which combines embedding and synthesis. This allows for conducting synthesis with a high degree of freedom, since the embedding that suits best is inherently chosen during synthesis. We propose two solutions (an exact an a heuristic one) following this scheme that improve the currently established synthesis flow by magnitudes in terms of runtime-allowing to synthesize a reversible circuit with a minimum number of lines for some of the frequently considered benchmark functions for the first time. Furthermore, a significant reduction of the costs of the resulting circuits (up to several orders of magnitude) is achieved with this new design flow.
27 July 2022 in ACM Transactions on Quantum Computing
Quantum computers promise to solve important problems faster than conventional computers ever could. Underneath is a fundamentally different computational primitive that introduces new challenges for the development of software tools that aid designers of corresponding quantum algorithms. The different computational primitives render classical simulation of quantum circuits particularly challenging. While the logic simulation of conventional circuits is comparatively simple with linear complexity with respect to the number of gates, quantum circuit simulation has to deal with the exponential memory requirements to represent quantum states on non-quantum hardware with respect to the number of qubits. Decision Diagrams (DDs) address this challenge through exploitation of redundancies in matrices and vectors to provide significantly more compact representations in many cases. Moreover, the probabilistic nature of quantum computations enables another angle to tackle the complexity: Quantum algorithms are resistant to some degree against small inaccuracies in the quantum state as these only lead to small changes in the outcome probabilities. We propose to exploit this resistance against (small) errors to gain even more compact decision diagrams. In this work, we investigate the potential of approximation in quantum circuit simulation in detail. To this end, we first present four dedicated schemes that exploit the error resistance and efficiently approximate quantum states represented by decision diagrams. Subsequently, we propose two simulation strategies that utilize those approximations schemes in order to improve the efficiency of DD-based quantum circuit simulation, while, at the same time, allowing the user to control the resulting degradation in accuracy. We empirically show that the proposed approximation schemes reduce the size of decision diagrams substantially and also analytically prove the effect of multiple approximations on the attained accuracy. Eventually, this enables speed-ups of the resulting approximate quantum circuit simulation of up to several orders of magnitudes—again, while controlling the fidelity of the result.