Research on quantum computers has gained attention since they are able to solve certain tasks significantly faster than classical machines (in some cases, exponential speed-ups are possible). Since quantum computations typically contain large Boolean components, design automation techniques are required to realize the respective Boolean functions in quantum logic. They usually introduce a significant amount of additional qubits - a highly limited resource. In this work, we propose an alternative method for the realization of Boolean components for quantum logic. In contrast to the current state-of-the-art, we dedicatedly address the main reasons causing the additionally required qubits (namely the number of the most frequently occurring output pattern as well as the number of primary outputs of the function to be realized) and propose to manipulate the function so that both issues are addressed. The resulting methods allow to push the number of required qubits below what is currently considered the minimum.
Research on quantum computers has gained attention since they are able to solve certain tasks significantly faster than classical machines (in some cases, exponential speed-ups are possible). Since quantum computations typically contain large Boolean components, design automation techniques are required to realize the respective Boolean functions in quantum logic. They usually introduce a significant amount of additional qubits - a highly limited resource. In this work, we propose an alternative method for the realization of Boolean components for quantum logic. In contrast to the current state-of-the-art, we dedicatedly address the main reasons causing the additionally required qubits (namely the number of the most frequently occurring output pattern as well as the number of primary outputs of the function to be realized) and propose to manipulate the function so that both issues are addressed. The resulting methods allow to push the number of required qubits below what is currently considered the minimum.
Research on quantum computing has recently gained significant momentum since first physical devices became available. Many quantum algorithms make use of so-called oracles that implement Boolean functions and are queried with highly superposed input states in order to evaluate the implemented Boolean function for many different input patterns in parallel. To simplify or enable a realization of these oracles in quantum logic in the first place, the Boolean reversible functions to be realized usually need to be broken down into several non-reversible sub-functions. However, since quantum logic is inherently reversible, these sub-functions have to be realized in a reversible fashion by adding further qubits in order to make the output patterns distinguishable (a process that is also known as embedding). This usually results in a significant increase of the qubits required in total. In this work, we show how this overhead can be significantly reduced by utilizing coding. More precisely, we prove that one additional qubit is always enough to embed any non-reversible function into a reversible one by using a variable-length encoding of the output patterns. Moreover, we characterize those functions that do not require an additional qubit at all. The made observations show that coding often allows one to undercut the usually considered minimum of additional qubits in sub-functions of oracles by far.
The pressure of fundamental limits on classical computation and the promise of exponential speedups from quantum effects have recently brought quantum circuits (Proc. R. Soc. Lond. A, Math. Phys. Sci., vol. 425, p. 73, 1989) to the attention of the electronic design automation community (Proc. 40th ACM/IEEE Design Automation Conf., 2003), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 68, p. 012318, 2003), (Proc. 41st Design Automation Conf., 2004), (Proc. 39th Design Automation Conf., 2002), (Proc. Design, Automation, and Test Eur., 2004), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 69, p. 062321, 2004), (IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 22, p. 710, 2003). Efficient quantum-logic circuits that perform two tasks are discussed: 1) implementing generic quantum computations, and 2) initializing quantum registers. In contrast to conventional computing, the latter task is nontrivial because the state space of an n-qubit register is not finite and contains exponential superpositions of classical bitstrings. The proposed circuits are asymptotically optimal for respective tasks and improve earlier published results by at least a factor of 2. The circuits for generic quantum computation constructed by the algorithms are the most efficient known today in terms of the number of most expensive gates [quantum controlled-NOTs (CNOTs)]. They are based on an analog of the Shannon decomposition of Boolean functions and a new circuit block, called quantum multiplexor (QMUX), which generalizes several known constructions. A theoretical lower bound implies that the circuits cannot be improved by more than a factor of 2. It is additionally shown how to accommodate the severe architectural limitation of using only nearest neighbor gates, which is representative of current implementation technologies. This increases the number of gates by almost an order of magnitude, but preserves the asymptotic optimality of gate counts.
Abstract Quantum computing has gained attention in recent years due to the significant progress in quantum computing technology. Today many companies like IBM, Google and Microsoft have developed quantum computers and simulators for research and commercial use. The development of quantum techniques and algorithms is essential to exploit the full power of quantum computers. In this paper we propose a simple visual technique (we call Q-Map) for quantum realization of classical Boolean logic circuits. The proposed method utilizes concepts from Boolean algebra to produce a quantum circuit with minimal number of quantum gates.
Quantum computation established itself as a promising emerging technology and, hence, attracted considerable attention in the domain of computer-aided-design (CAD). However, quantum mechanical phenomena such as superposition, phase shifts, or entanglement lead to a logic model which poses serious challenges to the development of a proper design flow for quantum circuits. Consequently, researchers addressed synthesis of quantum circuits not as a single design step, but considered sub-tasks such as synthesis of Boolean components or synthesis of restricted subsets of quantum functionality. Generating a particularly desired quantum state is another of these sub-tasks. However, logic synthesis of quantum circuits accomplishing that has hardly been considered yet. In this work, we propose a generic method which automatically synthesizes a quantum circuit generating any desired quantum state from an initially given basis state. The proposed method allows for both, a theoretical determination of upper bounds as well as an experimental evaluation of the number of quantum gates needed for this important design step.
Noisy intermediate scale quantum (NISQ) computers are becoming a reality thanks to the recent advances made by researchers who physically build such systems. In order to execute corresponding quantum algorithms (usually provided in terms of quantum circuits), certain physical constraints in the architectures need to be satisfied. More precisely, physical constraints restrict the possible interactions between qubits which frequently result in cases where qubits which are supposed to interact in a quantum circuit are not allowed to interact on the physical device. Thus far, this is addressed by dedicated methods that map the logical quantum circuit to a physical realization and satisfy the constraints by inserting further operations. This leads to additional costs which harm the fidelity of the circuit and, hence, urgently need to be avoided. Unfortunately, current state-of-the-art approaches for this mapping process take the existing architectures as invariant and only try to reduce the number of additionally needed operations. In contrast, (slight) changes in the, respectively, given architectures (which still keep the underlying physical constraints satisfied) might be possible and may allow for even better (i.e., less costly) mappings. But this potential has not been investigated yet. In this work, we explore this potential. More precisely, we introduce several schemes for generating alternative coupling graphs (and, by this, quantum computing architectures) that still might be able to satisfy physical constraints but, at the same time, allow for a more efficient realization of the desired quantum functionality. Evaluations confirm the potential of those alternative coupling graphs and demonstrate that they can reduce the mapping overhead by up to 60% in the best case and up to almost 40% on average.
Although the concept of quantum computing has existed for decades, the technology needed to successfully implement a quantum computing system has not yet reached the level of sophistication, reliability, and scalability necessary for commercial viability until very recently. Significant progress on this front was made in the past few years, with IBM planning to create a 1000-qubit chip by the end of 2023, and Google already claiming to have achieved quantum supremacy. Other major industry players such as Intel and Microsoft have also invested significant amounts of resources into quantum computing research. Any viable computing system requires both hardware and software to work together harmoniously in order to perform useful computations. While the achievements of IBM and other companies represent a large step forward for quantum hardware, many gaps remain to be filled with respect to the corresponding software. Specifically, there is currently no clear path towards a complete process for translating quantum algorithms into physical operations that are directly executable on quantum hardware. Such a process is analogous to a compiler that translates programs written in a high-level language into executable machine instructions on a conventional digital computer, and it is necessary if quantum computers are to be harnessed to perform practically useful computations. Existing work has addressed individual components of this process, but so far no unified method for translating the whole of a quantum algorithm into executable operations has been described. I make substantial progress towards filling this gap by describing a set of high-level and low-level quantum circuit design techniques, which when taken together reduce the need of a circuit designer to be concerned with low-level details. On the high-level side, I describe an approach or strategy to designing quantum oracles for Grover's algorithm that allows it to be applied to several types of problems. This approach involves designing oracles in terms of high-level blocks such as counters, multiplexers, comparators, and arbitrary Boolean functions. The implementations of these blocks in terms of lower-level quantum gates are demonstrated in a way that makes it clear that scaled-up versions of them can be generated in a completely automated fashion. For a specific class of problems, which I call state-space path planning problems, I also introduce a paradigm for quantum oracle design that involves representing the problem in terms of individual states and moves. Problems of this sort have applications in robotics and games. Low-level techniques that I introduce