Silicon Dangling Bond (SiDB) logic is a promising technology for energy-efficient computation, supported by significant advancements in manufacturing and design automation. However, physical simulation, essential for accurately predicting the behavior of SiDB logic prior to costly manufacturing, lags behind these developments. In particular, exact physical simulation, which scales exponentially with base 3, remains infeasible for larger SiDB assemblies, limiting its utility to small structures such as single gates. This computational bottleneck slows progress in SiDB technology and hinders the establishment of reliable ground truths for heuristic approaches. To address the challenge, this work presents a novel methodology for exact SiDB simulation that restructures the exponential search space according to a hierarchical clustering. The hierarchy structure enables a systematic pruning of the search space at its different levels: it provides an ordering of interactions between clusters of SiDBs to facilitate efficacious exploitation of dynamically-inferred problem-specific constraints-like solving a Sudoku. Experimental results demonstrate that the effective exponential base can be lowered to approximately 1.3, enabling, for the first time, the exact physical simulation of entire multi-gate SiDB circuits in minutes that would take the state of the art millions of years to compute. This breakthrough establishes a robust ground truth for SiDB logic validation, marking a pivotal step toward scalable, energy-efficient, and atomic-scale computing.

As the capabilities of quantum computing hardware continue to rise, algorithms that exploit them are becoming increasingly complex. These developments increase the need for sophisticated compilation frameworks that translate high-level algorithms into executable code. In the past, most solutions were built with a quantum-first approach and handled mostly pure quantum programs without classical elements such as structured control flow. However, developments in quantum algorithms, error correction, and optimization, as well as the integration into high-performance computing (HPC) environments, depend on such classical elements. As quantum-first approaches increasingly struggle to handle these concepts, classical-first approaches are becoming a promising alternative. In this work, we present the MQT Compiler Collection, a blueprint for a future-proof quantum-classical compilation framework built on the Multi-Level Intermediate Representation (MLIR). After years of experience with the quantum-first approach and its shortcomings, we propose a framework that embraces core MLIR concepts to support the full compilation pipeline from high-level algorithms to hardware-specific instructions. The proposed architecture is designed from the ground up to support complex optimizations beyond, e.g., simple gate cancellation. It is publicly available at github.com/munich-quantum-toolkit/core.

Superconducting quantum computers are fundamentally limited by restricted qubit connectivity. Bus-resonator architectures alleviate this constraint by enabling effective all-to-all interactions. This advantage, however, comes at the cost of significant operational overhead. Realizing the full potential of such hardware thus requires sophisticated compilation techniques that minimize this overhead. In this work, we present the first formalization of the underlying compilation problem for bus-resonator architectures amenable to so-called SAT-CP solvers. This formalization yields optimal solutions for small quantum circuits. For larger instances, we propose a linear-time heuristic. Experimental evaluations confirm that the formalization makes it possible to find optimal solutions even in vast search spaces and that the heuristic provides near-optimal compilation while scaling efficiently to circuits of practical size. Together, these contributions establish both a rigorous baseline and a practical path toward low-overhead compilation for superconducting bus-resonator devices.

The Quantum Approximate Optimization Algorithm (QAOA) requires considered optimization problems to be translated into a compatible format. A popular transformation step in this pipeline involves the quadratization of higher-order binary optimization problems, translating them into Quadratic Unconstrained Binary Optimization (QUBO) formulations through the introduction of auxiliary variables. Conventional algorithms for the selection of auxiliary variables often aim to minimize the total number of required variables without taking the constraints of the underlying quantum computer-in particular, the connectivity of its qubits-into consideration. This quickly results in interaction graphs that are incompatible with the target device, resulting in a substantial compilation overhead even with highly optimized compilers. To address this issue, this work presents a novel approach for the selection of auxiliary variables tailored for architectures with limited connectivity. By specifically constructing an interaction graph with a regular structure and a limited maximal degree of vertices, we find a way to construct QAOA circuits that can be mapped efficiently to a variety of architectures. We show that, compared to circuits constructed from a QUBO formulation using conventional auxiliary selection methods, the proposed approach reduces the circuit depth by almost 40%. An implementation of all proposed methods is publicly available at https://github.com/munich-quantum-toolkit/problemsolver.

We present a novel quantum circuit extraction scheme that tightly integrates graph-like ZX diagrams with hardware-adaptive routing. The method utilizes the degrees of freedom during the conversion from a ZX diagram to a quantum circuit (extraction). It alternates between generating multiple extraction options and evaluating them based on hardware constraints, allowing the routing algorithm to inform and guide the extraction process. This feedback loop extends existing graph-like ZX extraction and supports modular integration of different extraction algorithms, routing strategies, and target hardware, making it a versatile building block during compilation. To perform numerical evaluations, a reference instance of the scheme is implemented with SWAP-based routing for neutral atom hardware and evaluated using various benchmark collections on small-to mid-scale circuits. The reference code is available as open-source, allowing fast integration of other extraction and/or routing tools to stimulate further research and foster improvements of the proposed scheme.

Power consumption is a primary constraint in modern digital circuit design, with switching activity being a major contributor to dynamic power dissipation. While exact synthesis methods guarantee optimality for metrics such as gate count or delay, they typically do not directly target switching activity. This paper presents a novel SAT-based exact synthesis approach designed to minimize switching activity in combinational logic circuits. We extend existing SAT encodings for logic synthesis, incorporating new constraints and variables to model and constrain the switching behavior of the circuit. Different SAT encoding strategies, including BDD-based approaches for handling cardinality constraints, as well as various search algorithms, are explored. Experimental results on NPN benchmark functions demonstrate the effectiveness of the proposed method in identifying circuits with, on average, 6.7% (over 30% in the best case) reduced switching activity compared to traditional exact synthesis techniques, often achieving this reduction with no or minimal area overhead. While runtime remains challenging, this work establishes a foundation for power-aware exact synthesis.

Quantum computing is becoming a reality. Superconducting, ion traps, neutral atoms, etc.—the hardware is getting there! However, software capable of handling complex design tasks is needed to connect end users to these platforms. Unfortunately, software for quantum computing is still in its infancy, and the development of quantum computing software remains a significant challenge. The MQSC aims to create production-ready software tools that provide for quantum computing what we already take for granted in classical IT.

Vehicle-to-Everything (V2X) perception enhances 3D object detection by extending sensing range and mitigating occlusions through information sharing between infrastructure- and vehicle-mounted sensors. Among various sensing modalities, 4D radar has attracted increasing attention for V2X perception due to its ability to provide 3D point clouds and velocity measurements, as well as its robustness under adverse weather. However, 4D radar point clouds remain sparse and noisy. Recent advances in vision-language models (VLMs) have enabled high-level scene understanding from visual inputs, with strong generalization to complex and unseen scenes. Motivated by this, we propose a novel 4D radar and text fusion framework, Text4Radar-V2X, which leverages text semantics to compensate for the sparsity of 4D radar features. Specifically, we introduce a view-specific asymmetric text-generation strategy. The generated Q&A pairs contain background structural semantics from infrastructure perspectives and foreground object semantics from vehicle perspectives. Furthermore, we design a dual-branch text-driven interaction to hierarchically integrate asymmetric text with 4D radar point clouds. Extensive experiments on the V2X-R dataset demonstrate that our method achieves the best mAP at IoU thresholds of 0.3 and 0.5, with improvements of 2.52% and 2.07%, respectively.

In recent years,Silicon Dangling Bond(SiDB) logic has emerged as a promising beyond-CMOS technology due to its integration density and operating frequency. This advancement is driving the development of comprehensive design automation workflows, including physical simulators and gate design tools. Unlike conventional circuit technology, where logic is implemented through transistors, SiDB logic utilizes quantum dots with variable charge states. By strategically arranging these dots, standard logic functions like OR, AND, NAND, etc. can be implemented, which are usually provided asStandard Cellsin design processes. However, finding such arrangements that implement a given Boolean function is a tremendously complex task that involves considering numerous candidates and verifying them through computationally expensive physical simulation. Hence, the automatic obtainment of SiDB logic layouts is thus far limited to simple 2-input functions only— which already require substantial computation resources. In contrast, conventional physical design algorithms for VLSI have long transitioned from single-gate considerations to multi-input standard cells. To address this challenge, this paper proposesQuickCell: A fast algorithm for automatic standard cell design for SiDB logic that uses dedicated search space pruning techniques. In an extensive experimental evaluation, it is demonstrated that combining these pruning techniques yields 1) a drastic reduction of the search space amounting to up to six orders of magnitude, 2) a corresponding decrease of the runtime by up to a factor of 91, 3) the capability to handle more complex functionality, as, e. g., utilized in standard cells, for the first time, significantly narrowing the gap between SiDB logic and conventional CMOS design paradigms, and 4) a significant speedup compared to physical simulation (up to a factor of 10 000), with near independence from the number of I/O pins when determining the non-operationality of a given layout. This efficiency makes these techniques—and by extensionQuickCell—a powerful enabler for the design of complex standard cells.

Field-coupled Nanocomputing(FCN) is a post-CMOS paradigm in which information propagates through near-field interactions rather than charge flow, enabling ultra-low-power, high-density logic. Translating netlists into manufacturable, cell-level layouts therefore becomes a pivotal challenge. Existing FCN physical design tools optimize only a single cost metric, typically footprint or runtime. As a result, designers must choose between exponentially slow exact solvers and fast yet area-intensive heuristics. We present the first FCN physical design engine that closes this gap by introducing configurableeffort modes. These modes let users trade runtime for solution quality while simultaneously optimizing any discretionary objective, e. g. area, wire segments, crossings, or delay, thereby integrating data from physical simulation and manufacturing constraints. Our open-source implementation, released as part of theMunich Nanotech Toolkit, generates layouts for circuits that defeat state-of-the-art exact solvers. On such benchmarks, it shrinks footprint by an average of 73.07 %, reduces crossings by 19.10 %, and cuts wire segments by 54.47 % relative to a leading heuristic baseline. Even after post-layout optimization of the baseline, our approach still achieves mean gains of 25.99 % in area, 37.82% in crossings, and 25.96% in wire segments. These results establish the proposed engine as a compelling solution for highly optimized, large-scale standard-cell FCN design.

Boost converters are a crucial component in power conversion systems, often operated in quasi-resonant mode (QRM) to reduce switching losses and enhance efficiency for medium and low power level applications. However, traditional modelling approaches have difficulties in balancing simulation speed and accuracy, particularly during transient phases. Moreover, conventional linear control schemes such as PI control have limitations in fast transient regulation.In this paper, a state machine-based model is proposed and tested. Compared to Simscape model in MATLAB/Simulink, the proposed modelling method shows high accuracy in output voltage both in steady state and transient phase. Furthermore, a neural network-based nonlinear control scheme has been designed to optimize the transient response and is compared to a tuned PI controller.

Despite the continuous advancements in size and robustness of real quantum devices, reliable large-scale quantum computers are not yet available. Hence, classical simulation of quantum algorithms remains crucial for testing new methods and estimating quantum advantage. Pushing classical simulation methods to their limit is essential, particularly due to their inherent exponential complexity. Besides the established Schrödinger-style full statevector simulation, so-called Hybrid Schrödinger-Feynman (HSF) approaches have shown promise to make simulations more efficient. HSF simulation employs the idea of “cutting” the circuit into smaller parts, reducing their execution times. This, however, comes at the cost of an exponential overhead in the number of cuts. Inspired by the domain of Quantum Circuit Cutting, we propose an HSF simulation method based on the idea of “joint cutting” to significantly reduce the aforementioned overhead. This means that, prior to the cutting procedure, gates are collected into “blocks” and all gates in a block are jointly cut instead of individually. We investigate how the proposed refinement can help decrease simulation times and highlight the remaining challenges. Experimental evaluations show that “joint cutting” can outperform the standard HSF simulation by up to a factor $\approx 4000 \times$ and the Schrödinger-style simulation by a factor $\approx 200 \times$ for suitable instances. The implementation is available at https://github.com/cda-tum/mqt-qsim-joint-cutting.

In recent years, Silicon Dangling Bond (SiDB) logic has emerged as a promising beyond-CMOS technology. Unlike conventional circuit technology, where logic is realized through transistors, SiDB logic utilizes quantum dots with variable charge states. By strategically arranging these dots, logic functions can be constructed. However, determining such arrangements is a tremendously complex task. Because of that, the automatic obtainment of SiDB logic implementations is inefficient. To address this challenge, we propose an idea to speed up the design process by utilizing dedicated search space pruning strategies. Initial results show that the combined pruning techniques yield 1) a drastic reduction of the search space, and 2) a corresponding reduction in runtime by up to a factor of 33.

And-Inverter Graphs (AIGs) are a fundamental data structure in logic optimization, widely used in modern electronic design automation. A persistent challenge in AIG optimization is structural bias, where the initial graph structure strongly influences optimization quality by restricting the search space, often resulting in subpar outcomes. Existing methods address this issue by running multiple optimization workflows in parallel, relying on a trial-and-error approach that lacks a systematic way to measure structural diversity or assess effectiveness, making them computationally expensive and inefficient. This paper introduces a novel framework for systematically evaluating and reducing structural bias by measuring structural diversity, defined as the degree of dissimilarity between AIG graphs. Several traditional graph similarity measures and newly proposed AIG-specific metrics, including the Rewrite, Refactor, and Resub Scores, are explored. Results reveal limitations in traditional graph similarity metrics and highlight the effectiveness of the proposed AIG-specific measures in quantifying structural dissimilarity. Notably, the RRR Score shows a strong correlation (Pearson correlation coefficient,$r$= 0.79) with post-optimization structural differences, demonstrating the reliability of the metric in capturing meaningful variations between AIG structures. This work addresses the challenge of quantifying structural bias and offers a methodology that can potentially improve optimization outcomes, with future extensions applicable to other logic graph types.

Field-coupled Nanocomputing (FCN), a class of post-CMOS technologies operating at the nanoscale without the flow of electricity, is becoming a reality due to advancements in simulating and manufacturing logic gates using Silicon Dangling Bonds (SiDBs). Efficient physical design methodologies are crucial for the performance, area efficiency, reliability, and manufacturability of FCN circuits. However, despite considerable progress in developing algorithms and tools tailored to FCN physical design, achieving efficient results still requires a co-design approach, necessitating expert manual refinement similar to the CMOS design process. To this end, we introduce a GUI-based tool that combines both automation and expert adjustments, enabling designers to easily optimize and modify FCN layouts. To demonstrate its potential, a designer used the tool to reduce the area of the best-known layout for the benchmark circuit cm82a by over 15 % in less than a minute. Additionally, the tool is publicly available as open-source at https://github.com/cda-tum/mnt-designer.

Quantum computing is an emerging technology that has seen significant software and hardware improvements in recent years. Executing a quantum program requires the compilation of its quantum circuit for a target Quantum Processing Unit (QPU). Various methods for qubit mapping, gate synthesis, and optimization of quantum circuits have been proposed and implemented in compilers. These compilers try to generate a quantum circuit that leads to the best execution quality-a criterium which is usually approximated by figures of merit such as the number of (two-qubit) gates, the circuit depth, expected fidelity, or estimated success probability. However, it is often unclear how well these figures of merit represent the actual execution quality on a QPU. In this work, we investigate the correlation between established figures of merit and actual execution quality on real machines-revealing that the correlation is weaker than anticipated and that more complex figures of merit are not necessarily more accurate. Motivated by this finding, we propose an improved figure of merit (based on a machine learning approach) that can be used to predict the expected execution quality of a quantum circuit for a chosen QPU without actually executing it. The employed machine learning model reveals the influence of various circuit features on generating high correlation scores. The proposed figure of merit demonstrates a strong correlation and outperforms all previous ones in a case study-achieving an average correlation improvement of 49%.

To ensure resilience against the unavoidable noise in quantum computers, quantum information needs to be encoded using an error-correcting code, and circuits must have a particular structure to be fault-tolerant. Compilation of fault-tolerant quantum circuits is thus inherently different from the non-fault-tolerant case. However, automated fault-tolerant compilation methods are widely underexplored, and most known constructions are obtained manually for specific codes only. In this work, we focus on the problem of automatically synthesizing fault-tolerant circuits for the deterministic initialization of an encoded state for a broad class of quantum codes that are realizable on current and near-term hardware. To this end, we utilize methods based on techniques from classical circuit design, such as satisfiability solving, resulting in tools for the synthesis of (optimal) fault-tolerant state preparation circuits for near-term quantum codes. We demonstrate the correct fault-tolerant behavior of the synthesized circuits using circuit-level noise simulations. We provide all routines as open-source software as part of the Munich Quantum Toolkit (MQT) at https://github.com/cdatum/mqt-qecc.

Quantum computing promises to solve problems previously deemed infeasible. However, high error rates necessitate quantum error correction for practical applications. Seminal experiments with zoned neutral atom architectures have shown remarkable potential for fault-tolerant quantum computing. To fully harness their potential, efficient software solutions are vital. A key aspect of quantum error correction is the initialization of physical qubits representing a logical qubit in a highly entangled state. This process, known as state preparation, is the foundation of most quantum error correction codes and, hence, a crucial step towards fault-tolerant quantum computing. Generating a schedule of target-specific instructions to perform the state preparation is highly complex. First software tools exist but are not suitable for the zoned neutral atom architectures. This work addresses this gap by leveraging the computational power of SMT solvers and generating minimal schedules for the state preparation of logical arrays. Experimental evaluations demonstrate that actively utilizing zones to shield idling qubits consistently results in higher fidelities than solutions disregarding these zones. The complete code is publicly available in open-source as part of the Munich Quantum Toolkit (MQT) at https://github.com/cdatum/mqt-qmap.

The demand for sustainable railway transportation is increasing over time.At the same time, the capacity of railway networks is limited.Hence, efficient algorithms for generating optimal timetables are of great interest.Previous research focuses on trains being separated by classical fixed block signaling systems.With modern control systems based on moving block, e.g., within the European Train Control System (ETCS), the principles of safely separating trains change significantly.Only limited research on optimal routing on such modern railway networks exists.With this work, we propose a simulation approach tailored to be used with heuristic optimization algorithms to tackle this problem.Moreover, we show how such a framework can allow for more general inputs to jointly optimize what is usually planned sequentially as of today.The simulation framework is included within the open-source Munich Train Control Toolkit (MTCT) available on GitHub at https://github.com/cda-tum/mtct.

807

773

Radar and LiDAR have been widely used in autonomous driving as LiDAR provides rich structure information, and radar demonstrates high robustness under adverse weather. Recent studies highlight the effectiveness of fusing radar and LiDAR point clouds. However, challenges remain due to the modality misalignment and information loss during feature extractions. To address these issues, we propose a 4D radar-LiDAR framework to mutually enhance their representations. Initially, the indicative features from radar are utilized to guide both radar and LiDAR geometric feature learning. Subsequently, to mitigate their sparsity gap, the shape information from LiDAR is used to enrich radar BEV features. Extensive experiments on the View-of-Delft (VoD) dataset demonstrate our approach’s superiority over existing methods, achieving the highest mAP of 71.76% across the entire area and 86.36% within the driving corridor. Especially for cars, we improve the AP by 4.17% and 4.20% due to the strong indicative features and symmetric shapes.

Recently, radar-camera fusion algorithms have gained significant attention as radar sensors provide geometric information that complements the limitations of cameras. However, most existing radar-camera depth estimation algorithms focus solely on improving performance, often neglecting computational efficiency. To address this gap, we propose LiRCDepth, a lightweight radar-camera depth estimation model. We incorporate knowledge distillation to enhance the training process, transferring critical information from a complex teacher model to our lightweight student model in three key domains. Firstly, low-level and high-level features are transferred by incorporating pixel-wise and pair-wise distillation. Additionally, we introduce an uncertainty-aware inter-depth distillation loss to refine intermediate depth maps during decoding. Leveraging our proposed knowledge distillation scheme, the lightweight model achieves a 6.6% improvement in MAE on the nuScenes dataset compared to the model trained without distillation. Code: https://github.com/harborsarah/LiRCDepth

Microfluidics is a rapidly growing field that aims to simplify complex analytical procedures by moving them to small-scale devices. A particularly interesting application of microfluidics are so-called Organs-on-Chips, i.e., microfluidic devices that mimic the structure and function of human organs and, therefore, allow studying the effects of drugs and diseases. Recent recognition of the need for standardization in this domain has led to the generation and uptake of new ISO standards—providing the basis of modular and reusable microfluidic building blocks that allow for various organ-on-chip setups. However, designing these building blocks, especially so-called routing blocks that interconnect pumps, cell cultures, and other modules is a cumbersome, repetitive task that is still conducted manually. In this work, we propose a design and routing method that significantly simplifies the design of such routing blocks by fully automating the process of interconnecting components of a microfluidic chip. The evaluation of physical, fabricated routing blocks that were designed using the proposed method showcases its feasibility in real-world applications and its potential to reduce design effort and time significantly. In order to make the work accessible to the microfluidic community, we provide implementations of the resulting methods in the form of a user-friendly, interactive online tool, provided as part of the Munich Microfluidic Toolkit (MMFT).

Quantum computing promises to solve previously intractable problems, with neutral atoms emerging as a promising technology. Zoned neutral atom architectures allow for immense parallelism and higher coherence times by shielding idling atoms from interference with laser beams. However, in addition to hardware, successful quantum computation requires sophisticated software support, particularly compilers that optimize quantum algorithms for hardware execution. In the compilation flow for zoned neutral atom architectures, the effective interplay of the placement and routing stages decides the overhead caused by rearranging the atoms during the quantum computation. Suboptimal placements can lead to unnecessary serialization of the rearrangements in the subsequent routing stage. Despite this, all existing compilers treat placement and routing independently thus far—focusing solely on minimizing travel distances. This work introduces the first routing-aware placement method to address this shortcoming. It groups compatible movements into parallel rearrangement steps to minimize both rearrangement steps and travel distances. The implementation utilizing the A* algorithm reduces the rearrangement time by 17% on average and by 49% in the best case compared to the state-of-the-art. The complete code is publicly available in open-source as part of the Munich Quantum Toolkit (MQT) at https://github.com/cda-tum/mqt-qmap.

Microfluidic devices have become essential in biochemical and medical research, enabling high-throughput experimentation on compact and cost-effective platforms. However, the design and realization of microfluidic devices is a manual, tedious, and error-prone task. Additionally, multiple iterations for prototyping are often needed until a physical realization works as intended. Accordingly, methods for the automatic design and simulation of microfluidic devices are key—something that is standard in the design of conventional circuits and systems. In this work, we present the Munich Microfluidics Toolkit (MMFT), an open-source toolkit that provides corresponding tools for automating the design and simulation of microfluidic systems. For selected design tasks—such as the generation of meanders, gradient generators, organs-on-chip layouts, as well as ISO-compliant routing and validation—we showcase corresponding tools and provide an overview of simulators for microfluidics. MMFT helps researchers and engineers to design microfluidic devices in an automatic fashion (often with the click of a button) and to validate them through simulation across different abstraction levels. All tools are publicly available at https://www.cda.cit.tum.de/research/microfluidics/mmft/.

LiDAR and 4D radar are widely used in autonomous driving and robotics. While LiDAR provides rich spatial information, 4D radar offers velocity measurement and remains robust under adverse conditions. As a result, increasing studies have focused on the 4D radar-LiDAR fusion method to enhance the perception. However, the misalignment between different modalities is often overlooked. To address this challenge and leverage the strengths of both modalities, we propose a LiDAR detection framework enhanced by 4D radar motion status and cross-modal uncertainty. The object movement information from 4D radar is first captured using a Dynamic Motion-Aware Encoding module during feature extraction to enhance 4D radar predictions. Subsequently, the instance-wise uncertainties of bounding boxes are estimated to mitigate the cross-modal misalignment and refine the final LiDAR predictions. Extensive experiments on the View-of-Delft (VoD) dataset highlight the effectiveness of our method, achieving state-of-the-art performance with the mAP of 74.89% in the entire area and 88.70% within the driving corridor while maintaining a real-time inference speed of 30.02 FPS.

As traditional transistor scaling reaches its physical and economic limits, Silicon Dangling Bond (SiDB) logic is emerging as a promising post-CMOS technology for atomic-scale computation. However, despite mitigation efforts, atomic defects persist on the hydrogen-passivated silicon surface and remain challenging to eliminate. Since SiDB logic is highly sensitive to these charged atomic defects, efficient defect robustness simulation is essential for reliable SiDB logic design and successful operation. Existing simulation methods, however, are inefficient, limiting their practical applicability. To address this shortcoming, we present QuickTrace, an efficient algorithm to simulate the defect robustness of SiDB logic. QuickTrace uses contour tracing to identify the boundary in the simulation area between operational and non-operational states caused by defect positions, allowing defect robustness to be simulated with significantly fewer simulator calls. Experimental evaluations show that QuickTrace precisely and accurately computes defect robustness while avoiding the need to consider 88% of potential defect positions in simulations—and thus reducing runtime by the same percentage—compared to the state-of-the-art approach. This enables efficient and scalable defect robustness simulation of SiDB logic for the first time, contributing to the advancement of SiDB technology as a promising post-CMOS technology.

This demonstration presents the Operational Domain Explorer, a PyQt6-based application designed for computationally efficient resilience analysis of Silicon Dangling Bond (SiDB) logic layouts. Leveraging novel algorithms, the tool significantly reduces the simulation load required for operational domain evaluations, supporting real-time, multi-dimensional visualizations and advancing SiDB layout reliability.

Multiorgans-on-chips (multi-OoCs) represent human or other animal physiology on a chip—providing testing platforms for the pharmaceutical, cosmetic, and chemical industries. They are composed of miniaturized organ tissues (so-called organ modules) that are connected via a microfluidic channel network and, by this, represent organ functionalities and their interactions on-chip. The design of these multi-OoC geometries, however, requires a sophisticated orchestration of numerous aspects, such as the size of organ modules, the required shear stress on membranes and subsequently the flow rate, the dimensions and geometry of channels, pump pressures, etc. Mastering all this constitutes a nontrivial design task for which, unfortunately, no automatic support exists yet. In this work, we propose a design automation solution for multi-OoC geometries. To this end, we review the respective design steps and derive a corresponding formal design specification from them. Based on that, we then propose an automatic design tool, which generates a design of the desired device and exports it in a fashion that is ready for subsequent simulation or fabrication. The open-source tool and a step-by-step tutorial are available athttps://github.com/cda-tum/mmft-ooc-designer. Evaluations (inspired by real-world use cases and confirmed by computational fluid dynamic simulations as well as a fabrication process) demonstrate the applicability and validity of the proposed approach.

Reversible computing has garnered significant attention as a promising avenue for achieving energy-efficient computing systems, particularly within the realm of quantum computing. The reversible quantum-flux-parametron (RQFP) is the first practical reversible logic gate utilizing adiabatic superconducting devices, with experimental evidence supporting both its logical and physical reversibility. Each RQFP logic gate operates on alternating current (AC) power and features three input ports and three output ports. Notably, each output port is capable of implementing a majority function while driving only a single fan-out. Additionally, the three inputs to each gate must arrive in the same clock phase. These inherent characteristics present substantial challenges in the design of RQFP logic circuits. To address these challenges, this article proposes an automatic synthesis framework for RQFP logic circuit design based on efficient Cartesian genetic programming (CGP). The framework aims to minimize both the number of RQFP logic gates and the number of garbage outputs within the generated RQFP logic circuit. It incorporates the specific characteristics of the RQFP logic circuit by encoding them into the genotype of a CGP individual. It also introduces several point mutation operations to facilitate the generation of new individuals. Furthermore, the framework integrates circuit simulation with formal verification to assess the functional equivalence between the parent and its offspring. Experimental results on RevLib and reversible reciprocal circuit benchmarks demonstrate the effectiveness of our framework.

As conventional computing technologies approach their physical limits, the quest for increased computational power intensifies, heightening interest in post-CMOS technologies. Among these, Field-coupled Nanocomputing (FCN), which operates through the repulsion of physical fields at the nanoscale, emerges as a promising alternative. However, realizing specific functionalities within this technology necessitates the development of dedicated FCN physical design methods. Although various methods have been proposed, their reliance on heuristic approaches often results in suboptimal quality, highlighting a significant opportunity for enhancement. In the realm of conventional CMOS design, post-layout optimization techniques are employed to capitalize on this potential, yet such methods for FCN are either not scalable or lack efficiency. This work bridges this gap by introducing the first scalable and efficient post-layout optimization algorithm for FCN. Experimental evaluations demonstrate the efficiency of this approach: when applied to layouts obtained by a state-of-the-art heuristic method, the proposed post-layout optimization achieves area reductions of up to$ {\mathrm {73.75~\%}}~({\mathrm {45.58~\%}}$on average). This significant improvement underscores the transformative potential of post-layout optimization in FCN. Moreover, unlike existing algorithms, the method exhibits scalability even in optimizing layouts with over 20 million tiles. Implementations of the proposed methods are publicly available as part of the Munich Nanotech Toolkit (MNT) athttps://github.com/cda-tum/fiction.

Trapped-ion quantum computers exhibit promising potential to provide platforms for high-quality qubits and reliable quantum computation. The quantum charge coupled device (QCCD) architecture is a leading example that offers a modular solution to enable the realization of scalable quantum computers, paving the way for practical quantum algorithms with large qubit numbers. Within these devices, ions can be shuttled (moved) throughout the trap and through different dedicated zones, e.g., a memory zone for storage and a processing zone for the actual computation. However, due to decoherence of the ions’ quantum states, the qubits lose their quantum information over time. Thus, the required time steps of shuttling operations should be minimized. In this work,1 we propose a heuristic approach to determining an efficient shuttling schedule, which orchestrates the movement operations within the device. Given a quantum algorithm and a device architecture, the proposed approach produces shuttling schedules with a close-to-minimal amount of time steps for small-size QCCD architectures. For large-scale QCCD devices, empirical evaluations show promising results with respect to quality of the solution as well as performance. An implementation of the proposed approach is publicly available as part of the open-source Munich Quantum Toolkit (MQT) athttps://github.com/cda-tum/mqt-ion-shuttler.

The design of microfluidic devices, i.e., Lab-on-Chips (LoCs) or Micro Total Analysis Systems ($\mu $TASs), is a tedious and cumbersome process with many time-consuming and costly fabrication cycles. Many of these devices contain dissolved species (i.e., solutes) that are required to appear in the system at specific predefined concentrations. The use of simulations can aid the design process of microfluidic devices. However, methods from Computational Fluid Dynamics (CFDs), which are commonly used, are computationally costly and require a lot of time to finish. In this work, we present a simulator for species concentrations in channel-based microfluidic devices that operates on a higher level of abstraction and is multiple orders of magnitude faster than CFD simulation methods. The simulator has been implemented in C++ and is benchmarked against CFD simulations as well as against measured results from experiments on a fabricated device. The results are analyzed and the applicability of the simulator for the simulation of microfluidic devices is assessed.

Efficient methods for the simulation of quantum circuits on classical computers are crucial for their analysis due to the exponential growth of the problem size with the number of qubits. Here we study lumping methods based on bisimulation, an established class of techniques that has been proven successful for (classic) stochastic and deterministic systems such as Markov chains and ordinary differential equations. Forward constrained bisimulation yields a lower-dimensional model which exactly preserves quantum measurements projected on a linear subspace of interest. Backward constrained bisimulation gives a reduction that is valid on a subspace containing the circuit input, from which the circuit result can be fully recovered. We provide an algorithm to compute the constraint bisimulations yielding coarsest reductions in both cases, using a duality result relating the two notions. As applications, we provide theoretical bounds on the size of the reduced state space for well-known quantum algorithms for search, optimization, and factorization. Using a prototype implementation, we report significant reductions on a set of benchmarks. In particular, we show that constrained bisimulation can boost decision-diagram-based quantum circuit simulation by several orders of magnitude, allowing thus for substantial synergy effects.

Fueled by recent accomplishments in quantum computing hardware and software, an increasing number of problems from various application domains are being explored as potential use cases for this new technology. Similarly to classical computing, realizing an application on a particular quantum device requires the corresponding (quantum) circuit to be compiled so that it can be executed on the device. With a steadily growing number of available devices—each with their own advantages and disadvantages—and a wide variety of different compilation tools, the number of choices to consider when trying to realize an application is quickly exploding. Due to missing tool support and automation, especially end-users who are not quantum computing experts are easily left unsupported and overwhelmed. In this work, we propose a methodology that allows one to automatically select a suitable quantum device for a particular application and provides an optimized compiler for the selected device. The resulting framework—called the MQT Predictor —not only supports end-users in navigating the vast landscape of choices, it also allows mixing and matching compiler passes from various tools to create optimized compilers that transcend the individual tools. Evaluations of an exemplary framework instantiation based on more than 500 quantum circuits and seven devices have shown that—compared with both Qiskit’s and TKET’s most optimized compilation flows for all devices—the MQT Predictor produces circuits within the top-3 out of 14 baselines in more than 98% of cases while frequently outperforming any tested combination by up to 53% when optimizing for expected fidelity . Additionally, the framework is trained and evaluated for critical depth as another figure of merit to showcase its flexibility and generalizability—producing circuits within the top-3 in 89% of cases while frequently outperforming any tested combination by up to 400%. MQT Predictor is part of the Munich Quantum Toolkit (MQT) and publicly available as open-source on GitHub ( https://github.com/cda-tum/mqt-predictor ) and as an easy-to-use Python package ( https://pypi.org/p/mqt.predictor ).

The Silicon Dangling Bond (SiDB) logic platform, an emerging computational beyond-CMOS nanotechnology, is a promising competitor due to its ability to achieve integration density and clock speed values that are several orders of magnitude higher compared to current CMOS fabrication nodes. However, the exact physical simulation of SiDB layouts, which is an essential component of any design validation workflow, is computationally expensive. In this paper, we propose a novel algorithm called QuickExact, which aims to be both, efficient and exact. To this end, we are introducing three techniques, namely 1) Physically-informed Search Space Pruning, 2) Partial Solution Caching, and 3) Effective State Enumeration. Extensive experimental evaluations confirm that, compared to the state-of-the-art algorithm, the resulting approach leads to a paramount runtime advantage of more than a factor of 5000 on randomly generated layouts and more than a factor of 2000 on an established gate library.

Trapped ions are a promising technology for building scalable quantum computers. Not only can they provide a high qubit quality, but they also enable modular architectures, referred to as Quantum Charge Coupled Device (QCCD) architecture. Within these devices, ions can be shuttled (moved) throughout the trap and through different dedicated zones, e.g., a memory zone for storage and a processing zone for the actual computation. However, this movement incurs a cost in terms of required time steps, which increases the probability of decoherence, and, thus, should be minimized. In this paper, we propose a formalization of the possible movements in ion traps via Boolean satisfiability. This formalization allows for determining the minimal number of time steps needed for a given quantum algorithm and device architecture, hence reducing the decoherence probability. An empirical evaluation confirms that—using the proposed approach—minimal results (i.e., the lower bound) can be determined for the first time. An open-source implementation of the proposed approach is publicly available at https://github.com/cda-tum/mqt-ion-shuttler.

Increasing the capacity of our railway infrastructure will become more and more essential in coping with the need for sustainable transportation. This can be achieved by intelligently implementing train control systems on specific railway networks. Methods that automate and optimize parts of this planning process are of great interest. For control systems based on hybrid train detection, such optimization tasks simultaneously involve routing and block layout generation. These tasks are already complex on their own; hence, a joint consideration often becomes infeasible. This work-in-progress paper proposes an idea to tackle the corresponding complexity. To this end, we present a pipeline that allows to sequentially handle corresponding optimization tasks in a less complex fashion while generating results that remain (close to) optimal. Results from an initial case study showcase that this approach is, indeed, promising. A prototypical implementation is included in the open-source Munich Train Control Toolkit available at https://github.com/cda-tum/mtct.

Reversible computing has gained increasing attention as a prospective solution for energy dissipation, particularly in quantum computing. As the first practical reversible logic gate using adiabatic superconducting devices, the reversible quantum-flux-parametron (RQFP) has been experimentally demonstrated in logical and physical reversibility. However, the circuit design of RQFP logic poses enormous challenges due to its distinctive logic function and structure. Furthermore, the circuit scale severely restricts the applicability of the existing exact logic synthesis method for RQFP logic. Therefore, this paper proposes RCGP, an automatic synthesis framework based on efficient Cartesian genetic programming, to generate large RQFP logic circuits. RCGP considers the characteristics of RQFP logic circuits to minimize the number of gates and garbage outputs. Meanwhile, RCGP combines circuit simulation with formal verification to assess the functional equivalence between the parent and its offspring. Experimental results on reversible logic benchmarks demonstrate the effectiveness of RCGP.

The emergence of Field-coupled Nanocomputing (FCN) as a green and atomically-sized post-CMOS technology introduces a unique challenge for the development of physical design methods: unlike conventional computing, wire segments in FCN entail the same area and delay costs as standard gates. Hence, it is imperative to reconsider physical design strategies tailored for FCN to effectively address this distinctive characteristic. This paper unveils a recent breakthrough in minimizing the number of wire segments by an average of 20.13 %, which, due to the high cost associated with wires, also leads to an average decrease of 34.10 % in overall area and 19.84 % in critical path length. Furthermore, unlike existing post-layout optimization algorithms, the proposed method maintains scalability even for layouts encompassing millions of tiles.

Quantum computers have the potential to solve important problems which are fundamentally intractable on a classical computer. The underlying physics of quantum computing platforms supports using multi-valued logic, which promises a boost in performance over the prevailing two-level logic. One key element to exploiting this potential is the capability to efficiently prepare quantum states for multi-valued, or qudit, systems. Due to the time sensitivity of quantum computers, the circuits to prepare the required states have to be as short as possible. In this paper, we investigate quantum state preparation with a focus on mixed-dimensional systems, where the individual qudits may have different dimensionalities. The proposed approach automatically realizes quantum circuits constructing a corresponding mixed-dimensional quantum state. To this end, decision diagrams are used as a compact representation of the quantum state to be realized. We further incorporate the ability to approximate the quantum state to enable a finely controlled trade-off between accuracy, memory complexity, and number of operations in the circuit. Empirical evaluations demonstrate the effectiveness of the proposed approach in facilitating fast and scalable quantum state preparation, with performance directly linked to the size of the decision diagram. The implementation is freely available as part of Munich Quantum Toolkit (MQT) at github.com/cda-tum/mqt-qudits.

Quantum computing based on Neutral Atoms (NAs) provides a wide range of computational capabilities, encompassing high-fidelity long-range interactions with native multi-qubit gates and the ability to shuttle arrays of qubits. While, previously, these capabilities have been studied individually, we propose a fast hybrid compiler to perform circuit mapping and routing utilizing both high-fidelity gate interactions and qubit shuttling. We delve into the intricacies of the compilation process when combining multiple capabilities and present effective solutions to address the resulting challenges. The final compilation strategy is then showcased across various hardware settings, revealing its versatility, and highlighting potential fidelity enhancements achieved through the strategic utilization of combined gate- and shuttling-based routing. With the additional multi-qubit gate support for both routing capabilities, the proposed approach is able to take advantage of the full spectrum of computational capabilities offered by NAs.

Design, simulation, analysis and verification methodologies are crucial for developing electronic circuits and systems at large. Whereas long-standing EDA software is used in the semiconductor technology, there is no counterpart for quantum computing systems yet. Although the quantum computing community started utilizing and adapting some of the already existing EDA tools, for instance, to design quantum processors and control electronics for driving the qubits, or even to solve some quantum computing design tasks, they do not fully use the expertise gained over the last decades in the field of design automation. Current intermediate-scale quantum computers have been designed in an ‘adhoc’ manner with heterogeneous methods and tools. As we are entering the large-scale era, it is timely and key to further adopt EDA methodologies and software for quantum computing. In this paper, we provide an overview on how full-stack quantum computing systems are being implemented nowadays and discuss which the main challenges are for transitioning from this current scenario to a comprehensive framework encompassing full automated system-wide architecting, design, simulation, verification, and test.

Organs-on-Chips (OoCs) are testing platforms for the phar-maceutical, cosmetic, and chemical industries. They are composed of miniaturized organ tissues (so-called organ modules) that are connected via a microfluidic channel network and, by this, emulate human or other animal physiology on a miniaturized chip. The design of those chips, however, requires a sophisticated orchestration of numerous aspects, such as the size of organ modules, the required shear stress on membranes, the dimensions and geometry of channels, pump pressures, etc. Mastering all this constitutes a non-trivial design task for which, unfortunately, no automatic support exists yet. In this work, we propose a first design automation solution for OoCs. To this end, we review the respective design steps and formalize a corresponding design specification from it. Based on that, we then propose an automatic method which generates a design of the desired device. Evaluations (inspired by real-world use cases and confirmed by CFD simulations) demonstrate the applicability and validity of the proposed approach.

To increase the capacity of existing railway infras-tructure, the European Train Control System (ETCS) allows the introduction of virtual subsections. As of today, the planning of such systems is mainly done by hand. Previous design automation methods suffer from long runtimes in certain instances. However, late breaking results show that these methods can highly benefit from an iterative approach. An initial implementation of the resulting method is available in open-source as part of the Munich Train Control Toolkit at https://github.com/cda-tum/rntct.

As Field-coupled Nanocomputing (FCN) gains traction as a viable post-CMOS technology, the EDA community lacks public benchmarks to evaluate the performance of academic and commercial design tools. We propose MNT Bench to address this gap by providing a platform for researchers to compare algorithms across a diverse set of benchmarks generated by multiple physical design tools. These benchmarks span various clocking schemes and gate libraries, with MNT Bench being consistently updated to integrate the latest advancements in the field. In fact, using MNT Bench, we were able to provide layouts that are substantially better (in terms of area) than everything the community generated thus far.

The Quantum Charge Coupled Device (QCCD) architecture offers a modular solution to enable the realization of trappedion quantum computers with a large number of qubits. Within these devices, ions can be shuttled (moved) throughout the trap and through different dedicated zones. However, due to decoherence of the ions' quantum states, the qubits lose their quantum information over time. Thus, the shuttling needed for these shuttling operations should be minimized. In this extended abstract, we propose a concept towards a cycle-based heuristic approach to determining an efficient shuttling schedule for a given quantum circuit.

Recent advancements in Silicon Dangling Bond (SiDB) fabrication have transitioned from manual to automated processes. However, sub-nanometer substrate defects remain a significant challenge, thus preventing the fabrication of functional logic. Current design automation techniques lack defect-aware strategies. This paper introduces an idea for a surface defect model based on experimentally verified defects, which can be applied to enhance the robustness of established gate libraries. Additionally, a prototypical automatic placement and routing algorithm is presented, utilizing STM data from physical experiments to obtain dot- accurate circuitry resilient to atomic surface defects. Initial evaluations on surfaces with varying defect rates demonstrate their critical impact, suggesting that fabrication processes must achieve defect rates of around 0.1 % to further advance this circuit technology.

We are at the dawn of a new “computing age” in which quantum computers hopefully will find their way into practical applications. However, while impressive accomplishments can be observed in the physical realization of quantum computers, the development of automated tools and methods that provide assistance in the design and realization of applications for those devices is at risk of not being able to keep up with this development anymore-leaving a situation where we might have powerful quantum computers but hardly any proper means to actually use them. The ERC Consolidator project “Design Automation for Quan-tum Computing” aims to provide a solution for this upcoming design gap by developing efficient and practically relevant de-sign methods for this emerging technology. While the current state of the art suffers from the interdisciplinarity of quantum computing (leading to the consideration of inappropriate models, inconsistent interpretations, and “wrong” problem formulations), this project builds a bridge between the design automation community and the quantum computing community. This will allow to fully exploit the potential of design automation which is hardly utilized in quantum computing yet. This intermediate stage report provides an overview of the motivation and approach of the project as well as showcases selected results and outreach activities conducted in the first two years of the project.

Railroad transportation plays a vital role in the future of sustainable mobility.Besides building new infrastructure, capacity can be improved by modern train control systems, e.g., based on moving blocks.At the same time, there is only limited work on how to optimally route trains using the potential gained by these systems.Recently, an initial approach for train routing with moving block control has been proposed to address this demand.However, detailed evaluations on so-called lazy constraints are missing, and no publicly available implementation exists.In this work, we close this gap by providing an extended approach as well as a flexible open-source implementation that can use different solving strategies.Using that, we experimentally evaluate what choices should be made when implementing a lazy constraint approach.The corresponding implementation and benchmarks are publicly available as part of the Munich Train Control Toolkit (MTCT) at https://github.com/cda-tum/mtct.

393

Quantum circuit simulator (QCS) is essential for designing quantum algorithms because it assists researchers in understanding how quantum operations work without access to expensive quantum computers. Traditional array-based QCSs suffer from exponential time and memory complexities. To address this problem, Decision Diagram (DD) was introduced to compress simulation data by exploring the circuit regularity. However, for irregular circuit structures, DD-based simulation incurs significant runtime and memory overhead. To overcome this challenge, we present FlatDD, a high-performance QCS that capitalizes on the strength of both DD- and array-based approaches. FlatDD parallelizes the simulation workload at multiple levels and leverages an efficient caching technique to reuse historical results. To further enhance the simulation performance for deep circuits, FlatDD introduces a gate-fusion algorithm to reduce the computational cost. Compared to state-of-the-art QCSs on commonly used quantum circuits, FlatDD achieves 34.81× speed-up and 1.93× memory reduction.

Depth estimation is critical in autonomous driving for interpreting 3D scenes accurately. Recently, radar-camera depth estimation has become of sufficient interest due to the robustness and low-cost properties of radar. Thus, this paper introduces a two-stage, end-to-end trainable Confidence-aware Fusion Net (CaFNet) for dense depth estimation, combining RGB imagery with sparse and noisy radar point cloud data. The first stage addresses radar-specific challenges, such as ambiguous elevation and noisy measurements, by predicting a radar confidence map and a preliminary coarse depth map. A novel approach is presented for generating the ground truth for the confidence map, which involves associating each radar point with its corresponding object to identify potential projection surfaces. These maps, together with the initial radar input, are processed by a second encoder. For the final depth estimation, we innovate a confidence-aware gated fusion mechanism to integrate radar and image features effectively, thereby enhancing the reliability of the depth map by filtering out radar noise. Our methodology, evaluated on the nuScenes dataset, demonstrates superior performance, improving upon the current leading model by 3.2% in Mean Absolute Error (MAE) and 2.7% in Root Mean Square Error (RMSE). Code: https://github.com/harborsarah/CaFNet

Radar and camera fusion yields robustness in perception tasks by leveraging the strength of both sensors. The typical extracted radar point cloud is 2D without height information due to insufficient antennas along the elevation axis, which challenges the network performance. This work introduces a learning-based approach to infer the height of radar points associated with 3D objects. A novel robust regression loss is introduced to address the sparse target challenge. In addition, a multi-task training strategy is employed, emphasizing important features. The average radar absolute height error decreases from 1.69 to 0.25 meters compared to the state-of-the-art height extension method. The estimated target height values are used to preprocess and enrich radar data for downstream perception tasks. Integrating this refined radar information further enhances the performance of existing radar camera fusion models for object detection and depth estimation tasks.

Abstract. Field-Programmable Gate Arrays (FPGAs) employ a large number of SRAM cells to provide a flexible routing architecture which have a significant impact on the FPGA’s area and power consumption. This flexible routing allows for a rather easy realization of the desired functionality, but our evaluations show that the full routing flexibility is not required in many occasions. In this work, we focus on what is actually needed and introduce a new switch-box realization what we call Turn-Restricted Switch-Boxes which supports only a subset of possible turns. The proposed method increases the utilization rate of FPGA switch-boxes by eliminating the unemployed resources. Experimental evaluations confirm that the area and average power consumption can be reduced by 12.8% and 14.1%, on average, respectively and the FPGA routing susceptibility to SEU and MBU can be improved by 18.2%, on average, by imposing negligible performance. 1

Quantum programming languages support the design of quantum applications. However, to create such programs, one needs to understand the fundamental characteristics of quantum computing and quantum information theory. Furthermore, quantum algorithms frequently make use of abstract operations with a hidden low-level realization (e.g., Quantum Fourier Transform). Thus, turning from elementary quantum operations to a higher-level view of quantum circuit design not only reduces the development effort but also lowers the entry barriers for non-quantum computing experts. To this end, this article proposes a modeling language and design framework for quantum circuits. This allows the definition of composite operators to advocate a higher-level quantum algorithm design, together with automated code generation for the circuit execution. To demonstrate the benefits of the proposed approach, coined Composition-based Quantum Circuit Designer , we applied it for realizing the Quantum Counting algorithm and the Quantum Approximate Optimization Algorithm. Our evaluation results show that, compared to an existing state-of-the-art editor, the proposed approach allows for the realization of both quantum algorithms on a high level with a substantially reduced development effort. In particular, the proposed approach shows constant scaling when increasing the size of the investigated quantum circuits and a lower change criticality when evolving existing quantum circuits.

Quantum Error Correction (QEC) is an essential field of research towards the realization of large-scale quantum computers. On the theoretical side, a lot of effort is put into designing error-correcting codes that protect quantum data from errors, which inevitably happen due to the noisy nature of quantum hardware and quantum bits (qubits). Protecting data with an error-correcting code necessitates means to recover the original data, given a potentially corrupted data set---a task referred to as decoding. It is vital that decoding algorithms can recover error-free states in an efficient manner. While theoretical properties of certain QEC methods have been extensively studied, good techniques to analyze their performance in practically more relevant settings is still a widely unexplored area. In this work, we propose a set of software tools that facilitate numerical experiments with so-called Quantum Low-Density Parity-Check codes (QLDPC codes)---a broad class of codes, some of which have recently been shown to be asymptotically good. Based on that, we provide an implementation of a general decoder for QLDPC codes. On top of that, we propose a highly efficient heuristic decoder that eliminates the runtime bottlenecks of the general QLDPC decoder while still maintaining comparable decoding performance. These tools eventually make it possible to confirm theoretical results around QLDPC codes in a more practical setting and showcase the value of software tools (in addition to theoretical considerations) for investigating codes for practical applications. The resulting tool, which is publicly available at https://github.com/cda-tum/qecc as part of the Munich Quantum Toolkit (MQT), is meant to provide a playground for the search for "practically good" quantum codes.

Today, the verification of classical circuits poses a severe challenge for the design of circuits and systems. While the underlying (exponential) complexity is tackled in various fashions (simulation-based approaches, emulation, formal equivalence checking, fuzzing, model checking, etc.), no "silver bullet" has been found yet which allows to escape the growing verification gap. In this work, we entertain and investigate the idea of a complementary approach which aims at exploiting reversible computing. More precisely, we show the potential of the reversible computing paradigm for verification, debunk misleading paths that do not allow to exploit this potential, and discuss the resulting consequences for the development of future, complementary design and verification flows. An extensive empirical study (involving more than 30 million simulations) confirms these findings. Although this work cannot provide a fully-fledged realization yet, it may provide the basis for an alternative path towards overcoming the verification gap.

Most quantum computing architectures to date natively support multi-valued logic, albeit being typically operated in a binary fashion. Multi-valued, or qudit, quantum processors have access to much richer forms of quantum entanglement, which promise to significantly boost the performance and usefulness of quantum devices. However, much of the theory as well as corresponding design methods required for exploiting such hardware remain insufficient and generalizations from qubits are not straightforward. A particular challenge is the compilation of quantum circuits into sets of native qudit gates supported by state-of-the-art quantum hardware. In this work, we address this challenge by introducing a complete workflow for compiling any two-qudit unitary into an arbitrary native gate set. Case studies demonstrate the feasibility of both, the proposed approach as well as the corresponding implementation (which is freely available at github.com/cda-tum/qudit-entanglement-compilation).

Variational quantum algorithms have been introduced as a promising class of quantum-classical hybrid algorithms that can already be used with the noisy quantum computing hardware available today by employing parameterized quantum circuits. Considering the non-trivial nature of quantum circuit compilation and the subtleties of quantum computing, it is essential to verify that these parameterized circuits have been compiled correctly. Established equivalence checking procedures that handle parameter-free circuits already exist. However, no methodology capable of handling circuits with parameters has been proposed yet. This work fills this gap by showing that verifying the equivalence of parameterized circuits can be achieved in a purely symbolic fashion using an equivalence checking approach based on the ZX-calculus. At the same time, proofs of inequality can be efficiently obtained with conventional methods by taking advantage of the degrees of freedom inherent to parameterized circuits. We implemented the corresponding methods and proved that the resulting methodology is complete. Experimental evaluations (using the entire parametric ansatz circuit library provided by Qiskit as benchmarks) demonstrate the efficacy of the proposed approach.

Executing quantum algorithms on a quantum computer requires compilation to representations that conform to all restrictions imposed by the device. Due to devices' limited coherence times and gate fidelities, the compilation process has to be optimized as much as possible. To this end, an algorithm's description first has to be synthesized using the device's gate library. In this paper, we consider the optimal synthesis of Clifford circuits---an important subclass of quantum circuits, with various applications. Such techniques are essential to establish lower bounds for (heuristic) synthesis methods and gauging their performance. Due to the huge search space, existing optimal techniques are limited to a maximum of six qubits. The contribution of this work is twofold: First, we propose an optimal synthesis method for Clifford circuits based on encoding the task as a satisfiability (SAT) problem and solving it using a SAT solver in conjunction with a binary search scheme. The resulting tool is demonstrated to synthesize optimal circuits for up to 26 qubits---more than four times as many as the current state of the art. Second, we experimentally show that the overhead introduced by state-of-the-art heuristics exceeds the lower bound by 27 % on average. The resulting tool is publicly available at https://github.com/cda-tum/qmap.

Recent breakthroughs in atomically precise manufacturing are paving the way for Field-coupled Nanocomputing (FCN) to become a real-world post-CMOS technology. This drives the need for efficient and scalable physical design automation methods. However, due to the problem’s NP-completeness, existing solutions either generate designs of high quality, but are not scalable, or generate designs in negligible time but of poor quality. In an attempt to balance scalability and quality, we created and evaluated a hybrid approach that combines the best of established design methods and deep reinforcement learning. This paper summarizes the obtained results.

Any quantum computing application, once encoded as a quantum circuit, must be compiled before being executable on a quantum computer. Similar to classical compilation, quantum compilation is a sequential process with many compilation steps and numerous possible optimization passes. Despite the similarities, the development of compilers for quantum computing is still in its infancy—lacking mutual consolidation on the best sequence of passes, compatibility, adaptability, and flexibility. In this work, we take advantage of decades of classical compiler optimization and propose a reinforcement learning framework for developing optimized quantum circuit compilation flows. Through distinct constraints and a unifying interface, the framework supports the combination of techniques from different compilers and optimization tools in a single compilation flow. Experimental evaluations show that the proposed framework—set up with a selection of compilation passes from IBM’s Qiskit and Quantinuum’s TKET—significantly outperforms both individual compilers in 73% of cases regarding the expected fidelity. The framework is available on GitHub (https://github.com/cda-tum/MQTPredictor) as part of the Munich Quantum Toolkit (MQT).

Cryogenic CMOS circuits operate at temperatures close to absolute zero and are essential in many applications such as controllers for quantum computing but also medical engineering, space technology, or physical instruments. However, operating circuits at cryogenic temperatures fundamentally changes the underlying semiconductor physics that governs the CMOS transistor—rendering existing design automation approaches infeasible. In this work, we propose and implement the first end-to-end approach that enables design automation for cryogenic CMOS circuits. To this end, we (1) perform the first-of-its-kind measurements of commercial 5nm FinFET transistors from 300K down to 10K, (2) use the results to validate and calibrate the first cryogenic-aware industrial-standard compact model for FinFET technology, (3) create cryogenic-aware standard cell libraries that are compatible with the existing EDA tool flows, and (4) propose an initial cryogenic-aware logic synthesis approach that re-uses established design automation expertise but optimizes it for cryogenic purposes. Evaluations, comparisons, and discussions of all these novel contributions confirm the applicability and validity of the resulting cryogenic-aware design automation flow.

Microfluidics is an emerging technology that is expected to revolutionize biochemical experiments and reduce the need for unwieldy laboratory equipment. Motivated by that, the design automation community has spent considerable efforts and proposed numerous methods on automating the design process for corresponding microfluidic devices. For many of them, however, it often remains unclear whether the (automatically) generated design indeed works as intended and/or satisfies its purpose. Simulations, e.g., based on Computational Fluid Dynam-ics (CFD) can help here as they allow for studying the behavior of microfluidic devices without the need for actual fabrication. However, the setup and configuration of CFD simulations is time-consuming and requires extensive expertise-some of the reasons why it is hardly utilized in the design automation community yet. In this work, we propose a workflow that improves upon this state of the art by automating intermediate steps and highlighting the parameters that are relevant to the specific use case. We demonstrate the feasibility of the proposed workflow for fluid mixing in channel-based microfluidics.

Channel-based microfluidic devices, often in the form of so-called Lab-on-a-Chip (LoC), have a broad range of applications in domains such as biology, chemistry, medicine, etc. Many of these applications rely on merging of droplets, e.g., in order to trigger some kind of reaction inside the droplets. However, the design process of LoCs is, in general, still in its infancy and mostly relies on simplifications, assumptions, as well as the expertise of the designer-making this process rather error-prone and frequently resulting in a “trial-and-error” approach. Simulation tools can help in this regard. While Computational Fluid Dynamics (CFD) tools can simulate the merging of droplets, their complex setup and computational efforts limit their applicability to rather small components and do not allow simulations of larger microfluidic devices. Instead, considerations on the so-called one-dimensional model (1D model) offer a more abstract and, hence, computationally much faster simulation. However, currently there are no simulators based on the 1D model available that support the merging of droplets-severely restricting the applicability of such simulators. In this work, we address this problem by proposing a concept for droplet merging based on the 1D-model and implementing these ideas on top of an already existing 1D-simulator. The resulting simulator (which is made publicly available as part of the Munich Microfluidics Toolkit (MMFT)) eventually allows for the efficient simulation of channel-based microfluidic devices where droplet merging is an essential part.

Recent years have shown that we are steadily getting closer to industrial applications of quantum computing. As such it is important to teach quantum computing concepts to users to allow them to incorporate quantum computing into their toolbox. As educational research has shown the potential of game-based learning in the past years, we are thus proposing QRogue, an educational game with Rogue-like elements targeted at computer science students. The game’s goal is to teach the math behind quantum computing in a playful environment with analogies to this technology’s counter-intuitive fundamentals. To gather first feedback and stir the further development, we conducted a user study – involving playtesting and a post-experience survey – with eight students showing that the game was positively received but requires further tuning of the onboarding process and of the in-game feedback provided to players.

Data selection is essential for any data-based optimization technique, such as Reinforcement Learning. State-of-the-art sampling strategies for the experience replay buffer improve the performance of the Reinforcement Learning agent. However, they do not incorporate uncertainty in the Q-Value estimation. Consequently, they cannot adapt the sampling strategies, including exploration and exploitation of transitions, to the complexity of the task. To address this, this paper proposes a new sampling strategy that leverages the exploration-exploitation trade-off. This is enabled by the uncertainty estimation of the Q-Value function, which guides the sampling to explore more significant transitions and, thus, learn a more efficient policy. Experiments on classical control environments demonstrate stable results across various environments. They show that the proposed method outperforms state-of-the-art sampling strategies for dense rewards w.r.t. convergence and peak performance by 26% on average.

Quantum computing is an emerging technology that has the potential to revolutionize fields such as cryptography, machine learning, optimization, and quantum simulation. However, a major challenge in the realization of quantum algorithms on actual machines is ensuring that the gates in a quantum circuit (i.e., corresponding operations) match the topology of a targeted architecture so that the circuit can be executed while, at the same time, the resulting costs (e.g., in terms of the number of additionally introduced gates, fidelity, etc.) are kept low. This is known as the quantum circuit mapping problem. This summary paper provides an overview of QMAP-an open-source tool that is part of the Munich Quantum Toolkit (MQT) and offers efficient, automated, and accessible methods for tackling this problem. To this end, the paper first briefly reviews the problem. Afterwards, it shows how QMAP can be used to efficiently map quantum circuits to quantum computing architectures from both a user's and a developer's perspective. QMAP is publicly available as open-source at https://github.com/cda-tum/qmap.

Abstract In many industrial or healthcare contexts, keeping track of the number of people is essential. Radar systems, with their low overall cost and power consumption, enable privacy-friendly monitoring in many use cases. Yet, radar data are hard to interpret and incompatible with most computer vision strategies. Many current deep learning-based systems achieve high monitoring performance but are strongly context-dependent. In this work, we show how context generalization approaches can let the monitoring system fit unseen radar scenarios without adaptation steps. We collect data via a 60 GHz frequency-modulated continuous wave in three office rooms with up to three people and preprocess them in the frequency domain. Then, using meta learning, specifically the Weighting-Injection Net, we generate relationship scores between the few training datasets and query data. We further present an optimization-based approach coupled with weighting networks that can increase the training stability when only very few training examples are available. Finally, we use pool-based sampling active learning to fine-tune the model in new scenarios, labeling only the most uncertain data. Without adaptation needs, we achieve over 80% and 70% accuracy by testing the meta learning algorithms in new radar positions and a new office, respectively. Graphical abstract

This article presents a systematic mapping study on the model-driven engineering of safety and security concerns in software systems. Combined modeling and development of both safety and security concerns is an emerging field of research as both concerns affect one another in unique ways. Our mapping study provides an overview of the current state of the art in this field. This study carefully selected 143 publications out of 27,259 relevant papers through a rigorous and systematic process. This study then proposes and answers questions such as frequently used methods and tools and development stages where these concerns are typically investigated in application domains. Additionally, we identify the community's preference for publication venues and trends. The discussion on obtained results also features the gained insights and future research directions.

Simulating quantum circuits on classical computers is a notoriously hard, yet increasingly important task for the development and testing of quantum algorithms. In order to alleviate this inherent complexity, efficient data structures and methods, such as tensor networks and decision diagrams, have been proposed. However, their efficiency heavily depends on the order in which the individual computations are performed. For tensor networks, the order is defined by so-called contraction plans and a plethora of methods has been developed to determine suitable plans. On the other hand, simulation based on decision diagrams is mostly conducted in a straight-forward, i.e., sequential, fashion thus far. In this work, we study the importance of the path that is chosen when simulating quantum circuits using decision diagrams and show, conceptually and experimentally, that choosing the right simulation path can make a vast difference in the efficiency of classical simulations using decision diagrams. We propose an open-source framework (available at github.com/cda-tum/ddsim) that not only allows to investigate of dedicated simulation paths but also to reuse of existing findings, e.g., obtained from determining contraction plans for tensor networks. Experimental evaluations show that translating strategies from the domain of tensor networks may yield speedups of several factors compared to the state of the art. Furthermore, we design a dedicated simulation path heuristic that allows to improve the performance even further—frequently yielding speedups of several orders of magnitude. Finally, we provide an extensive discussion on what can be learned from tensor networks and what cannot.

Microfluidics is a technology that enables moving analytic processes from expensive and bulky laboratory equipment to small-scale devices. Microfluidic devices, usually in the form of labs-on-a-chips (LoCs), have found many great applications in medicine, biology, and chemistry. In particular, LoCs that utilize channels to transport fluids or droplets between different components on the chip are a promising technology. However, the design process of such channel-based LoCs is in need of further automation efforts since the underlying design steps are still rather complex and conducted mainly by hand. An important task in microfluidic design automation is the so-called channel routing, where components on LoCs are connected by microfluidic channels. Methods that aim to automate this routing task must factor in the specific demands of microfluidic devices. Common requirements for microfluidic routing layouts are to prevent sharp channel bends and to realize a particular length of channels. Unfortunately, most of the available routing algorithms address these requirements only partly and insufficiently. In this work, we propose a router that is able to overcome these shortcomings and allows automatic channel routing with a minimal bending radius as well as a desired length. In order to make the router accessible to users with little to no design automation expertise, the solution is implemented as an online tool with a user-friendly and intuitive interface. The resulting tool can be accessed athttps://www.cda.cit.tum.de/research/microfluidics/channel_router/.

Since quantum computers can solve important problems faster than classical computers, many resources have gone into the development of this technology in recent decades. Despite the tremendous progress that has already been made toward the development of quantum computers, they are still an emerging technology, which restricts access and reliability. Thus, research on quantum algorithms still heavily relies on quantum circuit simulators that run on classical hardware. However, simulating the execution of a quantum computer on conventional hardware is exponentially difficult, which is also the reason why quantum computing is an interesting technology in the first place. Particularly complex is noise-aware simulation of quantum computers, i.e., the consideration of noise effects that are common in today’s quantum hardware during quantum circuit simulation. In this work, we investigate the use of decision diagrams for this task. To this end, we present two distinct approaches for noise-aware quantum circuit simulation, investigate how they can be realized using decision diagrams, and implement decision diagram-based solutions for each of the presented noise-aware simulation schemes. In an extensive evaluation, we unveil potential for further improvements and also demonstrate substantial speed-ups compared to the current state of the art.

Owing to the high complexity of chip architecture and assay protocol, considerable effort has been directed toward the design automation of continuous-flow microfluidics over the past decade. Existing methods, however, perform the corresponding design tasks, including binding, scheduling, placement, and routing separately, leading to serious gaps between different steps and potentially even cause design failure. To overcome these drawbacks, in this article, we propose a one-pass design paradigm for continuous-flow microfluidic lab-on-a-chip systems, integrating all the design steps into an “organic whole,” which has never been considered in prior work. With the proposed paradigm, all the design tasks can be synchronized seamlessly and performed in a combined manner, thereby eliminating the gaps between design steps. Consequently, optimized biochip architectures can be generated without any design adjustments and modifications. The experimental results demonstrate the effectiveness of the proposed automation flows.

Driven by Moore’s law, the chip design complexity is steadily increasing. Electronic Design Automation (EDA) has been able to cope with the challenging very large-scale integration process, assuring scalability, reliability, and proper time-to-market. However, EDA approaches are time and resource demanding, and they often do not guarantee optimal solutions. To alleviate these, Machine Learning (ML) has been incorporated into many stages of the design flow, such as in placement and routing. Many solutions employ Euclidean data and ML techniques without considering that many EDA objects are represented naturally as graphs. The trending Graph Neural Networks (GNNs) are an opportunity to solve EDA problems directly using graph structures for circuits, intermediate Register Transfer Levels, and netlists. In this article, we present a comprehensive review of the existing works linking the EDA flow for chip design and GNNs. We map those works to a design pipeline by defining graphs, tasks, and model types. Furthermore, we analyze their practical implications and outcomes. We conclude by summarizing challenges faced when applying GNNs within the EDA design flow.

Compiling a high-level quantum circuit down to a low-level description that can be executed on state-of-the-art quantum computers is a crucial part of the software stack for quantum computing. One step in compiling a quantum circuit to some device is quantum circuit mapping, where the circuit is transformed such that it complies with the architecture’s limited qubit connectivity. Because the search space in quantum circuit mapping grows exponentially in the number of qubits, it is desirable to consider as few of the device’s physical qubits as possible in the process. Previous work conjectured that it suffices to consider only subarchitectures of a quantum computer composed of as many qubits as used in the circuit. In this work, we refute this conjecture and establish criteria for judging whether considering larger parts of the architecture might yield better solutions to the mapping problem. We show that determining subarchitectures that are of minimal size, i.e., from which no physical qubit can be removed without losing the optimal mapping solution for some quantum circuit, is a very hard problem. Based on a relaxation of the criteria for optimality, we introduce a relaxed consideration that still maintains optimality for practically relevant quantum circuits. Eventually, this results in two methods for computing near-optimal sets of subarchitectures—providing the basis for efficient quantum circuit mapping solutions. We demonstrate the benefits of this novel method for state-of-the-art quantum computers by IBM, Google, and Rigetti.

Microfluidic devices, often in the form of Lab-on-a-Chip (LoCs), are successfully utilized in many domains such as medicine, chemistry, biology, etc. However, neither the fabrication process nor the respectively used materials are perfect and, thus, defects are frequently induced into the actual physical realization of the device. This is especially critical for sensitive devices such as droplet-based microfluidic networks that are able to route droplets inside channels along different paths by only exploiting passive hydrodynamic effects. However, these passive hydrodynamic effects are very sensitive and already slight changes of parameters (e.g., in the channel width) can alter the behavior, even in such a way that the intended functionality of the network breaks. Hence, it is important that microfluidic networks become robust against such defects in order to prevent erroneous behavior. But considering such defects during the design process is a non-trivial task and, therefore, designers mostly neglected such considerations thus far. To overcome this problem, we propose a robustness improvement process that allows to optimize an initial design in such a way that it becomes more robust against defects (while still retaining the original behavior of the initial design). To this end, we first utilize a metric to compare the robustness of different designs and, afterwards, discuss methods that aim to improve the robustness. The metric and methods are demonstrated by an example and also tested on several networks to show the validity of the robustness improvement process.

As state-of-the-art quantum computers are capable of running increasingly complex algorithms, the need for automated methods to design and test potential applications rises. Equivalence checking of quantum circuits is an important, yet hardly automated, task in the development of the quantum software stack. Recently, new methods have been proposed that tackle this problem from widely different perspectives. However, there is no established baseline on which to judge current and future progress in equivalence checking of quantum circuits. In order to close this gap, we conduct a detailed case study of two of the most promising equivalence checking methodologies---one based on decision diagrams and one based on the ZX-calculus---and compare their strengths and weaknesses.

Field-coupled Nanocomputing (FCN) defines a class of post-CMOS nanotechnologies that promises compact layouts, low power operation, and high clock rates. Recent breakthroughs in the fabrication of Silicon Dangling Bonds (SiDBs) acting as quantum dots enabled the demonstration of a sub-30 nm2 OR gate and wire segments. This motivated the research community to invest manual labor in the design of additional gates and whole circuits which, however, is currently severely limited by scalability issues. In this work, these limitations are overcome by the introduction of a design automation framework that establishes a flexible topology based on hexagons as well as a corresponding Bestagon gate library for this technology and, additionally, provides automatic methods for physical design. By this, the first design automation solution for the promising SiDB platform is proposed. In an effort to support open research and open data, the resulting framework and all design files will be made available.

Quantum computers promise to efficiently solve important problems classical computers never will. However, in order to capitalize on these prospects, a fully automated quantum software stack needs to be developed. This involves a multitude of complex tasks from the classical simulation of quantum circuits, over their compilation to specific devices, to the verification of the circuits to be executed as well as the obtained results. All of these tasks are highly non-trivial and necessitate efficient data structures to tackle the inherent complexity. Starting from rather straight-forward arrays over decision diagrams (inspired by the design automation community) to tensor networks and the ZX-calculus, various complementary approaches have been proposed. This work provides a look "under the hood" of today's tools and showcases how these means are utilized in them, e.g., for simulation, compilation, and verification of quantum circuits.

The classical simulation of quantum circuits is essential in the development and testing of quantum algorithms. Methods based on tensor networks or decision diagrams have proven to alleviate the inevitable exponential growth of the underlying complexity in many cases. But the complexity of these methods is very sensitive to so-called contraction plans or simulation paths, respectively, which define the order in which respective operations are applied. While, for tensor networks, a plethora of strategies has been developed, simulation based on decision diagrams is mostly conducted in a straight-forward fashion thus far. In this work, we envision a flow that allows to translate strategies from the domain of tensor networks to decision diagrams. Preliminary results indicate that a substantial advantage may be gained by employing suitable simulation paths-motivating a thorough consideration.

Microfluidics is an emerging field that allows to minimize, integrate, and automate processes that are usually conducted with unwieldy laboratory equipment inside a single device; resulting in so-called “Labs-on-a-Chip” (LoCs). The design process of channel-based LoCs is still mainly conducted manually thus far - resulting in time-consuming tasks and error-prone designs. This also holds for the routing process, where multiple components inside an LoC should be connected according to a specification. In this work, we present a routing tool which considers the particular requirements of microfluidic applications and automates the routing process. In order to make the tool more accessible (even to users with little to no EDA-expertise), it is incorporated into a user-friendly and intuitive online interface.

Droplet-based microfluidic networks interconnect multiple microfluidic modules which allow to process (e.g., mix, sort, heat, incubate) so-called payload droplets (i.e., droplets containing a biological sample) on a single microfluidic chip. Inside such networks the path of a droplet and, thus, the module which processes it, can be controlled by microfluidic switches. Thus far, these switches are realized by injecting additional control droplets into the network which allow to trigger the switching mechanism by solely exploiting passive hydrodynamic effects. While this eliminates the need of expensive components such as valves, this droplet-controlled switching concept is very sensitive and already slight deviations, e.g., in the control droplet injection could lead to incorrectly triggered switches. In this work, we address this issue by proposing a new concept of pressure-controlled networks which omit the control droplets (and their drawbacks) and, instead, use a single pump in order to drive the switches. Using design automation expertise together with established models, we derive a corresponding blueprint which realizes this idea for a specific network architecture. Simulations based on established methods and design tools confirmed the suitability of the proposed pressure-controlled networks.

In this paper, we introduce the Label-Aware Ranked loss, a novel metric loss function. Compared to the state-of-the-art Deep Metric Learning losses, this function takes advantage of the ranked ordering of the labels in regression problems. To this end, we first show that the loss minimises when datapoints of different labels are ranked and laid at uniform angles between each other in the embedding space. Then, to measure its performance, we apply the proposed loss on a regression task of people counting with a short-range radar in a challenging scenario, namely a vehicle cabin. The introduced approach improves the accuracy as well as the neighboring labels accuracy up to 83.0% and 99.9%: An increase of 6.7% and 2.1% on state-of-the-art methods, respectively.

Nowadays, Deep Learning (DL) methods often overcome the limitations of traditional signal processing approaches. Nevertheless, DL methods are barely applied in real-life applications. This is mainly due to limited robustness and distributional shift between training and test data. To this end, recent work has proposed uncertainty mechanisms to increase their reliability. Besides, meta-learning aims at improving the generalization capability of DL models. By taking advantage of that, this paper proposes an uncertainty-based Meta-Reinforcement Learning (Meta-RL) approach with Out-of-Distribution (OOD) detection. The presented method performs a given task in unseen environments and provides information about its complexity. This is done by determining first and second-order statistics on the estimated reward. Using information about its complexity, the proposed algorithm is able to point out when tracking is reliable. To evaluate the proposed method, we benchmark it on a radar-tracking dataset. There, we show that our method outperforms related Meta-RL approaches on unseen tracking scenarios in peak performance by 16% and the baseline by 35% while detecting OOD data with an F1-Score of 72%. This shows that our method is robust to environmental changes and reliably detects OOD scenarios.

Nowadays, deep neural networks are widely used in a variety of fields that have a direct impact on society. Although those models typically show outstanding performance, they have been used for a long time as black boxes. To address this, Explainable Artificial Intelligence (XAI) has been developing as a field that aims to improve the transparency of the model and increase their trustworthiness. We propose a retraining pipeline that consistently improves the model predictions starting from XAI and utilizing state-of-the-art techniques. To do that, we use the XAI results, namely SHapley Additive exPlanations (SHAP) values, to give specific training weights to the data samples. This leads to an improved training of the model and, consequently, better performance. In order to benchmark our method, we evaluate it on both real-life and public datasets. First, we perform the method on a radar-based people counting scenario. Afterward, we test it on the CIFAR-10, a public Computer Vision dataset. Experiments using the SHAP-based retraining approach achieve a 4% more accuracy w.r.t. the standard equal weight retraining for people counting tasks. Moreover, on the CIFAR-10, our SHAP-based weighting strategy ends up with a 3% accuracy rate than the training procedure with equal weighted samples.

Boolean Satisfiability (SAT) techniques are well-established in classical computing where they are used to solve a broad variety of problems, e.g., in the design of classical circuits and systems. Analogous to the classical realm, quantum algorithms are usually modelled as circuits and similar design tasks need to be tackled. Thus, it is natural to pose the question whether these design tasks in the quantum realm can also be approached using SAT techniques. To the best of our knowledge, no SAT formulation for arbitrary quantum circuits exists and it is unknown whether such an approach is feasible at all. In this work, we define a propositional SAT encoding that, in principle, can be applied to arbitrary quantum circuits. However, we show that, due to the inherent complexity of representing quantum states, constructing such an encoding is not feasible in general. Therefore, we establish general criteria for determining the feasibility of the proposed encoding and identify classes of quantum circuits fulfilling these criteria. We explicitly demonstrate how the proposed encoding can be applied to the class of Clifford circuits as a representative. Finally, we empirically demonstrate the applicability and efficiency of the proposed encoding for Clifford circuits. With these results, we lay the foundation for continuing the ongoing success of SAT in classical circuit and systems design for quantum circuits.

No abstract available.

Malware applications are one of the major threats that computing systems face today. While security researchers develop new defense mechanisms to detect malware, attackers continue to release new malware families that evade detection. New defense mechanisms must therefore be developed to effectively counter malware. Hardware performance counters (HPCs) have been recently proposed as a means to detect malware. However, recent work has also shown that malware detection is not effective when performance counters are sampled in realistic scenarios. We show how proper data preprocessing and the use of the XGBoost classifier can be used to improve the performance of malware detection using HPCs by at least 15%. We also show that the proposed method can detect malware early (shortly after its launch) by classifying HPC datastreams at short time intervals. In addition, we propose a multitemporal classification model that ensures the early detection of a high percentage of malware while maintaining overall low false positive rates. Finally, we show that through robust training, the XGBoost classifier shows up to 50x less vulnerability to adversarial attacks that are intended to undermine its malware detection performance.

Sample preparation refers to the task of generating fluids with a specified target concentration. Generally, this is achieved by performing a set of mixing operations between biochemical fluids with a given volumetric ratio. Sample preparation plays a crucial role in several medical applications. Microfluidic devices or labs-on-chips (LoCs) got established as a suitable solution to realize this task in a miniaturized, integrated, and automatic fashion. Over the years, a variety of different microfluidic platforms emerged, which all have their respective pros and cons. Accordingly, numerous approaches aiming at the sample preparation problem have been proposed—each specialized on a single platform only. More precisely, sample preparation methods introduced thus far provide solutions for a particular platform only, i.e., they are platform specific. In this work, we propose a generic approach that generalizes the constraints of the different microfluidic platforms and, by this, provides a platform-independent sample preparation method. This allows designers to quickly check what existing platform is most suitable for the considered task and to easily support upcoming and future microfluidic platforms as well. We evaluated the performance of the proposed method with a wide range of test cases and concluded (from the evaluations) that the proposed generic approach is capable of efficiently generating results for various platforms with a quality that is close to results from dedicated approaches presented thus far.

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.

With quantum computers promising advantages even in the near-term NISQ era, there is a lively community that develops software and toolkits for the design of corresponding quantum circuits. Although the underlying problems are different, expertise from the design automation community, which developed sophisticated design solutions for the conventional realm in the past decades, can help here. In this respect, decision diagrams provide a promising foundation for tackling many design tasks such as simulation, synthesis, and verification of quantum circuits. However, users of the corresponding tools often do not have a proper background or an intuition about how these methods based on decision diagrams work and what their strengths and limits are. In this work, we first review the concepts of how decision diagrams can be employed, e.g., for the simulation and verification of quantum circuits. Afterwards, in an effort to make decision diagrams for quantum computing more accessible, we then present a visualization tool for quantum decision diagrams, which allows users to explore the behavior of decision diagrams in the design tasks mentioned above. Finally, we present decision diagram-based tools for simulation and verification of quantum circuits using the methods discussed above as part of the open-source Munich Quantum Toolkit (MQT)—a set of tools for quantum computing developed at the Technical University of Munich and the Johannes Kepler University Linz and released under the MIT license. More information about the corresponding tools is available at https://github.com/cda-tum/ddsim . By this, we provide an introduction of the concepts and tools for potential users who would like to work with them as well as potential developers aiming to extend them.

Microfluidics is a prospective field which provides technological advances to the life sciences. However, the design process for microfluidic devices is still in its infancy and frequently results in a "trial-and-error" scheme. In order to overcome this problem, simulation methods provide a powerful solution---allowing for deriving a design, validating its functionality, or exploring alternatives without the need of an actual fabricated and costly prototype. To this end, several physical models are available such as Computational Fluid Dynamics (CFD) or the 1-dimensional analysis model. However, while CFD-simulations have high accuracy, they also have high costs with respect to setup and simulation time. On the other hand, the 1D-analysis model is very efficient but lacks in accuracy when it comes to certain phenomena. In this work, we present ideas to combine these two models and, thus, to provide an accurate and efficient simulation approach for microfluidic networks. A case study confirms the general suitability of the proposed approach.

Quantum computers are constantly growing in their number of qubits, but continue to suffer from restrictions such as the limited pairs of qubits that may interact with each other. Thus far, this problem is addressed by mapping and moving qubits to suitable positions for the interaction (known as quantum circuit mapping). However, this movement requires additional gates to be incorporated into the circuit, whose number should be kept as small as possible since each gate increases the likelihood of errors and decoherence. State-of-the-art mapping methods utilize swapping and bridging to move the qubits along the static paths of the coupling map---solving this problem without exploiting all means the quantum domain has to offer. In this paper, we propose to additionally exploit quantum teleportation as a possible complementary method. Quantum teleportation conceptually allows to move the state of a qubit over arbitrary long distances with constant overhead---providing the potential of determining cheaper mappings. The potential is demonstrated by a case study on the IBM Q Tokyo architecture which already shows promising improvements. With the emergence of larger quantum computing architectures, quantum teleportation will become more effective in generating cheaper mappings.

Field-coupled Nanocomputing (FCN) is a class of post-CMOS emerging technologies, which promises to overcome certain physical limitations of conventional solutions such as CMOS by allowing for high computational throughput with low power dissipation. Despite their promises, the design of corresponding FCN circuits is still in its infancy. In fact, state-of-the-art solutions still heavily rely on conventional synthesis approaches that do not take the tight physical constraints of FCN circuits (particularly with respect to routability and clocking) into account. Instead, physical design is conducted in a second step in which a classical logic network is mapped onto an FCN layout. Using this two-stage approach with a classical and FCN-oblivious logic network as an intermediate result, frequently leads to substantial quality loss or completely impractical results. In this work, we propose a one-pass synthesis scheme for FCN circuits, which conducts both steps, synthesis and physical design, in a single run. For the first time, this allows to generate exact, i. e., minimal FCN circuits for a given functionality.

Recent years have seen unprecedented advance in the design and control of quantum computers. Nonetheless, their applicability is still restricted and access remains expensive. Therefore, a substantial amount of quantum algorithms research still relies on simulating quantum circuits on classical hardware. However, due to the sheer complexity of simulating real quantum computers, many simulators unrealistically simplify the problem and instead simulate perfect quantum hardware, i.e., they do not consider errors caused by the fragile nature of quantum systems. Stochastic quantum simulation provides a conceptually suitable solution to this problem: physically motivated errors are applied in a probabilistic fashion throughout the simulation. In this work, we propose to use decision diagrams, as well as concurrent executions, to substantially reduce resource-requirements-which are still daunting—for stochastic quantum circuit simulation. Backed up by rigorous theory, empirical studies show that this approach allows for a substantially faster and much more scalable simulation for certain quantum circuits.

Quantum computers promise to solve important problems faster than conventional computers. However, unleashing this power has been challenging. In particular, design automation runs into (1) the probabilistic nature of quantum computation and (2) exponential requirements for computational resources on non-quantum hardware. In quantum circuit simulation, Decision Diagrams (DDs) have previously shown to reduce the required memory in many important cases by exploiting redundancies in the quantum state. In this paper, we show that this reduction can be amplified by exploiting the probabilistic nature of quantum computers to achieve even more compact representations. Specifically, we propose two new DD-based simulation strategies that approximate the quantum states to attain more compact representations, while, at the same time, allowing the user to control the resulting degradation in accuracy. We also analytically prove the effect of multiple approximations on the attained accuracy and empirically show that the resulting simulation scheme enables speed-ups up to several orders of magnitudes.

Quantum computers exploit quantum effects in a controlled manner in order to efficiently solve problems that are very hard to address on classical computers. The ion-trap-based technology is a particularly advanced concept of realizing quantum computers with advantages with respect to physical realization and fault-tolerance. Accordingly, several physical design methods aiming at realizing quantum circuits to corresponding architectures have been proposed. However, all these methods are heuristic and cannot guarantee minimality. In this work, we propose a solution which can generate exact physical designs, i.e., solutions which require a minimal number of time steps. To this end, satisfiability solvers are utilized. Experimental evaluations confirm that, despite the underlying computational complexity of the problem, this allows to generate minimal physical designs for several quantum circuits for the first time.

Sample preparation plays a crucial role in several medical applications. Microfluidic devices or Labs-on-Chips (LoCs) got established as a suitable solution to realize this task in a miniaturized, integrated, and automatic fashion. Over the years,$a$variety of different microfluidic platforms emerged, which all have their respective pros and cons. Accordingly, numerous approaches for sample preparation have been proposed-each specialized on a single platform only. In this work, we propose an idea towards a generic sample preparation approach which will generalize the constraints of the different microfluidic platforms and, by this, will provide a platform-independent sample preparation method. This will allow designers to quickly check what existing platform is most suitable for the considered task and to easily support upcoming and future microfluidic platforms as well. We illustrate the applicability of the proposed method with examples for various platforms.

With the emergence of more and more applications for quantum computing, also the development of corresponding methods for design automation is receiving increasing interest. In this respect, decision diagrams provide a promising basis for many design tasks such as simulation, synthesis, verification, and more. However, users of the corresponding tools often do not have a proper background or an intuition about how these methods based on decision diagrams work and what their strengths and limits are. In an effort to make decision diagrams for quantum computing more accessible, we present a visualization tool which visualizes quantum decision diagrams and allows to explore their behavior when used in the design tasks mentioned above. The installation-free web-tool allows users to interactively learn how decision diagrams can be used in quantum computing, e.g., to (1) compactly represent quantum states and the functionality of quantum circuits, (2) to efficiently simulate quantum circuits, and (3) to verify the equivalence of two circuits. The tool is available at https://iic.jku.at/eda/research/quantum_dd/tool

For centuries, block signaling has been the fundamental principle of today's railway systems to prevent trains from running into each other. But the corresponding infrastructure of physical blocks each requiring train detection methods is costly. Therefore, initiatives such as the European Train Control System (ETCS) and, here, particularly Level 3 of ETCS aim for the utilization of virtual sections which allow for a much higher degree of freedom and provide significant potential for increasing the efficiency in today's train schedules. However, exploiting this potential is a highly non-trivial task which, thus far, mainly relied on manual labor. In this work, we provide an initial automatic methodology which aids designers of corresponding railway networks and train schedules. The methodology utilizes design automation expertise (here, in terms of satisfiability solvers) to unveil the potential of ETCS Level 3. Case studies (including a real-life example inspired by the Norwegian Railways) confirm the applicability and suitability of the proposed methodology.

The emergence of continuous-flow microfluidics has led to a revolution in biochemistry and biomedicine. On such a microscale lab-on-a-chip system, complex biochemical assays, e.g., DNA analysis and drug discovery, can be executed efficiently without any human intervention. Owing to the high complexity of chip architecture and assay protocol, considerable effort has been directed towards the design automation of such chips over the past decade. Existing methods, however, perform the corresponding design tasks including binding, scheduling, placement, and routing separately, leading to serious gaps between different steps and may even cause design failure. To overcome these drawbacks, in this paper, we propose a one-pass architecture synthesis flow called BigIntegr, for continuous-flow microfluidic lab-on-a-chip, integrating all the design steps into an “organic whole”, which has never been considered in prior work. With the proposed BigIntegr, the aforementioned design tasks can be synchronized seamlessly and performed in a combined manner, thereby eliminating the gaps between design steps. As a result, biochip architectures with both high efficiency and low cost can be generated without any design adjustments and modifications. Experimental results on multiple benchmarks demonstrate the effectiveness of the proposed automation flow.

The utilization of System on Chips (SoCs) for short- living consumer applications has become very popular over the last decades. Because of that, more and more effort has been put into the physical design of SoCs and especially into the so-called macro placement step in order to keep the final price suitable for mass production. How to guarantee that the SoC is realized based on a minimal die area remains a challenging task. Current state-of-the-art solutions for this macro placement-problem mostly try to tackle the problem based on meta-heuristic- and genetic algorithms. However, although such methods are commonly used for macro placement, they can not guarantee that the macro placement and, therefore the die size is optimal. In this work, we are proposing the utilization of modern satisfiability solvers in order to generate optimized macro placements. To this end, we symbolically formulate the placement problem and forward it to a solver which allows us to obtain optimized solutions for the macro placement problem. In case this is not possible, search space pruning is employed which does not allow to employ the full optimization strategy anymore but still determines feasible results. We demonstrate the approach in experiments and made the resulting tool available as open-source.

Due to the significant progress made in the implementation of quantum hardware, efficient methods and tools to design corresponding algorithms become increasingly important. Many of these tools rely on functional representations of certain building blocks or even entire quantum algorithms which, however, inherently exhibit an exponential complexity. Although several alternative representations have been proposed to cope with this complexity, the construction of those representations remains a bottleneck. In this work, we propose solutions for efficiently constructing representations of quantum functionality based on the idea of conducting as many operations as possible on as small as possible intermediate representations -- using Decision Diagrams as a representative functional description. Experimental evaluations show that applying these solutions allows to construct the desired representations several factors faster than with state-of-the-art methods. Moreover, if repeating structures (which frequently occur in quantum algorithms) are explicitly exploited, exponential improvements are possible -- allowing to construct the functionality of certain algorithms within seconds, whereas the state of the art fails to construct it in an entire day.

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.

Droplet-based microfluidic networks allow to process biological or medical samples by standard unit operations, such as mixing, incubating, sorting, or sensing. However, many of these networks usually perform such operations in a predefined way and, thus, lack in their flexibility. To overcome this problem, ring networks are used, since they allow to execute multiple operations in a row. But while several concepts and also prototypical implementations exist that realize such ring networks, the design process for them is still mainly conducted manually thus far. This is a severe drawback since various aspects, such as the dimensions of the channels, the effects of droplets, the used fluids, the volumetric flow rates inside the channels, etc., have to be considered for this purpose. In this article, we propose design automation methods which address this problem. The proposed solution will automatically generate a proper design as well as correspondingly needed droplet sequences. A case study demonstrates the applicability of the resulting methods and simulations confirms the validity of the proposed approach.

A digital microfluidic biochip (DMFB) is a miniaturized laboratory capable of implementing biochemical protocols. Fully integrated DMFBs consist of a hardware platform, controller, and network connectivity, making it a cyber-physical system (CPS). A DMFB CPS is being advocated for safety-critical applications, such as medical diagnosis, drug development, and personalized medicine. Hence, the security of a DMFB CPS is of immense importance to their successful deployment. Recent research has made progress in devising corresponding defense mechanisms by employing so-called checkpoints (CPs). Existing solutions either rely on probabilistic security analysis that does not consider all possible actions an attacker may use to overcome an applied CP mechanism or rely on exhaustive monitoring of DMFB at all time-steps during the assay execution. For devising a defense scheme that is guaranteed to be secure, an exact analysis of the security of a DMFB is needed. This is not available in the current state-of-the-art. In this article, we address this issue by developing an exact method, which uses the deductive power of satisfiability solvers to verify whether a CP-based defense thwarts the execution of an attack. We demonstrate the usefulness of the proposed method by showcasing two applications on practical bioassays: 1) security analysis of various checkpointing strategies and 2) derivation of a counterexample-guided fool-proof secure CP scheme.

Digital microfluidics biochips are a promising emerging technology that provides fluidic experimental capabilities on a chip (i.e., following the lab-on-a-chip paradigm). However, the design of such biochips still constitutes a challenging task that is usually tackled by multiple individual design steps, such as binding, scheduling, placement, and routing. Performing these steps consecutively may lead to design gaps and infeasible results. To address these shortcomings, the concept of one-pass design for digital microfluidics biochips has recently been proposed—a holistic approach avoiding the design gaps by considering the whole synthesis process as large. But implementations of this concept available thus far suffer from either high computational effort or costly results. In this article, we present an efficient one-pass solution that is runtime efficient (i.e., rarely needing more than a second to successfully synthesize a design) while, at the same time, producing better results than previously published heuristic approaches. Experimental results confirm the benefits of the proposed solution and allow for realizing really large assays composed of thousands of operations in reasonable runtime.

Digital microfluidic biochips have fueled a paradigm shift in implementing bench-top laboratory experiments on a single tiny chip, thus replacing costly and bulky equipment. However, because of imprecise fluidic functions, several volumetric split errors may occur during the execution of bioassays. Earlier approaches to error-correcting sample preparation addressed this problem by using a cyberphysical system yielding several drawbacks such as increased sample preparation cost and time, and uncertainty in assay completion time. In addition, error correction for only a single-target sample has been considered so far, although many assays require the production of multi-target samples. In this work, we present an error-free dilution technique that guarantees the correctness of the resulting concentration factor of a sample without performing any additional roll-back or roll-forward action. To the best of our knowledge, we are the first to present a solution strategy for tackling dispensing errors during sample preparation. We use micro-electrode-dot-array biochips that offer the advantages of manipulating fractional volumes of droplets (aliquots) for navigation, as well as mix-split operations. Instead of performing traditional mix-and-split steps with integral-volume droplets, we execute only an aliquoting-and-mix sequence using differential-size aliquots. Thus, all split operations, which are the main source of errors in conventional digital microfluidic biochips, are completely eliminated, and hence neither sensing nor any correcting action is needed, and further, no management of intermediate waste droplets is needed. Additionally, the procedure can be fully parallelized for accurately producing multiple dilutions of a sample. Experimental results corroborate the superiority of the proposed method in terms of error management, as well as sample preparation cost and time.

In this work, we sketch an automated design flow for hardware synthesis based on a formal specification. Verification results are propagated from the FSL level through the proposed flow to generate an ESL model as well as an RTL implementation automatically. In contrast, the established design flow relies on manual implementations at the ESL and RTL level. The proposed design flow combines proof assistants with functional hardware description languages. This combination decreases the implementation effort significantly and the generation of test benches is no longer needed. We illustrate our design flow by specifying and synthesizing a set of benchmarks that contain sequential and combinational hardware designs. We compare them with implementations required by the established hardware design flow.

Quantum computing is gaining considerable momentum through the recent progress in physical realizations of quantum computers. This led to rather sophisticated design flows in which the originally specified quantum functionality is compiled through different abstractions. This increasingly raises the question whether the respectively resulting quantum circuits indeed realize the originally intended function. Accordingly, efficient methods for equivalence checking are gaining importance. However, existing solutions still suffer from significant shortcomings such as their exponential worst case performance and an increased effort to obtain counterexamples in case of non-equivalence. In this work, we propose an improved DD-based equivalence checking approach which addresses these shortcomings. To this end, we utilize decision diagrams and exploit the fact that quantum operations are inherently reversible - allowing for dedicated strategies that keep the overhead moderate in many cases. Experimental results confirm that the proposed strategies lead to substantial speed-ups - allowing to perform equivalence checking of quantum circuits factors or even magnitudes faster than the state of the art.

Despite recent progress in physical implementations of quantum computers, a significant amount of research still depends on simulating quantum computations on classical computers. Here, most state-of-the-art simulators rely on array-based approaches which are perfectly suited for acceleration through concurrency using multi- or many-core processors. However, those methods have exponential memory complexities and, hence, become infeasible if the considered quantum circuits are too large. To address this drawback, complementary approaches based on decision diagrams (called DD-based simulation) have been proposed which provide more compact representations in many cases. While this allows to simulate quantum circuits that could not be simulated before, it is unclear whether DD-based simulation also allows for similar acceleration through concurrency as array-based approaches. In this work, we investigate this issue. The resulting findings provide a better understanding about when DD-based simulation can be accelerated through concurrent executions of sub-tasks and when not.

The computational power of quantum computers poses major challenges to new design tools since representing pure quantum states typically requires exponentially large memory. As shown previously, decision diagrams can reduce these memory requirements by exploiting redundancies. In this work, we demonstrate further reductions by allowing for small inaccuracies in the quantum state representation. Such inaccuracies are legitimate since quantum computers themselves experience gate and measurement errors and since quantum algorithms are somewhat resistant to errors (even without error correction). We develop four dedicated schemes that exploit these observations and effectively approximate quantum states represented by decision diagrams. We empirically show that the proposed schemes reduce the size of decision diagrams by up to several orders of magnitude while controlling the fidelity of approximate quantum state representations.

The rapid rate of progress in the physical realization of quantum computers sparked the development of elaborate design flows for quantum computations on such devices. Each stage of these flows comes with its own representation of the intended functionality. Ensuring that each design step preserves this intended functionality is of utmost importance. However, existing solutions for equivalence checking of quantum computations heavily struggle with the complexity of the underlying problem and, thus, no conclusions on the equivalence may be reached with reasonable efforts in many cases. In this work, we uncover the power of simulation for equivalence checking in quantum computing. We show that, in contrast to classical computing, it is in general not necessary to compare the complete representation of the respective computations. Even small errors frequently affect the entire representation and, thus, can be detected within a couple of simulations. The resulting equivalence checking flow substantially improves upon the state of the art by drastically accelerating the detection of errors or providing a highly probable estimate of the operations' equivalence.

Quantum computers promise significant speedups in solving problems intractable for conventional computers but, despite recent progress, remain limited in scaling and availability. Therefore, quantum software and hardware development heavily rely on simulation that runs on conventional computers. Most such approaches perform strong simulation in that they explicitly compute amplitudes of quantum states. However, such information is not directly observable from a physical quantum computer because quantum measurements produce random samples from probability distributions defined by those amplitudes. In this work, we focus on weak simulation that aims to produce outputs which are statistically indistinguishable from those of error-free quantum computers. We develop algorithms for weak simulation based on quantum state representation in terms of decision diagrams. We compare them to using state-vector arrays and binary search on prefix sums to perform sampling. Empirical validation shows, for the first time, that this enables mimicking of physical quantum computers of significant scale.

With the decline of Moore's Law, several post-CMOS technologies are currently under heavy consideration. Promising candidates can be found in the class of Field-coupled Nanocomputing (FCN) devices as they allow for highest processing performance with tremendously low energy dissipation. With upcoming design automation in this domain, the need for formal verification approaches arises. Unfortunately, FCN circuits come with certain domain-specific properties that render conventional methods for the verification non-applicable. In this paper, we investigate this issue and propose a verification approach for FCN circuits that addresses this problem. For the first time, this provides researchers and engineers with an automatic method that allows them to check whether an obtained FCN circuit design indeed implements the given/desired function. A prototype implementation demonstrates the applicability of the proposed approach.

Quantum computing is currently moving from an academic idea to a practical reality. Quantum computing in the cloud is already available and allows users from all over the world to develop and execute real quantum algorithms. However, companies which are heavily investing in this new technology such as Google, IBM, Rigetti, Intel, IonQ, and Xanadu follow diverse technological approaches. This led to a situation where we have substantially different quantum computing devices available thus far. They mostly differ in the number and kind of qubits and the connectivity between them. Because of that, various methods for realizing the intended quantum functionality on a given quantum computing device are available. This paper provides an introduction and overview into this domain and describes corresponding methods, also referred to as compilers, mappers, synthesizers, transpilers, or routers.

The recent advances in the physical realization of Noisy Intermediate Scale Quantum (NISQ) computers have motivated research on design automation that allows users to execute quantum algorithms on them. Certain physical constraints in the architectures restrict how logical qubits used to describe the algorithm can be mapped to physical qubits used to realize the corresponding functionality. Thus far, this has been addressed by inserting additional operations in order to overcome the physical constrains. However, all these approaches have taken the existing architectures as invariant and did not explore the potential of changing the quantum architecture itself-a valid option as long as the underlying physical constrains remain satisfied. In this work, we propose initial ideas to explore this potential. More precisely, we introduce several schemes for the generation of 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.

The design of modern systems has reached a complexity which makes it inevitable to apply verification methods in order to guarantee its correct and safe execution. The verification methods frequently produce proof obligations that can not be solved any more due to the huge search space. However, by setting enough variables to fixed values, the search space is obviously reduced and solving engines eventually may be able to complete the verification task. Although this results in a partial verification, the results may still be valuable — in particular as opposed to the alternative of no verification at all. However, so far no systematic investigation has been conducted on which variables to fix in order to reduce verification runtime as much as possible while, at the same time, still getting most coverage. This paper addresses this question by proposing a corresponding verification runtime analysis. Experimental evaluations confirm the potential of this approach.

Field-coupled Nanocomputing (FCN) is a computing concept with several promising post-CMOS candidate implementations that offer tremendously low power dissipation and highest processing performance at the same time. Two of the manifold physical implementations are Quantum-dot Cellular Automata (QCA) and Nanomagnet Logic (NML). Both inherently come with domain-specific properties and design constraints that render established conventional design algorithms inapplicable. Accordingly, dedicated design tools for those technologies are required. This paper provides an overview of two leading examples of such tools, namely fiction and ToPoliNano. Both tools provide effective methods that cover aspects such as placement, routing, clocking, design rule checking, verification, and logical as well as physical simulation. By this, both freely available tools provide platforms for future research in the FCN domain.

The complexity of today's System on Chips (SoCs) forces designers to use higher levels of abstractions. Here, early design decisions are conducted on abstract models while different configurations describe how to actually realize the desired SoC. Since those decisions severely affect the final costs of the resulting SoC (in terms of utilized area, power consumption, etc.), a fast and accurate cost estimation is essential at this design stage. Additionally, the resulting costs heavily depend on the adopted logic synthesis algorithms, which optimize the design towards one or more cost objectives. But how to structure a cost estimation method that supports multiple configurations of an SoC, implemented by use of different synthesis strategies, remains an open question. In this work, we address this problem by providing a cost estimation method for a configurable SoC using Machine Learning (ML). A key element of the proposed method is a data representation which describes SoC configurations in a way that is suited for advanced ML algorithms. Experimental evaluations conducted within an industrial environment confirm the accuracy as well as the efficiency of the proposed method.

By using quantum mechanical effects, quantum computers promise significant speedups in solving problems intractable for conventional computers. However, despite recent progress they remain limited in scaling and availability---making quantum software and hardware development heavily reliant on quantum simulators running on conventional hardware. However, most of those simulators mimic perfect quantum computers and, hence, ignore the fragile nature of quantum mechanical effects which frequently yield to decoherence errors in real quantum devices. Considering those errors during the simulation is complex, but necessary in order to tailor quantum algorithms for specific devices. Thus far, most state-of-the-art simulators considering decoherence errors rely on (exponentially) large array representations. As an alternative, simulators based on decision diagrams have been shown very promising for simulation of quantum circuits in general, but have not supported decoherence errors yet. In this work, we are closing this gap. We investigate how the consideration of decoherence errors affects the simulation performance of approaches based on decision diagrams and propose advanced solutions to mitigate negative effects. Experiments confirm that this yields improvements of several orders of magnitudes compared to a naive consideration of errors.

With quantum computers on the brink of practical applicability, there is a lively community that develops toolkits for the design of corresponding quantum circuits. Many of the problems to be tackled here are similar to design problems from the classical realm for which sophisticated design automation tools have been developed in the previous decades. In this paper, we present JKQ---a set of tools for quantum computing developed at the Johannes Kepler University (JKU) Linz which utilizes this design automation expertise. By this, we offer complementary approaches for many design problems in quantum computing such as simulation, compilation, or verification. In the following, we provide an introduction of the tools for potential users who would like to work with them as well as potential developers aiming to extend them.

High-level descriptions of quantum algorithms do not take the restrictions of physical hardware into account. Therefore actually executing an algorithm in the form of a quantum circuit on a quantum computer requires compiling it for the desired target architecture first. The compilation of quantum circuits depends on efficient methods to be feasible for all but the trivial instances. To this end, different compiling methods have been introduced in the past, but room for improvement still exists. Moreover, just an efficient compilation process itself is not sufficient-the resulting circuits must be correct as well. In this summary paper, we review how existing compilation approaches can be optimized by utilizing heuristic search algorithms or exact reasoning engines. Furthermore, we review how the correctness of the obtained results can be verified afterwards by clever data structures such as decision diagrams. This illustrates core steps of a compilation flow which can generate minimal or close-to-minimal results for many instances and, additionally, guarantees correctness throughout the process.

Near zero-energy computing describes the concept of executing logic operations below the ( k B T ln 2) energy limit. Landauer discussed that it is impossible to break this limit as long as the computations are performed in the conventional, non-reversible way. But even if reversible computations were performed, the basic energy needed for operating circuits realized in conventional technologies is still far above the ( k B T ln 2) energy limit (i.e., the circuits do not operate in a physically reversible manner). In contrast, novel nanotechnologies like Quantum-dot Cellular Automata (QCA) allow for computations with very low energy dissipation and hence are promising candidates for breaking this limit. Accordingly, the design of reversible QCA circuits is an active field of research. But whether QCA in general and the proposed circuits in particular are indeed able to operate in a logically and physically reversible fashion is unknown thus far, because neither physical realizations nor appropriate simulation approaches are available. In this work, we address this gap by utilizing an established theoretical model that has been implemented in a physics simulator enabling a precise consideration of how energy is dissipated in QCA designs. Our results provide strong evidence that QCA is indeed a suitable technology for near zero-energy computing. Further, the first design of a logically and physically reversible adder circuit is presented, which serves as proof of concept for future circuits with the ability of near zero-energy computing.

Hardware/software co-designs are usually defined at high levels of abstractions at the beginning of the design process in order to provide a variety of options on how to realize a system. This allows for design exploration which relies on knowing the costs of different design configurations (with respect to hardware usage and firmware metrics). To this end, methods for cost estimation are frequently applied in industrial practice. However, currently used methods oversimplify the problem and ignore important features, leading to estimates which are far off from real values. In this article, we address this problem for memory systems. To this end, we borrow and re-adapt solutions based on Machine Learning (ML) which have been found suitable for problems from the domain of Computer Vision (CV). Based on that, an approach is proposed which outperforms existing methods for cost estimation. Experimental evaluations within an industrial context show that, while the accuracy of the state-of-the-art approach is frequently off by more than 20 percent for area estimation and more than 15 percent for firmware estimation, the method proposed in this article comes rather close to the actual values (just 5-7 percent off for both area and firmware). Furthermore, our approach outperforms existing methods for scalability, generalization, and decrease in manual effort.

Lab-on-chip (LoC) technology has emerged as one of the major driving forces behind the recent surge in biochemical protocol automation. Dilution and mixture preparation with fluids in a desired ratio, constitute basic steps in sample preparation for which several LoC-based architectures and algorithms are known. The optimization of cost and time for such protocols requires proper sequencing of fluidic mix-and-split steps, and storage-units for holding intermediate-fluids to be reused in the later steps. However, practical design constraints often limit the amount of on-chip storage in microfluidic LoC architectures and thus can badly affect the performance of the algorithms. Consequently, results generated by previous work may not be useful (in the case they require more storage-units than available) or more expensive than necessary (in the case when storage-units are available but not used, e.g., to further reduce the number of mix/split operations or reactant-cost). In this paper, we propose new algorithms for dilution and mixing with continuous-flow-based LoCs that explicitly take care of storage constraints while optimizing reactant-cost and time of sample preparation. We present a symbolic formulation of the problem that captures the degree of freedom in algorithmic steps satisfying the specified storage constraints. Solvers based on Boolean satisfiability are used to achieve the optimization goals. The experimental results show the efficiency and effectiveness of the solution as well as a variety of applications where the proposed methods would prove beneficial.

Microfluidic networks can be applied to droplet-based Lab-on-a-Chip devices, where droplets are used to confine samples which flow through closed microchannels along different paths in order to execute (bio-)chemical experiments. In order to allow this routing of droplets, the design of the microfluidic network has to be precisely defined and afterward fabricated. However, neither the fabrication process nor the applied materials and components are perfect and, therefore, the fabricated microfluidic device frequently contains defects (produced by fabrication tolerances, properties of the used material, or fluctuation of supply pumps). Those may have a severe impact on the behavior of the microfluidic network and can even render the network useless. Furthermore, these defects complicate the design process, which eventually results in a “trial-and-error”-approach causing high costs with respect to time and money. Consequently, designers want to anticipate how robust their design is against those defects. This article, for the first time, describes how these defects can be abstracted, which eventually allows to evaluate the robustness already in the design process. We additionally introduce models considering single and multiple defects as well as corresponding methods for their analysis. Evaluations on a microfluidic network which is used to screen drug compounds confirm that the resulting robustness analysis indeed provides designers with a simple metric to decide how sensitive their design is against defects. The models and methods proposed in this article are grounded on the established 1-D analysis model.

Droplet-based microfluidic devices are a well-established and highly potential Labs-on-Chip technology as droplets are especially suited to encapsulate biological samples like cells, proteins, or DNA. These droplets are injected in a continuous phase and flow through closed microchannels to modules executing operations on the droplets-eventually realizing a (bio-)chemical experiment. Moreover, this technology even allows for the realization of multiple experiments on a single device by letting droplets take different paths through the microfluidic network. This requires, however, a mechanism to route the droplets along these paths. To this end, the concept of passive droplet routing has been suggested which entirely avoids complex valves or switches and, instead, realizes the routing by exploiting the hydrodynamic effect that a droplet will always flow along the path with the highest volumetric flow rate. Since droplets themselves affect the volumetric flow rate, a dedicated sequence of droplets can define what path is taken and, hence, what experiment is executed. However, determining such a droplet sequence is a nontrivial task, as it is nonobvious how much droplets are needed, when to inject them, and how they are interacting. In this paper, we are addressing this issue by providing, for the first time, an automatic method for the generation of droplet sequences realizing the desired experiments on a given network. Evaluations confirm the practicability of the proposed solution. Moreover, the suitability of the obtained droplet sequences is additionally validated through simulations on the 1D analysis model.

Quantum computers are becoming a reality today due to the rapid progress made by researchers in the last years. In the process of building quantum computers, IBM has developed several versions-starting from 5-qubit architectures like IBM QX2 and IBM QX4 to larger 16- or 20-qubit architectures. These architectures support arbitrary rotations of a single qubit and a controlled negation (CNOT) involving two qubits. The two qubit operations come with added coupling-map restrictions that only allow specific physical qubits to be the control and target qubits of the operation. In order to execute a quantum circuit on the IBM QX architecture, CNOT gates must satisfy the so-called coupling constraints of the architecture. Previous works addressed this issue with the objective of reducing the number of gates and the circuit depth. However, in this article, we show that further improvements are possible. To this end, we present a general approach for further improving the number of gate operations and depth of the mapped circuit. The proposed approach encompasses the selection of physical qubits, determining initial and local permutations efficiently to obtain the final circuit mapped to the given IBM QX architecture. Through experiments, improvements are observed over existing methods in terms of the number of gates and circuit depth.

Quantum computation promises to solve many hard or infeasible problems substantially faster than classical solutions. The involvement of big players like Google, IBM, Intel, Rigetti, or Microsoft furthermore led to a momentum which increases the demand for automated design methods for quantum computations. In this context, decision diagrams for quantum computation provide a major pillar as they allow to efficiently represent quantum states and quantum operations which, otherwise, have to be described in terms of exponentially large state vectors and unitary matrices. However, current decision diagrams for the quantum domain suffer from a tradeoff between accuracy and compactness, since: 1) small errors that are inevitably introduced by the limited precision of floating-point arithmetic can harm the compactness (i.e., the size of the decision diagram) significantly and 2) overcompensating these errors (to increase compactness) may lead to an information loss and introduces numerical instabilities. In this article, we describe and evaluate the effects of this tradeoff which clearly motivates the need for a solution that is perfectly accurate and compact at the same time. More precisely, we show that the tradeoff indeed weakens current design automation approaches for quantum computation (possibly leading to corrupted results or infeasible run-times). To overcome this, we propose an alternative approach that utilizes an algebraic representation of the occurring complex and irrational numbers and outline how this can be incorporated in a decision diagram which is suited for quantum computation. Evaluations show that-at the cost of an overhead which is moderate in many cases-the proposed algebraic solution indeed overcomes the tradeoff between accuracy and compactness that is present in current numerical solutions.

Flow-based microfluidic biochips are one of the most promising platforms used in biochemical and pharmaceutical laboratories due to their high efficiency and low costs. Inside such a chip, fluids of nanoliter volumes are transported between devices for various operations, such as mixing and detection. The transportation channels and corresponding operation devices are controlled by microvalves driven by external pressure sources. Since assigning an independent pressure source to every microvalve would be impractical due to high costs and limited system dimensions, states of microvalves are switched by a control logic using time multiplexing. Existing control-logic designs, however, still switch only a single control channel per operation, leading to a low efficiency. In this article, we present the first automatic synthesis approach for a control logic that is able to switch multiple control channels simultaneously. Moreover, we propose the first fault-aware design in control logic by introducing backup control paths to maintain the correct function even when manufacturing defects occur. The construction of control logic is achieved by a highly efficient framework based on particle swarm optimization, Boolean logic simplification, grid routing, together with mixing multiplexing. The simulation results demonstrate that the proposed multichannel switching mechanism leads to fewer valve-switching times and lower total logic cost, while realizing fault tolerance for all control channels.

In this article, we consider the problem of droplet routing for Microelectrode-Dot-Array (MEDA) biochips. MEDA biochips today provide a host of useful features for droplet movement by making it possible to manoeuvre droplets at a much finer granularity and with significantly increased flexibility. More precisely, MEDA biochips support more degrees of freedom in navigation and volumetric manipulation such as diagonal movement, droplet reshaping, and fractional-level split-and-merge. This helps improve routing of droplets on microfluidic grids—in particular, when the space available on the grid is limited or blocked by obstacles. In this work, we discuss how these improved capabilities can be utilized in the realization of the desired routes on those biochips. To this end, we introduce a routing method that utilizes satisfiability solvers and guarantees the generation of optimal solutions, considering the set of MEDA operations we model. This significantly improves the state of the art, since previously proposed solutions either (1) relied on heuristics and, hence, were not able to guarantee the optimum or (2) only considered a subset of the MEDA features. The solution proposed in this work includes a formulation of all MEDA features, which, as illustrated by examples, allows for the determination of routing solutions with smaller completion times. Experimental evaluations confirm these findings.

Field-coupled Nanocomputing (FCN) technologies are considered as a solution to overcome physical boundaries of conventional CMOS approaches. But despite ground breaking advances regarding their physical implementation as e.g. Quantum-dot Cellular Automata (QCA), Nanomagnet Logic (NML), and many more, there is an unsettling lack of methods for large-scale design automation of FCN circuits. In fact, design automation for this class of technologies still is in its infancy - heavily relying either on manual labor or automatic methods which are applicable for rather small functionality only. This work presents a design method which - for the first time - allows for the scalable design of FCN circuits that satisfy dedicated constraints of these technologies. The proposed scheme is capable of handling around 40000 gates within seconds while the current state-of-the-art takes hours to handle around 20 gates. This is confirmed by experimental results on the layout level for various established benchmarks libraries.

Sample preparation is an important application for the digital microfluidic biochips (DMFBs) platform, and many methods have been developed to reduce the time and reagent usage associated with on-chip sample preparation. However, errors in fluidic operations can result in the concentration of the resulting droplet being outside the calibration range. Current error-recovery methods have the drawback that they need the use of on-chip sensors and further re-execution time. In this paper, we present two dilution-chain structures that can generate a droplet with a desired concentration even if volume variations occur during droplet splitting. Experimental results show the effectiveness of the proposed method compared to previous methods.

The identification of the memristor as fourth fundamental circuit element and, eventually, its fabrication in the HP labs provide new capabilities for in-memory computing. While there already exist sophisticated methods for realizing logic gates with memristors, mapping them to crossbar structures (which can easily be fabricated) still constitutes a challenging task. This is particularly the case since several (complementary) design objectives have to be satisfied, e.g. the design method has to be scalable, should yield designs requiring a low number of timesteps and utilized memristors, and a layout should result that is hardly skewed. However, all solutions proposed thus far only focus on one of these objectives and hardly address the other ones. Consequently, rather imperfect solutions are generated by state-of-the-art design methods for memristor-aided logic thus far. In this work, we propose a corresponding automatic design solution which addresses all these design objectives at once. To this end, a staircase structure is utilized which employs an almost square-like layout and remains perfectly scalable while, at the same time, keeps the number of timesteps and utilized memristors close to the minimum. Experimental evaluations confirm that the proposed approach indeed allows to satisfy all design objectives at once.

Adiabatic circuits are heavily investigated since they allow for computations with an asymptotically close to zero energy dissipation per operation---serving as an alternative technology for many scenarios where energy efficiency is preferred over fast execution. Their concepts are motivated by the fact that the information lost from conventional circuits results in an entropy increase which causes energy dissipation. To overcome this issue, computations are performed in a (conditionally) reversible fashion which, additionally, have to satisfy switching rules that are different from conventional circuitry---crying out for dedicated design automation solutions. While previous approaches either focus on their electrical realization (resulting in small, hand-crafted circuits only) or on designing fully reversible building blocks (an unnecessary overhead), this work aims for providing an automatic and dedicated design scheme that explicitly takes the recent findings in this domain into account. To this end, we review the theoretical and technical background of adiabatic circuits and present automated methods that dedicatedly realize the desired function as an adiabatic circuit. The resulting methods are further optimized---leading to an automatic and efficient design automation for this promising technology. Evaluations confirm the benefits and applicability of the proposed solution.

The Noisy Intermediate-Scale Quantum (NISQ) technology is currently investigated by major players in the field to build the first practically useful quantum computer. IBM QX architectures are the first ones which are already publicly available today. However, in order to use them, the respective quantum circuits have to be compiled for the respectively used target architecture. While first approaches have been proposed for this purpose, they are infeasible for a certain set of SU(4) quantum circuits which have recently been introduced to benchmark corresponding compilers. In this work, we analyze the bottlenecks of existing compilers and provide a dedicated method for compiling this kind of circuits to IBM QX architectures. Our experimental evaluation (using tools provided by IBM) shows that the proposed approach significantly outperforms IBM's own solution regarding fidelity of the compiled circuit as well as runtime. Moreover, the solution proposed in this work has been declared winner of the IBM QISKit Developer Challenge. An implementation of the proposed methodology is publicly available at http://iic.jku.at/eda/research/ibm_qx_mapping.

The recent progress in the physical realization of quantum computers (the first publicly available ones---IBM's QX architectures---have been launched in 2017) has motivated research on automatic methods that aid users in running quantum circuits on them. Here, certain physical constraints given by the architectures which restrict the allowed interactions of the involved qubits have to be satisfied. Thus far, this has been addressed by inserting SWAP and H operations. However, it remains unknown whether existing methods add a minimum number of SWAP and H operations or, if not, how far they are away from that minimum---an NP-complete problem. In this work, weaddress this by formulating the mapping task as a symbolic optimization problem that is solved using reasoning engines like Boolean satisfiability solvers. By this, we do not only provide a method that maps quantum circuits to IBM's QX architectures with a minimal number of SWAP and H operations, but also show by experimental evaluation that the number of operations added by IBM's heuristic solution exceeds the lower bound by more than 100% on average. An implementation of the proposed methodology is publicly available at http://iic.jku.at/eda/research/ibm_qx_mapping.

This paper investigates the benefits of verifying embedded systems after deployment. We argue that one reason for the huge state spaces of contemporary embedded and cyber-physical systems is the large variety of operating contexts, which are unknown during design. Once the system is deployed, these contexts become observable, confining several variables. By this, the search space is dramatically reduced, making verification possible even on the limited resources of a deployed system. In this paper, we propose a design and verification flow which exploits this observation. We show how specifications are transferred to the deployed system and verified there. Evaluations on a number of case studies demonstrate the reduction of the search space, and we sketch how the proposed approach can be employed in practice.

Hardware/software co-designs are usually defined at high levels of abstractions at the beginning of the design process in order to allow plenty of options how to eventually realize a system. This allows for design exploration which in turn heavily relies on knowing the costs of different design configurations (with respect to hardware usage as well as firmware metrics). To this end, methods for cost estimation are frequently applied in industrial practice. However, currently used methods for cost estimation oversimplify the problem and ignore important features - leading to estimates which are far off from the real values. In this work, we address this problem for memory systems. To this end, we borrow and re-adapt solutions based on Machine Learning (ML) which have been found suitable for problems from the domain of Computer Vision (CV) - in particular age determination of persons depicted in images. We show that, for an ML approach, age determination from the CV domain is actually very similar to cost estimation of a memory system.

Quantum computers promise substantial speedups over conventional machines for many practical applications. While considered "dreams of the future" for a long time, first quantum computers are available now which can be utilized by anyone. A leading force within this development is IBM Research which launched the IBM Q Experience - the first industrial initiative to build universal quantum computers and make them accessible to a broad audience through cloud access. Along this initiative, the tool Qiskit has been launched which enables researchers, teachers, developers, and general enthusiasts to write corresponding code and to run experiments on those machines. At the same time, this provides an ideal playground for the design automation community which - through Qiskit - can deploy improved solutions e.g. on designing and realizing quantum applications. This special session summary aims to provide an introduction into Qiskit and is showcasing selected success stories on how to work with and develop for it. In addition to that, it provides corresponding references to further readings in terms of tutorials and scientific papers as well as links to publicly available implementations for Qiskit extensions.

Quantum computation is a promising research field since it allows to conduct certain tasks exponentially faster than on conventional machines. As in the conventional domain, decision diagrams are heavily used in different design tasks for quantum computation like synthesis, verification, or simulation. However, unlike decision diagrams for the conventional domain, decision diagrams for quantum computation as of now suffer from a trade-off between accuracy and compactness that requires parameter fine-tuning on a case-by-case basis. In this work, we-for the first time-describe and evaluate the effects of this trade-off. Moreover, we propose an alternative approach that utilizes an algebraic representation of the occurring irrational numbers and outline how this can be incorporated in a decision diagram in order to overcome this trade-off.

The simulation of quantum computations basically boils down to the multiplication of vectors (describing the respective quantum state) and matrices (describing the respective quantum operations). However, since those matrices/vectors are exponential in size, most of the existing solutions (relying on arrays for their representation) are either limited to rather small quantum systems or require substantial hardware resources. To overcome these shortcomings, solutions based on decision diagrams (DD-based simulation) have been proposed recently. They exploit redundancies in quantum states as well as matrices and, by this, allow for a compact representation and manipulation. This offers further (unexpected) potential. In fact, simulation has been conducted thus far by applying one operation (i.e. one matrix-vector multiplication) after another. Besides that, there is the possibility to combine several operations (requiring a matrix-matrix multiplication) before applying them to a vector. But since, from a theoretical perspective, matrix-vector multiplication is significantly cheaper than matrix-matrix multiplication, the potential of this direction was rather limited thus far. In this work, we show that this changes when decision diagrams are employed. In fact, their more compact representation frequently makes matrix-matrix multiplication more beneficial-leading to substantial improvements by exploiting the combination of operations. Experimental results confirm the proposed strategies for combining operations lead to speed-ups of several factors or-when additionally exploiting further knowledge about the considered instance-even of several orders of magnitudes.

Several methods and tools have been proposed which supports designers in verifying embedded systems in early phases of the design process, e.g. at the Electronic System Level (ESL). However, they only show whether an error indeed exists in the system, but it frequently remains open to efficiently locate the source of this error. In this work, we propose a generic error localization methodology. More precisely, by applying code augmentations and conducting further runs of the verification method, it is analyzed what statements may have caused the error. The respectively determined statements then pin-point the verification engineer to possible error locations. By conducing all this on the code level only, the proposed methodology can be applied to any verification method available today. The suitability of the proposed methodology is demonstrated by means of a verification flow based on symbolic execution.

Reversible circuits are needed in different emerging technologies, but their design is still mainly conducted on low abstraction levels thus far. Hardware Description Languages (HDLs) provide suitable description means to lift the design process to higher levels of abstractions. However, synthesis of HDL descriptions thus far still relies on non-reversible building blocks even if the corresponding statements are purely reversible. This leads to reversible circuits with additional circuit lines (i.e., circuit signals)-rendering HDL-based synthesis infeasible for many applications such as quantum computing. In this work, we present a synthesis method which realizes many of the HDL statements with no additional lines at all. To this end, we consider the respective (reversible) HDL statements as an entirety rather than breaking it down into (possibly non-reversible) building blocks. For the first time, this allows to realize many HDL descriptions with no additional circuit lines.

Quantum computing promises substantial speedups by exploiting quantum mechanical phenomena such as superposition and entanglement. Corresponding design methods require efficient means of representation and manipulation of quantum functionality. In the classical domain, decision diagrams have been successfully employed as a powerful alternative to straightforward means such as truth tables. This motivated extensive research on whether decision diagrams provide similar potential in the quantum domain-resulting in new types of decision diagrams capable of substantially reducing the complexity of representing quantum states and functionality. From an implementation perspective, many concepts and techniques from the classical domain can be re-used in order to implement decision diagrams packages for the quantum realm. However, new problems-namely how to efficiently handle complex numbers-arise. In this work, we propose a solution to overcome these problems. Experimental evaluations confirm that this yields improvements of orders of magnitude in the runtime needed to create and to utilize these decision diagrams. The resulting implementation is publicly available as a quantum DD package at http://iic.jku.at/eda/research/quantum_dd.

Due to the ever increasing complexity of modern circuits and systems, verification represents one of the most time-consuming tasks in the entire design process for embedded systems. For this purpose, simulation-based techniques are widely applied in industrial contexts. Here, stimuli are determined which are used as input for the Design under Verification (DUV) and are supposed to trigger different aspects of the new design. However, usually much more stimuli are generated than actually needed to comprehensively cover all aspects. This obviously increases the run time of the verification significantly. Consequently, verification engineers aim for minimizing the number of stimuli after their generation - without loosing their coverage. Existing solutions, however, usually generate results which are far from being optimal. Besides that, their scalability is severely limited. In this work, we propose a solution for an exact minimization of stimuli. To this end, we utilize the computational power of modern reasoning engines such as MAX-SAT solvers which can efficiently minimize a given set of stimuli. Experimental evaluations confirm that, compared to previous work, up to 63% further reduction can be obtained and scalability significantly increases.

The ever increasing complexity of modern systems remains a challenge for semiconductor companies. Once a new chip has been produced, it has to be ensured that it works properly. To this end, sophisticated test environments and test programs are applied. However, to ensure that the applied test program indeed fully covers all important details of the produced chip remains a big challenge. In this work, we propose a methodology which supports the designer by analyzing the coverage of a given test program. To this end, we utilize accomplishments from coverage analysis for functional verification at other abstraction levels. A discussion of the resulting application scenario eventually shows that this allows for an efficient coverage analysis for test programs with basically no changes in the work-flows of test program developers.

The application of coatings by employing Electrophoretic Deposition (EPD) is one of the key processes in automotive manufacturing. Here, car assemblies or entire car bodies are dipped into a tank of liquid aimed for preventing the object from future corrosion. However, this process is highly non-trivial. In fact, it has to be ensured that no air bubbles emerge during the dipping which may lead to an incomplete coverage of the coating. Moreover, entrapped liquids that remained after dipping out may lead to corrosion in the consecutive manufacturing process. To detect such problems in an early development stage, simulation methods based on Computational Fluid Dynamics (CFD) are utilized. Additionally, employing a dedicated volumetric decomposition method, this has led to a tool chain ALSIM which allows to simulate the process of EPD with significantly reduced complexity as compared to standard CFD tools. However, despite these benefits, the method still suffers from large execution times. In this work, we are proposing a parallel scheme which allows for an execution on distributed parallel memory architectures. To that end, dedicated workload distribution and memory optimization methods are presented, which eventually allow for an efficient simulation of EPD coatings. Experimental evaluations based on industrial use cases confirm the obtained benefits: While a serial simulation required more than 8 days, the parallel method proposed in this work allows to complete the simulation with 32 processes in less than 15 hours.

The complexity of droplet microfluidics grows with the implementation of parallel processes and multiple functionalities on a single device. This poses a severe challenge to the engineer designing the corresponding microfluidic networks. In today’s design processes, the engineer relies on calculations, assumptions, simplifications, as well as his/her experiences and intuitions. To validate the obtained specification of the microfluidic network, usually a prototype is fabricated and physical experiments are conducted thus far. In case the design does not implement the desired functionality, this prototyping iteration is repeated—obviously resulting in an expensive and time-consuming design process. To avoid unnecessary debugging loops involving fabrication and testing, simulation methods could help to initially validate the specification of the microfluidic network before any prototype is fabricated. However, state-of-the-art simulation tools come with severe limitations, which prevent their utilization for practically relevant applications. More precisely, they are often not dedicated to droplet microfluidics, cannot handle the required physical phenomena, are not publicly available, and can hardly be extended. In this work, we present an advanced simulation approach for droplet microfluidics that addresses these shortcomings and, eventually, allows simulating practically relevant applications. To this end, we propose a simulation framework at the one-dimensional analysis model, which directly works on the specification of the design, supports essential physical phenomena, is publicly available, and is easy to extend. Evaluations and case studies demonstrate the benefits of the proposed simulator: While current state-of-the-art tools were not applicable for practically relevant microfluidic networks, the proposed simulator allows reducing the design time and costs, e.g., of a drug screening device from one person month and USD 1200, respectively, to just a fraction of that.

Reversible circuits employ a computational paradigm that is beneficial for several applications, including the design of encoding and decoding devices, low-power design, and emerging applications inquantum computation. However, similarly to conventional logic, reversible circuits are expected to be subject toIntellectual Property/Integrated Circuit piracy. To counteract such attacks, an understanding of how to identify the target function from a reversible circuit is a crucial first step. In contrast to conventional logic, the target function is (implicitly or explicitly) embedded into the reversible circuit. Numerous synthesis approaches have been proposed for this embedding task. To recover the target function embedded in a reversible circuit, one needs to know what synthesis approach has been used to embed the circuit. We propose a machine-learning-based scheme to determine the used reversible synthesis approach based on the telltale signs it leaves in the synthesized reversible circuit. We study the impact of optimizing the synthesis approaches on the telltale signs that they leave. Our analysis shows that the synthesis approaches can be determined in the vast majority of cases even if optimized versions of the synthesis approaches are used.

Field-coupled Nanocomputing (FCN) technologies provide an alternative to conventional CMOS-based computation technologies and are characterized by intriguingly low-energy dissipation. Accordingly, their design received significant attention in the recent past. FCN circuit implementations like Quantum-dot Cellular Automata (QCA) or Nanomagnet Logic (NML) have already been built in labs and basic operations such as inverters, Majority, AND, OR, and so on, are already available. The design problem basically boils down to the question of how to place basic operations and route their connections so that the desired function results while, at the same time, further constraints (related to timing, clocking, path lengths, etc.) are satisfied. While several solutions for this problem have been proposed, interestingly no clear understanding about the complexity of the underlying task exists thus far. In this research note, we consider this problem and eventually prove that placement and routing for tile-based FCN circuits is NP -complete. By this, we provide a theoretical foundation for the further development of corresponding design methods.

Two-phase flow microfluidics is a sophisticated and frequently applied Labs-on-Chip (LoC) technology as they allow to automatically conduct medical/biochemical experiments. In this technology, small volumes of reagents, so-called droplets, flow in an immiscible continuous flow inside closed channels making it particularly biocompatible. In the recent past, this technology was extended by a concept allowing to passively navigate droplets through the system-leading to so-called Networked Labs-on-Chips (NLoCs). After the design of an NLoC architecture which defines the comprising connectivity between components and, by this, how the considered medical/biochemical experiments are supposed to be realized, the question remains how to properly dimension the used components, i.e. especially how to dimension the used channels. However, this is a challenging task which is conducted manually thus far and frequently leads to specifications that do not work as intended. In this paper, we are addressing this issue by providing the designer with methods that allow to 1) automatically validate whether a chosen specification of an NLoC indeed works as intended and 2) automatically dimension NLoCs. Case studies demonstrate the importance and usefulness of the proposed methods for determining proper specifications of NLoCs.

Microfluidic chips are now being increasingly used for fast and cost-effective implementation of biochemical protocols. Sample preparation involves dilution and mixing of fluids in certain ratios, which are needed for most of the protocols. On a digital microfluidic biochip (DMFB), these tasks are usually automated as a sequence of droplet mix-split steps. In the most widely used (1:1) mix-split operation for DMFBs, two equal-volume droplets are mixed followed by a split operation, which, ideally, should produce two daughter-droplets of equal volume (balanced splitting). However, because of uncertain variabilities in fluidic operations, the outcome of droplet-split operations often becomes erroneous, i.e., they may cause unbalanced splitting. As a result, the concentration factor (CF) of each constituent fluid in the mixture may become erroneous during sample preparation. All traditional approaches aimed to recover from such errors deploy on-chip sensors to detect possible volumetric imbalance, and adopt either checkpointing-based rollback or roll-forward techniques. Most of them suffer from significant overhead in terms of assay-completion time, reactant-cost, and uncertainties in termination due to randomly occurring split-errors. In this paper, we propose a new approach to accurate dilution preparation on a DMFB that is oblivious to volumetric split-errors. It does not need any sensor and can handle multiple split-errors, deterministically. The proposed method is customized for each target-CF based on the criticality of split-errors in each mix-split step. Simulation experiments on various test-cases demonstrate the effectiveness of the proposed method.

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- 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 h 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 are publicly available at http://iic.jku.at/eda/research/ibm_qx_mapping.

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 paper, 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://iic.jku.at/eda/research/quantum_simulation.

The research community expects that quantum computers will give economical results for particular problems on which the classical computers break down. Examples include factoring of large numbers, searching in a big database, or simulating chemical reactions to design new drugs. Attempts are ongoing to build up a practical quantum computer. Users (clients) can implement quantum circuits to run on these quantum computers. However, before running the quantum circuit on the quantum computer, the users (clients) should compile, optimize, decompose, and technology map the quantum circuit. In the current embodiment, the resulting quantum circuit runs on a remote and untrusted quantum computer server -- introducing security risks. This study explores the risk of outsourcing the quantum circuit to the quantum computer by focusing on quantum oracles. Quantum oracles are pivotal building blocks and require specialized expertise and means to design. Hence, the designer may protect this proprietary quantum oracle intellectual property (IP) and hide his/her private information. We investigate how to manage that on a quantum computer server using the IBM project QX quantum computer and Qiskit tools as an exemplar.

Due to their shrinking feature sizes as well as environmental influences, such as high-energy radiation, electrical noise, and particle strikes, integrated circuits are getting more vulnerable to transient faults. Accordingly, how to make those circuits more robust has become an essential step in today's design flows. Methods increasing the robustness of circuits against these faults already exist for a long period of time but either introduce huge additional logic, change the timing behavior of the circuit, or are applicable for dedicated circuits such as microprocessors only. In this paper, we propose an alternative method, which overcomes these drawbacks by determining application-specific knowledge of the circuit, namely the relations of flip-flops and when they assume the same value. By this, we exploit partial redundancies, which are inherent in most circuits anyway (even the optimized ones), to frequently compare the circuit signals for their correctness-eventually leading to an increased robustness. Since determining the correspondingly needed information is a computationally hard task, formal methods, such as bounded model checking, satisfiability-based automatic test pattern generation, and binary decision diagrams, are utilized for this purpose. The resulting methodology requires only a slight increase in additional hardware, does only influence the timing behavior of the circuit negligibly, and is automatically applicable to arbitrary circuits. Experimental evaluations confirm these benefits.

Reversible circuits employ a computing paradigm that is useful in a broad variety of applications. With increasing interest, security concerns for those circuits also will rise in the near future. At first glance, reversible circuits seem to be more secure to integrated circuit (IC)/intellectual property (IP) piracy than conventional circuits, since the target function is usually embedded in the reversible backbone circuit. This embedding adds ancillary inputs and garbage outputs that may appear to hide the target function. However, recent work showed that target function embedding and reversible synthesis methods leave telltale signs in the reversible circuits, which allow for an easy extraction of the synthesis approach and the embedded circuit. In this article, we perform an analysis of the IC/IP piracy attacks on reversible circuits. We focus on the reversible circuits generated by the quantum multivalued decision diagram (QMDD)- and binary decision diagram (BDD)-based synthesis approaches as case studies. We show that most of the target function can be identified using the telltale signs of the synthesis approach. We then propose a cost-effective input-output scrambling scheme that wipes out these telltale signs and, thus, thwarts the considered attacks by adding reversible gates. Those additional gates yield efficient yet secure reversible circuits.

In the domain of microfluidic devices, a paradigm shift from application-specific to fully-programmable solutions takes place (a similar development from ASICS to FPGAs has been observed in conventional circuitry). So-called Programmable Microfluidic Devices (PMDs) provide a promising platform in this regard. Here, fluids can be pushed into various reaction vessels whose inflow and outflow is controlled by valves. The regular structure in combination with the flexibility of defining various flow paths through valves allows to realize a vast range of biological or chemical applications by only changing the corresponding valve-control sequence. However, determining a sound valve-control constitutes a non-trivial task. Although first automatic approaches for this problem have recently been proposed, we show that they frequently yield impractical control sequences. In this work, we address this issue by providing a precise definition of the underlying design task. Afterwards, we present complementary solutions (both exact as well as heuristic) and discuss how they guarantee a sound valve-control. Experimental evaluations demonstrate that the proposed solutions are capable of automatically generating a sound valve-control for PMDs.

Reversible circuits are composed of a set of circuit lines that are passed through a cascade of reversible gates. Since the number of circuit lines is crucial, functional logic synthesis approaches have been proposed which realize circuits where the number of circuit lines is minimal. However, since the function to be realized is often non-reversible, additional variables have to be added to the function in order to establish reversibility - leading to a significant overhead that affects the scalability of the synthesis method and yields rather complex circuits. In this work, we propose to overcome these problems by exploiting coding techniques in the logic synthesis of reversible circuits. To this end, we propose an intermediate encoding of the output patterns that requires fewer additional inputs and outputs. Using this synthesis scheme allows to perform the majority of the synthesis on significantly fewer variables and to exploit several don't care values in the code. Experimental evaluations - where we obtain better scalability and circuits with magnitudes fewer costs - confirmed the benefits of the proposed synthesis approach.

Recent advances in microfluidics have been the major driving force behind the ubiquity of Labs-on-Chip (LoC) in biochemical protocol automation. The preparation of dilutions and mixtures of fluids is a basic step in sample preparation for which several algorithms and chip-architectures are well known. Dilution and mixing are implemented on biochips through a sequence of basic fluid-mixing and splitting operations performed in certain ratios. These steps are abstracted using a mixing graph. During this process, on-chip storage-units are needed to store intermediate fluids to be used later in the sequence. This allows to optimize the reactant-costs, to reduce the sample-preparation time, and/or to achieve the desired ratio. However, the number of storage-units is usually limited in given LoC architectures. Since this restriction is not considered by existing methods for sample preparation, the results that are obtained are often found to be useless (in the case when more storage-units are required than available) or more expensive than necessary (in the case when storage-units are available but not used, e.g., to further reduce the number of mixing operations or reactant-cost). In this paper, we present a storage-aware algorithm for sample preparation with flow-based LoCs which addresses these issues. We present a SAT-based approach to construct a mixing graph that enables the best usage of available storage-units while optimizing sample-preparation cost and/or time. Experimental results on several test cases reveal the scope, effectiveness, and the flexibility of the proposed method.

The Clifford+T library provides robust and fault-tolerant realizations for quantum computations. Consequently, (logic) synthesis of Clifford+T quantum circuits became an important research problem. However, previously proposed solutions are either only applicable to very small quantum systems or lead to circuits that are far from being optimal- mainly caused by a local, i.e. column-wise, consideration of the underlying transformation matrix to be synthesized. In this paper, we suggest an improved approach that considers the matrix globally and, by this, overcomes many of these drawbacks. Preliminary evaluations show the promises of this direction.

Quantum-dot Cellular Automata (QCA) are an emerging computation technology in which basic states are represented by nanosize particles and logic operations are conducted through corresponding effects such as Coulomb interaction. This allows to overcome physical boundaries of conventional solutions such as CMOS and, hence, constitutes a promising direction for future computing devices. Despite these promises, however, the development of (automatic) design methods for QCAs is still in its infancy. In fact, QCA circuits are mainly designed manually thus far and only few heuristics are available. This frequently leads to unsatisfactory results and generally makes it hard to evaluate the quality of respective QCA designs. In this work, we propose an exact solution for the design of QCA circuits that can be configured e.g. to generate circuits that satisfy certain design objectives and/or physical constraints. For the first time, this allows for design exploration of QCA circuits. Experimental evaluations and case studies demonstrate the benefit of the proposed solution.

In March 2017, IBM launched the project IBM Q 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). In order to use these, the desired quantum functionality (e.g. provided in terms of a quantum circuit) has to properly be mapped so that the underlying physical constraints are satisfied - a complex task. This demands for solutions to automatically and efficiently conduct this mapping process. In this paper, we propose such an approach which satisfies all constraints given by the architecture and, at the same time, aims to keep the overhead in terms of additionally required quantum gates minimal. The proposed approach is generic and can easily be configured for future architectures. Experimental evaluations show that the proposed approach clearly outperforms IBM's own mapping solution with respect to runtime as well as resulting costs.

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.

Quantum-Dot Cellular Automata (QCA) are an emerging nanotechnology with remarkable performance and energy efficiency. Computation and information transfer in QCA is based on field forces rather than electric currents. As a consequence, new strategies are required for design automation approaches in order to cope with the arising challenges. One of these challenges rises from the fact that QCA is a planar technology. That means, logic gates as well as interconnection elements are mostly located in the same layer. Hence, it is expected that interconnections have higher influence on the final design costs than in conventional integrated technologies. For the first time, this paper presents an extensive study on the quantification of this impact. Therefore, we consider the entire design flow for QCA circuits from the initial synthesis (using different synthesis approaches) to the corresponding placement on a QCA grid. Then, we characterize the respectively obtained QCA circuits in terms of area, delay and energy costs. The obtained results indicate that the impact of interconnections in QCA is indeed substantial. Design costs including or not including interconnections differ by several orders of magnitudes, which motivates to completely re-think how logic synthesis for QCA circuits shall be conducted in the future.

This overview paper summarizes the content of a tutorial given at the 2018 edition of the Forum on specification & Design Languages. The aim of the tutorial was to introduce the technology of microfluidic devices, which gained significant interest in the recent past, as well as corresponding design challenges to a community focused on design automation and corresponding specification/design languages. By this, the overview presents a starting point for researchers and engineers interested in getting involved in this area.

Reversible logic is a building block for adiabatic and quantum computing in addition to other applications. Since common functions are non-reversible, one needs to embed them into proper-size reversible functions by adding ancillary inputs and garbage outputs. We explore the Intellectual Property (IP) piracy of reversible circuits. The number of embeddings of regular functions in a reversible function and the percent of leaked ancillary inputs measure the difficulty of recovering the embedded function. To illustrate the key concepts, we study reversible logic circuits designed using reversible logic synthesis tools based on Binary Decision Diagrams and Quantum Multi-valued Decision Diagrams.

Quantum computation is currently moving from an academic idea to a practical reality. The recent past has seen tremendous progress in the physical implementation of corresponding quantum computers - also involving big players such as IBM, Google, Intel, Rigetti, Microsoft, and Alibaba. These devices promise substantial speedups over conventional computers for applications like quantum chemistry, optimization, machine learning, cryptography, quantum simulation, and systems of linear equations. The Computer-Aided Design and Verification (jointly referred as CAD) community needs to be ready for this revolutionizing new technology. While research on automatic design methods for quantum computers is currently underway, there is still far too little coordination between the CAD community and the quantum computation community. Consequently, many CAD approaches proposed in the past have either addressed the wrong problems or failed to reach the end users. In this summary paper, we provide a glimpse into both sides. To this end, we review and discuss selected accomplishments from the CAD domain as well as open challenges within the quantum domain. These examples showcase the recent state-of-the-art but also outline the remaining work left to be done in both communities.

Continuous flow-based biochips are one of the promising platforms used in biochemical and pharmaceutical laboratories due to their efficiency and low costs. Inside such a chip, fluid volumes of nanoliter size are transported between devices for various operations, such as mixing and detection. The transportation channels and corresponding operation devices are controlled by microvalves driven by external pressure sources. Since assigning an independent pressure source to every microvalve would be impractical due to high costs and limited system dimensions, states of microvalves are switched using a control logic by time multiplexing. Existing control logic designs, however, still switch only a single control channel per operation – leading to a low efficiency. In this paper, we propose the first automatic synthesis approach for a control logic that is able to switch multiple control channels simultaneously to reduce the overall switching time of valve states. In addition, we propose the first fault-aware design in control logic to introduce redundant control paths to maintain the correct function even when manufacturing defects occur. Compared with the existing direct connection method, the proposed multi-channel switching mechanism can reduce the switching time of valve states by up to 64%. In addition, all control paths for fault tolerance have been realized.

Labs-on-Chips (LoCs) implement laboratory procedures on a single chip and are successfully used for chemical and biomedical applications. A promising and emerging realization of such chips are Networked LoCs (NLoCs) in which small volumes of fluids, so-called droplets, flow in closed channels of submillimeter diameters. NLoCs allow for an incubation and storage of assays over a long period of time and, hence, avoid evaporation and unwanted reactions. To increase the flexibility, effectiveness, and reusability, network functionalities allow to passively route droplets in channels and, hence, to dynamically select operations depending on the executed experiment. However, only manually designed architectures are considered for NLoCs thus far. They frequently suffer from large execution times and/or a high contamination of channels. To overcome these drawbacks, we propose the consideration of application-specific architectures for NLoCs. To this end, an automatic design method is proposed which, for a given set of experiments as well as constraints and objectives from the designer, is able to generate an optimized NLoC architecture realizing these experiments. Evaluations and case studies demonstrate the potential of the proposed solution for design exploration. Moreover, we are able to show that application-specific architectures are capable of realizing experiments in just a fraction of the time needed by architectures used thus far as well as with a substantially reduced contamination.

Quantum-dot cellular automata (QCA) are an emerging field-coupled nanotechnology with remarkable performance and energy efficiency. In order to enable the exploration of this technology, we propose a model for the logic synthesis of QCA circuits that, for the first time, considers and abstracts all main physical aspects-in particular, energy dissipation. To this end, we review in detail how energy is dissipated in QCA cells and present a corresponding environment that allows for the estimation of the energy dissipation with respect to any specific set of technology parameters. Based on that, we derive a model for logic synthesis. A case study confirms the accuracy of the proposed model and reveals that interconnections have a significant impact in this technology-motivating a more rigorous consideration. These findings eventually provide the basis for a new generation of synthesis approaches at the logic level that are explicitly dedicated to QCA systems.

Flow-based microfluidic biochips are attracting increasing attention with successful applications in biochemical experiments, point-of-care diagnosis, etc. Existing works in design automation consider the flow-layer design and control-layer design separately, lacking a global optimization and hence resulting in degraded routability and reliability. This paper presents a novel integrated physical co-design methodology, which seamlessly integrates the flow-layer and control-layer design stages. In the flow-layer design stage, a sequence-pair-based placement method is presented, which allows for an iterative placement refinement based on routing feedbacks. In the control-layer design stage, the minimum cost flow formulation is adopted to further improve the routability. Besides that, effective placement adjustment strategies are proposed to iteratively enhance the solution quality of the overall control-layer design. Experimental results show that compared with the existing work, the proposed design flow obtains an average reduction of 40.44% in flow-channel crossings, 31.95% in total chip area, and 22.02% in total flow-channel length. Moreover, all the valves are successfully routed in the control-layer design stage.

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.

Continuous-flow microfluidics rapidly evolved in the last decades as a solution to automate laboratory procedures in molecular biology and biochemistry. Therefore, the physical design of the corresponding chips, i.e., the placement and routing of the involved components and channels, received significant attention. Recently, several physical design solutions for this task have been presented. However, they often rely on general heuristics which traverse the search space in a rather arbitrary fashion and, additionally, consider placement and routing independently from each other. Consequently, the obtained results are often far from being optimal. In this work, a methodology is proposed which aims for determining close-to-optimal physical designs for continuous-flow microfluidic biochips. To this end, we consider all - or, at least, as much as possible - of the valid solutions. As this obviously yields a significant complexity, solving engines are utilized to efficiently traverse the search space and pruning schemes are proposed to reduce the search space without discarding too many promising solutions. Evaluations show that the proposed methodology is capable of determining optimal results for small experiments to be realized. For larger experiments, close-to-optimal results can efficiently be derived. Moreover, compared to the current state-of-the-art, improvements of up to 1-2 orders of magnitude can be observed.

Due to shrinking feature sizes, integrated circuits are getting more vulnerable against transient faults. Methods increasing the robustness of circuits against these faults already exist for a long period of time but either introduce huge additional logic, increase the latency of the circuit, or are applicable for dedicated circuits such as microprocessors only. This work proposes an alternative hardening method which requires only a slight increase in additional hardware, does not influence the timing behavior, and is automatically applicable to arbitrary circuits. To this end, application-specific knowledge of the considered circuit is exploited, analyzed by a dedicated orchestration of formal techniques, and, eventually, used to synthesize a fault detection mechanism enhancing the robustness of the circuit. Experimental evaluations show that the proposed solution leads to a significant increase in the robustness, while the hardware overhead is kept moderate.

Digital microfluidics is an emerging technology that provide fluidic-handling capabilities on a chip. One of the most important issues to be considered when conducting experiments on the corresponding biochips is the routing of droplets. A recent variant of biochips uses a micro-electrode-dot-array (MEDA) which yields a finer controllability of the droplets. Although this new technology allows for more advanced routing possibilities, it also poses new challenges to corresponding CAD methods. In contrast to conventional microfluidic biochips, droplets on MEDA biochips may move diagonally on the grid and are not bound to have the same shape during the entire experiment. In this work, we present an exact routing method that copes with these challenges while, at the same time, guarantees to find the minimal solution with respect to completion time. For the first time, this allows for evaluating the benefits of MEDA biochips compared to their conventional counterparts as well as a quality assessment of previously proposed routing methods in this domain.

Labs-on-Chip integrate and minimize the functionality of complete conventional laboratories on a single chip. An upcoming and especially biocompatible realization are Networked Labs-on-Chips (NLoCs). In NLoCs, small volumes of reagents, so-called droplets, flow in an immiscible fluid in closed channels. An external pump applies a force to this immiscible fluid driving the droplets through the channels of the NLoC. However, the exact flow behavior of droplets in NLoCs physically depends on many factors and interdependencies. This makes it cumbersome to manually determine the taken path of a droplet and the time it needs to pass the NLoC. For the same reason, also almost no automated design solutions exist for NLoCs yet. In this work, we present a discrete model enabling designers and design automation tools to efficiently determine the droplets' path and positions. The precision of the proposed model is evaluated by a systematic examination for basic building blocks of NLoCs as well as for a complete architecture. The resulting model can be used for manual inspections of the droplets' behavior in an NLoC and, additionally, provides the basis for automated design solutions.

Labs-on-Chips (LoCs) revolutionize conventional biochemical processes and may even replace laboratories by integrating and minimizing their functionalities on a single chip. In a promising and emerging realization of LoCs, small volumes of reagents, so-called droplets, transport the biological sample and flow in closed channels of sub-millimeter diameters. This realization is called Networked Labs-on-Chips (NLoCs). The architecture of an NLoC defines different paths through which the droplets can flow. These paths are realized by splitting channels into multiple successor channels - so-called bifurcations. However, whether the architecture indeed allows to route droplets along the desired paths and, hence, correctly executes the intended experiment is not guaranteed. In this work, we present the first automatic solution for verifying whether an NLoC architecture allows to correctly route the droplets. Our evaluations demonstrate the applicability and importance of the proposed solution on a set of NLoC architectures.

Reversible computation became established as a promising concept due to its application in various areas like quantum computation, energy-aware circuits, and further areas. Unfortunately, most functions of interest are non-reversible. Therefore, a process called embedding has to be conducted to transform a non-reversible function into a reversible one - a coNP-hard problem. Existing solutions suffer from the resulting exponential complexity and, hence, are limited to rather small functions only. In this work, an approach is presented which tackles the problem in an entirely new fashion. We divide the embedding process into matrix operations, which can be conducted efficiently on a certain kind of decision diagram. Experiments show that improvements of several orders of magnitudes can be achieved using the proposed method. Moreover, for many benchmarks exact results can be obtained for the first time ever.

Encoders play an important role in many areas such as memory addressing, data demultiplexing, or for interconnect solutions. However, design solutions for the automatic synthesis of corresponding circuits suffer from various drawbacks, e.g. they are often not scalable, do not exploit the full degree of freedom, or are applicable to realize certain codes only. All these problems are caused by the fact that existing design solutions have to explicitly guarantee a one-to-one mapping. In this work, we propose an alternative design approach which relies on dedicated description means for both, the specification of an encoder as well as its circuit. Based on that, synthesis can be conducted without the need to explicitly take care of guaranteeing one-to-one mappings. Experiments show that this indeed overcomes the drawbacks of current design solutions and leads to an improvement in the resulting number of gates by up to 92%.

For the manufacturing test of ASICs, it is important to reach a high test coverage in order to get the defect level as low as possible. However, complex digital circuits are usually not fully testable. In order to address that, previous work suggested to realize the circuits by means of Binary Decisions Diagrams (BDDs). Here, each node is implemented using multiplexer gates (MUX gates) which, with some minor additions, yield 100% testable circuits with respect to stuck-at and path-delay faults. Unfortunately, current physical implementations of MUX gates are rather expensive with respect to propagation delay, power consumption, or transistor count. Hence, despite the prospect of gaining 100% testability, BDD-based circuits did not find significant attention yet. In this work, we propose an alternative realization of MUX gates based on pass transistor logic which addresses these drawbacks. Experiments show that this allows for the realization of fully testable BDD-based circuits which are competitive to or, in many cases, even better than state-of-the-art realizations.

Binary decision diagrams are fundamental data structures in discrete mathematics, electrical engineering and computer science. Many different variations of binary decision diagrams exist, in particular variations that employ different reduction rules. For some applications, such as on-the-fly state space exploration, multiple reduction rules are beneficial to minimize the size of the involved graphs. We propose tagged binary decision diagrams, an edge-based approach that allows to use two reduction rules simultaneously. Experimental evaluations demonstrate that on-the-fly state space exploration is an order of magnitude faster using tagged binary decision diagrams compared to traditional binary decision diagrams.

On a droplet-based Labs-on-Chip (LoC) device, tiny volumes of fluids, so-called droplets, flow in channels of micrometer scale. The droplets contain chemical/biological samples that are processed by different modules on the LoC. In current solutions, an LoC is a single-purpose device that is designed for a specific application, which limits its flexibility. In order to realize a multi-purpose system, different modules are interconnected in a microfluidic network — yielding so-called Networked LoCs (NLoCs). In NLoCs, the droplets are routed to the desired modules by exploiting hydrodynamic forces. A well established topology for NLoCs are ring networks. However, the addressing schemes provided so far in the literature only allow to address multiple modules by re-injecting the droplet at the source every time, which is a very complex task and increases the risk of ruining the sample. In this work, we address this issue by revising the design of the network nodes, which include the modules. A novel configuration allows the droplet to undergo processing several times in cascade by different modules with a single injection. Simulating the trajectory of the droplets across the network confirmed the validity of our approach.

Optical circuits received significant interest as a promising alternative to existing electronic systems. Because of this, also the synthesis of optical circuits receives increasing attention. However, initial solutions for the synthesis of optical circuits either rely on manual design or rather straight-forward mappings from established data-structures such as BDDs, SoPs/ESoPs, etc. to the corresponding optical netlist. These approaches hardly utilize the full potential of the gate libraries available in this domain. In this paper, we propose an alternative synthesis solution based on AND-Inverter Graphs (AIGs) which is capable of utilizing this potential. That is, a scheme is presented which dedicatedly maps the given function representation to the desired circuit in a one-to-one fashion - yielding significantly smaller circuit sizes. Experimental evaluations confirm that the proposed solution generates optical circuits with up to 97% less number of gates as compared to existing synthesis approaches.

Reversible circuits are vulnerable to intellectual property and integrated circuit piracy. To show these vulnerabilities, a detailed understanding on how to identify the function embedded in a reversible circuit is crucial. To obtain the embedded function, one needs to know the synthesis approach used to generate the reversible circuit in the first place. We present a machine learning based scheme to identify the synthesis approach using telltale signs in the design.

UML/OCL models are used to describe system models in early stages of the design process. In order to detect design flaws in these models as soon as possible (ideally before the implementation phase starts), various methods for the validation and verification of UML/OCL models have been proposed. In particular, automatic solutions (so-called model finders) are of interest here. They provide designers with quick feedback, e. g., on the consistency of their models in a push-button fashion. But thus far, all proposed approaches support a (small) subset of UML/OCL only or employ substantial restrictions. In fact, there are only few solutions that support the extended type system including the irregular values null and invalid - although these values play an important role for covering exceptional cases. Moreover, these solutions either heavily rely on manual interaction or significantly restrict the supported UML/OCL description means. In this work, we propose a generic formal representation of UML/OCL which can be used for the validation and verification of corresponding models and, at the same time, addresses these shortcomings.

The use of formal models to describe early versions of the structure and the behavior of a system has become common practice in industry. UML and OCL are the de-facto specification languages for these tasks. They allow for capturing system properties and module behavior in an abstract but still formal fashion. At the same time, this enables designers to detect errors or inconsistencies in the initial phases of the design flow-even if the implementation has not already started. Corresponding tools for verification of formal models got established in the recent past. However, verification results are usually not reused in later design steps anymore. In fact, similar verification tasks are applied again, e.g., after the implementation has been completed. This is a waste of computational and human effort. In this paper, we address this problem by proposing a method which checks a given implementation of a system against its corresponding formal method. This allows for transferring verification results already obtained from the formal model to the implementation and, eventually, motivates a new design flow which addresses verification across abstraction levels. This paper describes the applied techniques as well as their orchestration. Afterwards, the applicability of the proposed methodology is demonstrated by means of examples as well as a case study from an industrial context.

Ensuring nearest neighbor compliance of quantum circuits by inserting SWAP gates has heavily been considered in the past. Here, quantum gates are considered which work on non-adjacent qubits. SWAP gates are applied in order to “move” these qubits onto adjacent positions. However, a decision how exactly the SWAPs are “moved” has mainly been made without considering the effect a “movement” of qubits may have on the remaining circuit. In this work, we propose a methodology for nearest neighbor optimization which addresses this problem by means of a look-ahead scheme. To this end, two representative implementations are presented and discussed in detail. Experimental evaluations show that, in the best case, reductions in the number of SWAP gates of 56% (compared to the state-of-the-art methods) can be achieved following the proposed methodology.

While previous decades have witnessed impressive accomplishments in the design and realization of conventional computing devices, physical boundaries and cost restrictions led to an increasing interest in alternative technologies (often referred to as Beyond CMOS or More than Moore technologies). In addition, these accomplishments also triggered many “complementary” applications and led to technologies providing an additional value to the conventional logic (often referred to as More than Moore). This led to a variety of emerging technologies such as Quantum Computation, Optical Circuits, or Microfluidic Biochips out of which many are considered very promising and some even entered the market recently. This poses new challenges to researchers and engineers working in computer-aided design. In this tutorial paper, we provide an overview on the main concepts of selected emerging technologies as well as the resulting design methods. To this end, we review the respective technological background and introduce the correspondingly used circuit models. Based on that, we show how computer-aided design has to adapt the common design tasks and review recently proposed solutions.

The specification of non-functional requirements, e. g., on timing forms an essential part of modern system design. Modeling languages such as MARTE/CCSL provide dedicated description means enabling engineers to formally define the ticking of the clocks to be implemented in terms of clock constraints and the actually intended timing behavior in terms of instant relations. But thus far, instant relations have only been utilized in order to monitor the correct execution of the clock constraints. In this work, we propose a methodology which, for the first time, verifies clock constraints against the given instant relations. To this end, the timing behavior is represented in terms of an automaton followed by its verification through satisfiability solvers. A case study illustrates the application of the proposed methodology.

Verification and validation of UML/OCL models is a crucial task in the design of complex software/hardware systems. The behavior in those models is expressed in terms of operations with pre- and postconditions. These, however, are often not precise enough to describe what may or may not be modified in a transition between two system states. This frame problem is commonly addressed by providing additional constraints in terms of so-called frame conditions and has already been considered in different research areas in the last decades - except for UML/OCL where corresponding approaches have been investigated only recently. Besides that, several approaches for the verification of the behavior specified in UML/OCL models have been proposed. They rely on a symbolic representation of all possible system states and transitions between them. But here, frame conditions have not been considered yet - a significant drawback for the underlying verification approaches. In this paper, we describe how to integrate frame conditions to symbolic representations. This enables designers to verify the behavior of UML/OCL models while, at the same time, respecting the given frame conditions.

In this article, we introduce a novel method of synthesizing symmetric Boolean functions with reversible logic gates. In contrast to earlier approaches, the proposed technique deploys a simple, regular, and cascaded structure consisting of an array of Peres and CNOT gates, which results in significant reduction with respect to the quantum cost. However, the number of circuit inputs may increase slightly when such cascades are used. In order to reduce their number, we next propose a postsynthesis optimization phase that allows judicious reuse of circuit lines. In addition to offering a cost-effective synthesis methodology, the proposed reversible logic structure supports elegant testability properties. With respect to all single or partial missing gate faults (SMGFs and PMGFs), or repeated gate faults (RGFs) in such an n -input circuit module, we show that it admits a universal test set of constant cardinality (=3) for any value of n . Thus, considering both the cost and testability issues, this approach provides a superior option for synthesizing symmetric functions compared to existing designs.

Optical circuits are considered a promising emerging technology for applications in ultra-high-speed networks or interconnects. However, the development of (automatic) synthesis approaches for such circuits is still in its infancy. Although first generic and automatic synthesis approaches have been proposed, no clear understanding exists yet on how to keep the costs of the resulting circuits as small as possible. In the domain of optical circuits, this is particularly interesting for the number of gates and the effect of so-called splitters to the signal strength. In this work, we investigate this relation by considering a variety of (existing as well as proposed) synthesis approaches for optical circuits. Our investigations show that reducing the number of gates and reducing the number of splitters are contradictory optimization objectives. Furthermore, the performance of synthesis guided with respect to gate efficiency as well as synthesis guided with respect to splitter freeness is evaluated and an overhead factor between the contradictory metrics is experimentally determined.

Reversible logic represents the basis for many emerging technologies and has recently been intensively studied. However, most of the Boolean functions of practical interest are irreversible and must be embedded into a reversible function before they can be synthesized. Thus far, an optimal embedding is guaranteed only for small functions, whereas a significant overhead results when large functions are considered. We study this issue in this article. We prove that determining an optimal embedding is coNP-hard already for restricted cases. Then, we propose heuristic and exact methods for determining both the number of additional lines and a corresponding embedding. For the approaches, we considered sum of products and binary decision diagrams as function representations. Experimental evaluations show the applicability of the approaches for large functions. Consequently, the reversible embedding of large functions is enabled as a precursor to subsequent synthesis.

Quantum mechanical phenomena such as phase shifts, superposition, and entanglement show promise in use for computation. Suitable technologies for the modeling and design of quantum computers and other information processing techniques that exploit quantum mechanical principles are in the range of vision. Quantum algorithms that significantly speed up the process of solving several important computation problems have been proposed in the past. The most common representation of quantum mechanical phenomena are transformation matrices. However, the transformation matrices grow exponentially with the size of a quantum system and, thus, pose significant challenges for efficient representation and manipulation of quantum functionality. In order to address this problem, first approaches for the representation of quantum systems in terms of decision diagrams have been proposed. One very promising approach is given by Quantum Multiple-Valued Decision Diagrams (QMDDs) which are able to efficiently represent transformation matrices and also inherently support multiple-valued basis states offered by many physical quantum systems. However, the initial proposal of QMDDs was lacking in a formal basis and did not allow, e.g., the change of the variable order-an established core functionality in decision diagrams which is crucial for determining more compact representations. Because of this, the full potential of QMDDs or decision diagrams for quantum functionality in general has not been fully exploited yet. In this paper, we present a refined definition of QMDDs for the general quantum case. Furthermore, we provide significantly improved computational methods for their use and manipulation and show that the resulting representation satisfies important criteria for a decision diagram, i.e., compactness and canonicity. An experimental evaluation confirms the efficiency of QMDDs.

Motivated by the promises of significant speed-ups for certain problems, quantum computing received significant attention in the past. While much progress has been made in the development of synthesis methods for quantum circuits, new physical developments constantly lead to new constraints to be addressed. The limited interaction distance between the respective qubits (i.e. nearest neighbor optimization) has already been considered intensely. But with the emerge of multi-dimensional quantum architectures, new physical requirements came up for which only a few automatic synthesis solutions exist yet all of them of heuristic nature. In this work, we propose an exact scheme for nearest neighbor optimization in multi-dimensional quantum circuits. Although the complexity of the problem is a serious obstacle, our experimental evaluation shows that the proposed solution is sufficient to allow for a qualitative evaluation of the respective optimization steps. Besides that, this enabled an exact comparison to heuristical results for the first time.

With the advancements in silicon photonics, optical devices have found applications e.g. for ultra-high speed and low-power interconnects as well as functional computations to be realized on-chip. Caused by the increasing complexity of the underlying functionality, also the need for computer-aided design methods for this technology rises. Motivated by that, initial work on the development of synthesis methods for optical circuits has been performed. But all approaches proposed thus far suffer e.g. from unsatisfactory synthesis results or restricted scalability. In particular, splittings in the resulting circuits which degrade the optical signals into hardly measurable fractions prevent an efficient and scalable synthesis for optical circuits. In this work, we present a synthesis approach based on Binary Decision Diagrams (BDDs) that overcomes these obstacles. The approach yields circuits that rely on a total of zero splitters - at the expense of a moderate increase in the number of optical gates. Experiments confirm that, by this, an efficient and scalable synthesis scheme for optical circuits eventually becomes available.

The complexity of today's embedded and cyber-physical systems is rapidly increasing and makes the consideration of higher levels of abstraction during the design process inevitable. In this context, the impact of modeling languages such as UML and its profiles such as MARTE is growing. Here, CCSL provides a formal description of timing constraints which have to be enforced on the considered system. This builds the basis for many further design steps and can be used e. g. for checking the consistency of the specification, for code generation, or for proving whether the time constraints have correctly been implemented at lower abstraction levels. However, most of the approaches available thus far usually focus on sole design tasks only -- often even without an explicit consideration of the system's functional behavior. In this work, we are aiming for overcoming this drawback by providing a method to automatically generate a generic representation of a set of clock constraints in terms of a transition relation. Afterwards, the resulting transition relation can easily be utilized for the above mentioned design tasks. A discussion on the applicability of the generic description as well as an exemplary evaluation shows the promise of the proposed generic representation.

Modeling languages such as UML or SysML in combination with constraint languages such as OCL allow for an abstract description of a system prior to its implementation. But the resulting system models can be highly non-trivial and, hence, errors in the descriptions can easily arise. In particular, too strong restrictions leading to an inconsistent model are common. Motivated by this, researchers and engineers developed methods for the validation and verification of given formal models. However, while these methods are efficient to detect the existence of an inconsistency, the designer is usually left alone to identify the reasons for it. In this contribution, we propose an automatic method which efficiently determines reasons explaining the contradiction in an inconsistent UML/OCL model. For this purpose, all constraints causing the contradiction are comprehensibly analyzed. By this, the designer is aided during the debugging of his/her model.

For the development of complex systems - composed of hardware, software, or both - more and more high-level descriptions have been introduced over the past years. Starting from an informal specification, models of the system are created with the help of languages such as UML, SysML, or MARTE. Based on this model, an implementation is generated in a programming language such as C++, Java, etc. for software or SystemC, VHDL, etc. for hardware. Whereas various approaches for the verification of the single levels of abstraction exist, their application to a cross-level design flow is still to be considered. In this work, we evaluate this issue by providing a case study on a verification-driven design across abstraction levels. The results of this case study demonstrate the capabilities of existing methods as well as challenges and open issues to be addressed in future work.

Formal models, based on modeling languages such as UML in combination with constraint languages such as OCL, allow for an abstract description of a system prior to its implementation. But since the resulting models are often rather complex, redundancies in terms of model descriptions which can directly be implied from already existing constraints can easily arise. In particular, OCL invariants are affected by this. In order to efficiently detect those, methodologies for the analysis for invariant dependence have recently been proposed. However, they have severe limitations with respect to scalability, automation, and quality of the determined results. In this work, we aim for leveraging the analysis for invariant independence in formal systems models by addressing these drawbacks. For this purpose, a new methodology based on the exploitation of powerful solving engines as well as a complete analysis scheme is proposed. Experimental evaluations confirm that the proposed solution is significantly faster and leads to a much better quality of the results.

Advances in microfluidic technologies have led to the emergence of Digital Microfluidic Biochips (DMFBs), which are capable of automating laboratory procedures in biochemistry and molecular biology. During the design and use of these devices, droplet routing represents a particularly critical challenge. Here, various design tasks have to be addressed for which, depending on the corresponding scenario, different solutions are available. However, all these developments eventually result in an “inflation” of different design approaches for routing of DMFBs - many of them addressing a very dedicated routing task only. In this work, we propose a comprehensive routing methodology which (1) provides one (generic) solution capable of addressing a variety of different design tasks, (2) employs a “push-button”-scheme that requires no (manual) composition of partial results, and (3) guarantees minimality e.g., with respect to the number of timesteps or the number of required control pins. Experimental evaluations demonstrate the benefits of the solution, i.e., the applicability for a wide range of design tasks as well as improvements compared to specialized solutions presented in the past.

Formal methods advanced to an important core technique in Computer-Aided Design (CAD). At the same time, researchers and engineers also started the investigation of so-called emerging technologies such as reversible computation, quantum computation, or optical circuits. Although most of these technologies are still in a rather “academic” state, first physical realizations have already been presented. This motivates a more detailed consideration of how to design circuits for these technologies. As for conventional circuits, formal methods do play an important role here. In this tutorial paper1, we are aiming to address the current momentum caused by the recent accomplishments and provide an overview of these emerging technologies as well as their corresponding CAD methods. This includes a special focus on how formal methods may help in the design and verification of circuits for those technologies.

In behavioral modeling, operation contracts defined by pre- and postconditions describe the effects on model properties (i.e., model elements such as attributes, links, etc.) that are enforced by an operation. However, it is usually omitted which model properties should not be modified. Defining so-called frame conditions can fill this gap. But, thus far, these have to be defined manually - a time-consuming task. In this work, we propose a methodology which aims to support the modeler in the definition of the frame conditions by extracting suggestions based on an automatic analysis of operation contracts provided in OCL. More precisely, the proposed approach performs a structural analysis of pre- and postconditions together with invariants in order to categorize which class and object properties are clearly “variable” or “unaffected” - and which are “ambiguous”, i.e. indeed require a more thorough inspection. The developed concepts are implemented as a prototype and evaluated by means of several example models known from the literature.

The Unified Modeling Language (UML) is a defacto standard for software development and, together with the Object Constraint Language (OCL), allows for a precise description of a system prior to its implementation. At the same time, these descriptions can be employed to check the consistency and, hence, the correctness of a given UML/OCL model. In the recent past, numerous (automated) approaches have been proposed for this purpose. The behavior of the systems has usually been considered by means of sequence diagrams, state machines, and activity diagrams. But with the increasing popularity of design by contract, also composite structures, classes, and operations are frequently used to describe behavior in UML/OCL. However, for these description means no solution for the validation and verification of concurrent behavior is available yet. In this work, we propose such a solution. To this end, we discuss the possible interpretations of “concurrency” which are admissible according to the common UML/OCL interpretation and, afterwards, propose a methodology which exploits solvers for SAT Modulo Theories (i. e., SMT solvers) in order to check the concurrent behavior of UML/OCL models. How to address the resulting problems is described and illustrated by means of a running example. Finally, the application of the proposed method is demonstrated.

In order to cope with the complexity of today's system designs, higher levels of abstraction are considered. Modeling languages such as SysML provide adequate description means for an abstract specification of the structure and the behavior of a system to be implemented. Due to its sufficient degree of formality, SysML additionally allows for performing several automated test and verification tasks. For these tasks, however, a formal encoding of the behavioral model semantics is required; this is typically achieved by generating initial state conditions as well as the transition relation from the model. Since SysML provides a multitude of alternative or complementary notations, this poses a significant challenge to the development of corresponding tool support. In this paper, we therefore propose an alternative approach to the generation of transition relations: In a first step, a model-to-model transformation is applied which unifies the behavioral descriptions into one single notation, namely operations allocated in blocks and specified by pre- and post-conditions. Afterwards, only pre- and post-conditions as well as some auxiliary constraints for fixing semantic variation points need to be considered when generating the transition relation. The approach presented here has been evaluated in the development of industrial tools supporting bounded model checking and model-based test generation.

Quantum circuits established themselves as a promising emerging technology and, hence, attracted considerable attention in the domain of computer-aided design. As a result, many approaches for synthesis of corresponding netlists have been proposed in the last decade. However, as the design of quantum circuits faces serious obstacles caused by phenomena such as superposition, entanglement, and phase shifts, automatic synthesis still represents a significant challenge. In this paper, we propose an automatic synthesis approach for quantum circuits that implement Clifford Group operations. These circuits are essential for many quantum applications and cover core aspects of quantum functionality. The proposed approach exploits specific properties of the unitary transformation matrices that are associated to quantum operations. Furthermore, Quantum Multiple-Valued Decision Diagrams (QMDDs) are employed for an efficient representation of these matrices. Experimental results confirm that this enables a compact realization of the respective quantum functionality.

Motivated by its promising applications e.g. for database search or factorization, significant progress has been made in the development of automated design methods for quantum circuits. But in order to keep up with recent physical developments in this domain, new technological constraints have to be considered. Limited interaction distance between gate qubits is one of the most common of these constraints. This led to the development of several strategies aiming at making a given quantum circuit nearest neighbor-compliant by inserting SWAP gates into the existing structure. Usually these strategies are of heuristic nature. In this work, we present an exact approach that enables nearest neighbor-compliance by inserting a minimal number of SWAP gates. Experiments demonstrate the applicability of the approach which enabled a comparison of results obtained by heuristic methods to the actual optimum.

With the advances of the microfluidic technology, the design of digital microfluidic biochips recently received significant attention. But thus far, the corresponding design tasks such as binding, scheduling, placement, and routing have usually been considered separately. Furthermore, often just heuristic results have been obtained. In this work, we present a one-pass synthesis scheme which directly realizes the desired functionality onto the chip and, at the same time, guarantees minimality with respect to area and/or timing. For this purpose, the deductive power of solvers for Boolean satisfiability is exploited. Experiments show how the approach leverages the design of the respective devices.

Synthesis of reversible circuits has attracted the attention of many researchers. In particular, approaches based on Decision Diagrams (DDs) have been shown beneficial since they enable the realization of corresponding circuits for large functions. However, all existing approaches rely on a gate library composed of positive control lines only. Recently, it has been shown that the additional use of negative control lines enables significant reductions of the respective circuit costs. In this paper, we aim for exploiting this potential. To this end, two complementary schemes are investigated. First, a post-synthesis optimization that exploits the power of negative control lines is utilized to optimize the circuits generated by previously proposed DD-based methods. Second, negative control lines are explicitly considered during synthesis. Experimental results demonstrate that the proposed approaches result in a significant reduction with respect to gate count as well as quantum costs.

Simulation-based verification is still the most frequently used technique when complex designs are to be verified. Stimuli are thereby generated and applied in order to sufficiently trigger and, by this, verify a set of considered scenarios. In general, a scenario can be triggered in various fashions. To ensure a high verification quality, each of these fashions should adequately be covered. However, to the best of our knowledge, this has not appropriately been addressed thus far, i.e. existing stimuli generation is mainly performed without an explicit consideration of the possible fashions in which a scenario might be triggered. To improve this, three approaches are proposed in this work. While examples illustrate their advantages, a case study confirms that, using the proposed approaches, very compact sets of stimuli satisfying this coverage requirement can efficiently be generated.

Modeling languages such as SysML provide various description means for a precise specification of the desired system. As a system model typically uses multiple diagram types focusing on different aspects, it is crucial to keep them consistent to each other. In this paper, we propose a verification methodology which ensures the consistency between activity diagrams as blueprints for the implementation and their contracts from a block definition diagram. For this purpose, activity diagrams are transformed to OCL constraints that can be checked against pre- and postconditions. The proposed approach is evaluated in a case study based on an industrial specification.

For the design of complex systems, formal modeling languages such as UML or SysML find significant attention. The typical model-driven design flow assumes thereby an initial (abstract) model which is iteratively refined to a more precise description. During this process, new errors and inconsistencies might be introduced. In this paper, we propose an automatic method for verifying the consistency of refinements in UML or SysML. For this purpose, a theoretical foundation is considered from which the corresponding proof obligations are determined. Afterwards, they are encoded as an instance of Satisfiability Modulo Theories (SMT) and solved using proper solving engines. The practical use of the proposed method is demonstrated and compared to a previously proposed approach.

This tutorial paper summarizes selective research results from the field of automated requirement engineering. Automatization is achieved by employing natural language processing techniques. We show algorithms that work directly on the natural language text and algorithms that translate natural language text to formal models. To ensure quality, we further illustrate verification algorithms that can proof correctness of the extracted formal models.

Digital microfluidic biochips enable a higher degree of automation in laboratory procedures in biochemistry and molecular biology and have received significant attention in the recent past. Their design is usually conducted in several stages with routing being a particularly critical challenge. Previously proposed solutions for this design step suffer from two issues: They are mainly of heuristic nature and usually assume that the blockages to be bypassed are present the entire time. In contrast, we present a methodology which exploits the fact that blockages are often only present at certain intervals. At the same time, our approach guarantees exact solutions, i.e. always determines a routing with a minimal number of time steps. Experimental results show that, despite the huge complexity, optimal results can be achieved in reasonable run-time and that the consideration of temporary blockages indeed significantly improves the routing results.

Due to the increasing complexity of today's embedded systems, the design on higher levels of abstraction becomes more and more important. In this context, modeling languages such as UML and its profile MARTE received significant attention in the recent past. They provide formal descriptions that can be exploited to automatically generate initial implementations of a system e.g. In SystemC. While corresponding approaches have been developed in the past, they often focused on functional specifications. Besides that, also non-functional behavior such as clocking constraints needs to be considered in this process. In this work, we propose an approach which addresses this gap. Given a formal specification of clocking constraints specified in the Clock Constraint Specification Language (CCSL, a MARTE accessory), we propose an automatic code generation scheme which enriches an existing SystemC implementation by a module triggering the desired clocks in the system.

No abstract available.

Research in the domain of quantum computation is mainly driven by their promising applications e.g., for factorization or database search. At the same time, physical developments for this emerging technology constantly lead to new constraints to be addressed by logic designers. The limited interaction distance between qubits, the elementary information storage in quantum circuits, is one of the most common restrictions, leading to the fact that, for many quantum architectures, computations can only be performed on adjacent (i.e., nearest neighbor) qubits. Motivated by that, optimization of quantum circuits with respect to this restriction has become an intensely considered research topic. In this paper, we briefly review existing approaches that have been proposed in the past for this purpose. We particularly consider that almost all existing solutions are of heuristic nature, i.e., do not guarantee an optimal solution. In order to address this, exact alternatives are introduced which make use of the deductive power of constraint solvers. By this, we are able to perform a qualitative evaluation of the performance of existing (heuristic) solutions for linear nearest neighbor quantum circuit optimization.

The efficient synthesis of quantum circuits is an active research area. Since many of the known quantum algorithms include a large Boolean component (e.g. the database in the Grover search algorithm), quantum circuits are commonly synthesized in a two-stage approach. First, the desired function is realized as a reversible circuit making use of existing synthesis methods for this domain. Afterwards, each reversible gate is mapped to a functionally equivalent quantum gate cascade. In this paper, we propose an improved mapping of reversible circuits to quantum circuits which exploits a certain structure of many reversible circuits. In fact, it can be observed that reversible circuits are often composed of similar gates which only differ in the position of their target lines. We introduce an extension of reversible gates which allow multiple target lines in a single gate. This enables a significantly cheaper mapping to quantum circuits. Experiments show that considering multiple target lines leads to improvements of up to 85% in the resulting quantum cost.

Modeling languages such as UML or SysML received significant attention over the last years. They allow for an abstract description of systems already in the absence of a precise implementation or a hardware/software partitioning. Additionally considering textual constraints, for example provided by means of OCL, enables to automatically check the specified systems e.g. for consistency of the structure or reachability of certain system states. However, for the majority of verification tasks, not the entire model has to be considered. In this work, we propose an approach that automatically determines reduced system models, i.e. system descriptions that only include model elements which are relevant for the considered verification task. Considering reduced models eases the access by the designer and supports incremental design and verification schemes. But most important, they improve the efficiency of the applied formal verification engine. Experiments demonstrate that already small reductions in the model lead to significant accelerations in the run-time of the verification engine.

The use of modeling languages such as UML or SysML enables to formally specify and verify the behavior of digital systems already in the absence of a specific implementation. However, for each modeling method and verification task usually a separate verification solution has to be applied today. In this paper, a methodology is envisioned that aims at stopping this “inflation” of different verification approaches and instead employs a generic methodology. For this purpose, a given specification as well as the verification shall be transformed into a basic model which itself is specified by means of a generic modeling language. Then, a range of automatic reasoning engines shall uniformly be applied to perform the actual verification. A feasibility study demonstrates the applicability of the envisioned approach.

Cone of influence analysis, i.e. determining the parts of the circuit which are relevant to a considered circuit signal, is an established methodology applied in several design tasks. In abstractions like the Register Transfer Level (RTL) or the gate level, cone of influence analysis is simple. However, the introduction of higher levels of abstractions, particularly the Electronic System Level (ESL), made it significantly harder to reliably extract a cone of influence. In this paper, we propose a methodology that enables cone of influence analysis at the ESL. Instead of a structural analysis, a behavioral scheme is proposed, i.e. stimuli representing different system executions are analyzed. To this end, machine learning techniques are exploited. This enables a very good approximation of the desired cone of influence which is non-invasive, does not rely on the availability of the source code, and performs fast. Case studies confirm the applicability of the proposed approach.

Simulation-based verification is still the state-of-the-art when checking the correctness of complex Systems-on-Chips. In particular, constraint-based simulation is popular, since here dedicated stimuli are generated which trigger certain corner-case behavior. However, to the best of our knowledge, only heuristic methods have been introduced so far. In this paper, we propose an approach that determines a minimal set of stimuli for the desired set of scenarios to be simulated. For this purpose, we are making use of solving techniques from Boolean satisfiability. Experimental evaluations demonstrate that the proposed approach can be applied to generate very compact stimuli sets. Furthermore, the proposed approach can be used to evaluate the quality of results obtained by heuristic methods.

Automatic Test Pattern Generation (ATPG) based on Boolean Satisfiability (SAT) is a robust alternative to classical structural ATPG. Due to the powerful reasoning engines of modern SAT solvers, SAT-based algorithms typically provide a high test coverage because of the ability to reliably classify hard-to-detect faults. However, a drawback of SAT-based ATPG is the test compaction ability. In this paper, we propose an enhanced dynamic test compaction approach which leverages the high implicative power of modern SAT solvers. Fault detection constraints are encoded into the SAT instance and a formal optimization procedure is applied to increase the detection ability of the generated tests. Experiments show that the proposed approach is able to achieve high compaction - for certain benchmarks even smaller test sets than the currently best known results are obtained.

Reversible circuits are an emerging technology where all computations are performed in an invertible manner. Motivated by their promising applications, e.g. in the domain of quantum computation or in the low-power design, the synthesis of such circuits has been intensely studied. However, how to automatically realize reversible circuits with the minimal number of lines for large functions is an open research problem. In this paper, we propose a new synthesis approach which relies on concepts that are complementary to existing ones. While “conventional” function representations have been applied for synthesis so far (such as truth tables, ESOPs, BDDs), we exploit Quantum Multiple-valued Decision Diagrams (QMDDs) for this purpose. An algorithm is presented that performs transformations on this data-structure eventually leading to the desired circuit. Experimental results show the novelty of the proposed approach through enabling automatic synthesis of large reversible functions with the minimal number of circuit lines. Furthermore, the quantum cost of the resulting circuits is reduced by 50% on average compared to an existing state-of-the-art synthesis method.

Quantum computing offers a promising alternative to conventional computation due to the theoretical capacity to solve many important problems with exponentially less complexity. Since every quantum operation is inherently reversible, the desired function is often realized in reversible logic and then mapped to quantum gates. We consider the realization of reversible circuits using a new class of quantum gates. Our method uses a mapping that grows at a very low linear rate with respect to the number of controls. Results show that, particularly for medium to large circuits, our method yields substantially smaller quantum gate counts than do prior approaches.

In model-based design, it is common and helpful to use invariants in order to highlight restrictions or to formulate characteristics of a design. In contrast to pre- and post-conditions, they represent global constraints. That is, they are harder to explicitly consider and, thus, become disadvantageous when the design process approaches the implementation phase. As a consequence, they should be removed from a design when it comes to an implementation. However, so far only naïve tool support aiding the designer in this task is available. In this paper, we present an approach which addresses this problem. A methodology is proposed which iteratively removes invariants from a model and, afterwards, presents the designer with invalid scenarios originally prevented by the just eliminated invariant. Using this, the designer can either manually modify the model or simply take the automatically generated suggestion. This enables to entirely eliminate all invariants without changing the semantics of the model. Case studies illustrate the applicability of the proposed approach.

The application of coding strategies is an established methodology to improve the characteristics of on-chip interconnect architectures. Therefore, design methods are required which realize the corresponding encoders and decoders with as small as possible overhead in terms of power and delay. In the past, conventional design methods have been applied for this purpose.

While being a de-facto standard for the modeling of software systems, the Unified Modeling Language (UML) is also increasingly used in the domain of hardware design and hardware/software co-design. To ensure the correctness of the specified systems, approaches have been presented which automatically verify whether a UML model is consistent, i.e. free of conflicts. However, if the model is inconsistent, these approaches do not provide further information to assist the designer in finding the error. In this work, we present an automatic debugging approach which determines contradiction candidates, i.e. a small subset of the original model explaining the conflict. These contradiction candidates aid the designer in finding the error faster and therefore accelerate the whole design process. The approach employs different satisfiability solvers as well as different debugging strategies. Experimental results demonstrate that, even for large UML models with up to 2500 classes and constraints, the approach determines a very small number of contradiction candidates to be inspected.

Simulation-based verification is still one of the most important methods to validate the correctness of System-on-Chips. Here, explicitly specified stimuli need to be generated which trigger certain scenarios of the design. However, so far stimuli generation is mainly performed independently of the desired coverage. In this work, we propose approaches for coverage-driven stimuli generation. Despite a naive method, we introduce and discuss automatic and interactive methods for an improved stimuli generation. We show that explicitly considering coverage metrics leads to smaller and complete sets of stimuli.

Reversible circuits rely on an entirely different computing paradigm allowing to perform computations not only from the primary inputs to the primary outputs but also vice versa. Recently, first physical realizations based on this paradigm have been introduced in the domain of quantum computation and low-power circuits. This puts key test challenges for the future on the table. While first steps towards testing such circuits have been made (e.g. fault models and appropriate ATPG methods have been introduced), fault diagnosis has hardly been considered so far. In this paper, we consider the application of fault diagnosis methods for reversible circuits. In particular, we propose a new fault diagnosis approach which explicitly exploits the advantageous properties of reversible circuits. Experiments show that even though conventional methods can be applied to reversible circuits, improvements of more than one order of magnitude are achieved if reversibility is explicitly exploited.

The Unified Modeling Language (UML) as a defacto standard for software development finds more and more application in the design of systems which also contain hardware components. Guaranteeing the correctness of a system specified in UML is thereby an important as well as challenging task. In recent years, first approaches for this purpose have been introduced. However, most of them focus only on the static view of a UML model. In this paper, an automatic approach is presented which checks verification tasks for dynamic aspects of a UML model. That is, given a UML model as well as an initial system state, the approach proves whether a sequence of operation calls exists so that a desired behavior is invoked. The underlying verification problem is encoded as an instance of the satisfiability problem and subsequently solved using a SAT Modulo Theory solver. An experimental evaluation confirms the applicability of the proposed approach.

Synthesis of reversible circuits is an active research area motivated by its applications e.g. in quantum computation or low-power design. The number of used circuit lines is thereby a crucial criterion. In this paper, we introduce several methods (including a theoretical upper bound) for the efficient computation or at least approximation of the minimal number of lines needed to realize a given function in reversible logic. While the proposed exact approach requires a significant amount of run-time (exponential in the worst case), the heuristic methods lead to very precise approximations in very short run-time. Using this, it can be shown that current synthesis approaches for large functions are still far away from producing optimal circuits with respect to the number of lines.

Reversible logic became a promising alternative to traditional circuits because of its applications e.g. in low-power design and quantum computation. As a result, design of reversible circuits attracted great attention in the last years. The number of circuit lines is thereby a major criterion since it e.g. affects the still limited resource of qubits. Nevertheless, all approaches introduced so far for synthesis of complex reversible circuits need a significant amount of additional circuit lines — sometimes orders of magnitude more than the primary inputs. In this paper, we propose a post-process optimization method that addresses this problem. The general idea is to merge garbage output lines with appropriate constant input lines. To this end, parts of the circuits are re-synthesized. Experimental results show that by applying the proposed approach, the number of circuit lines can be reduced by 17% on average — in the best case by more than 40%. At the same time, the increase in the number of gates and the quantum costs, respectively, can be kept small.

Nowadays, modeling languages like UML are essential in the design of complex software systems and also start to enter the domain of hardware and hardware/software codesign. Due to shortening time-to-market demands, ¿first time right¿ requirements have thereby to be satisfied. In this paper, we propose an approach that makes use of Boolean satisfiability for verifying UML/OCL models. We describe how the respective components of a verification problem, namely system states of a UML model, OCL constraints, and the actual verification task, can be encoded and afterwards automatically solved using an off-the-shelf SAT solver. Experiments show that our approach can solve verification tasks significantly faster than previous methods while still supporting a large variety of UML/OCL constructs.

In the past, reversible logic has become an intensely studied research topic. This is mainly motivated by its applications in the domain of low-power design and quantum computation. Since reversible logic is subject to certain restrictions (e.g. fanout and feedback are not allowed), traditional synthesis methods are not applicable and specific methods have been developed. In this paper, we focus on synthesis of multiplier circuits in reversible logic. Three methods are presented that address the drawbacks of previous approaches. In particular, the large number of circuit lines in the resulting realizations as well as the poor scalability. Finally, we compare the results to circuits obtained by general purpose synthesis approaches.

This paper considers the optimization of reversible and quantum circuits. Both represent the basis for emerging technologies e.g. in the area of quantum computation and low power design. An approach called window optimization is described that does not consider the circuit as a whole, but smaller sub-circuits of it (so called windows). Two schemes for extracting the windows and three approaches for their optimization are considered. Application scenarios show that applying the proposed optimizations leads to significant reductions of the circuit cost.

Researchers are looking for alternatives to overcome the upcoming limits of conventional hardware technologies. Reversible logic thereby established itself as a promising direction so that several methods for synthesis, verification, and testing of reversible circuits have already been proposed. However, also methods for debugging, i.e., to determine error candidates in case of a failed verification, are required to complete the design flow. Even if first approaches have already been proposed, debugging of reversible circuits still is in the beginning. In this paper, we present an alternative method to automatically debug reversible circuits. We thereby focus on missing control errors -- an established error model in the design of reversible circuits. A new notion of an error candidate is proposed that relies on the observation of a necessary condition for error locations in reversible circuits. Using this notion, a set of error candidates is obtained that differs from the error candidates returned by previous methods. Thus, combining the approaches enhances the overall debugging flow. Experimental results demonstrate that a higher accuracy is obtained in significantly shorter run-time.

Reversible logic is the basis for several emerging technologies such as quantum computing, optical computing, or DNA computing and has further applications in domains like low-power design and nanotechnologies. However, current methods for the synthesis of reversible logic are limited, i.e. they are applicable to relatively small functions only. In this paper, we propose a synthesis approach, that can cope with Boolean functions containing more than a hundred of variables. We present a technique to derive reversible circuits for a function given by a Binary Decision Diagram (BDD). The circuit is obtained using an algorithm with linear worst case behavior regarding run-time and space requirements. Furthermore, the size of the resulting circuit is bounded by the BDD size. This allows to transfer theoretical results known from BDDs to reversible circuits. Experiments show better results (with respect to the circuit cost) and a significantly better scalability in comparison to previous synthesis approaches.

Intensive research is performed to find post-CMOS technologies. A very promising direction based on reversible logic are quantum computers. While in the domain of reversible logic synthesis, testing, and verification have been investigated, debugging of reversible circuits has not yet been considered. The goal of debugging is to determine gates of an erroneous circuit that explain the observed incorrect behavior. In this paper we propose the first approach for automatic debugging of reversible Toffoli networks. Our method uses a formulation for the debugging problem based on Boolean satisfiability. We show the differences to classical (irreversible) debugging and present theoretical results. These are used to speed-up the debugging approach as well as to improve the resulting quality. Our method is able to find and to correct single errors automatically.

Many reversible circuit synthesis procedures have been proposed. A common feature of most methods is that the initial specification must be a completely-specified reversible function. However, often the desired functionality is a, possibly incompletely-specified, irreversible function. In this paper, we consider how to fully automate the process of synthesizing a reversible function given an irreversible specification with particular emphasis on how to embed an irreversible function into a reversible specification. Systematic procedures are presented and results for benchmark problems show the methods produce very good results compared to earlier methods.

In the context of formal verification Bounded Model Checking (BMC) has shown to be very powerful for large industrial designs. BMC is used to check whether a circuit satisfies a temporal property or not. Typically, such a property is formulated as an implication. In the antecedent of the property the verification engineer specifies the assumptions about the design environment and joins the respective expressions by logical AND. However, the overall conjunction may have no solution, i.e. the antecedent is contradictory. Since in this case a property trivially holds this situation has to be avoided. Furthermore, the root cause of a contradictory antecedent has to be identified which is a manual and very time-consuming process. In this paper we propose a fully automatic approach for presenting all reasons of a contradictory antecedent to the verification engineer, i.e. the approach pinpoints to the sub-expressions in the antecedent that form a contradiction. Hence, our approach reduces the debugging time of a contradictory antecedent significantly.

Synthesis of reversible logic has become a very important research area in recent years. Applications can be found in the domain of low-power design, optical computing, and quantum computing. In the past, several approaches have been introduced that synthesize reversible networks with respect to a given function. Most of these methods only approximate a minimal network representation. In this paper, exact algorithms for the synthesis of multiple-control Toffoli networks are presented, i.e., algorithms that guarantee to find a network with the minimal number of gates. Our iterative algorithms formulate the synthesis problem as a sequence of decision problems. The decision problems are encoded as Boolean satisfiability (SAT) or SAT modulo theory (SMT) instances, respectively. As soon as one of these instances becomes satisfiable, a Toffoli network representation for the given function has been found. We show that choosing the encoding for synthesis is crucial for the resulting runtimes. Furthermore, we discuss the principal limits of the SAT and SMT approaches. To overcome these limits, we propose a method using problem-specific knowledge during synthesis. In addition, better embeddings to make irreversible functions reversible are considered. For the resulting synthesis problems, an improvement is presented that reduces the overall runtime by automatically setting the constant inputs to their optimal values. Experimental results on a large set of benchmarks demonstrate the differences between three exact synthesis algorithms. In addition, a comparison with the best-known heuristic results is provided. In summary, the results show that, for some benchmarks, the heuristic approaches have already found the minimal network, while for other benchmarks, significantly smaller networks exist.

In the last years synthesis of reversible logic functions has emerged as an important research area. Other fields such as low-power design, optical computing and quantum computing benefit directly from achieved improvements. Recently, several approaches for exact synthesis of Toffoli networks have been proposed. They all use Boolean satisfiability to solve the underlying synthesis problem. In this paper a new exact synthesis approach based on Quantified Boolean Formula (QBF) satisfiability - a generalization of Boolean satisfiability - is presented. Besides the application of QBF solvers, we propose Binary Decision Diagrams to solve the quantified problem formulation. This allows to easily support different gate libraries during synthesis. In addition, all minimal networks are found in a single step and the best one with respect to quantum costs can be chosen. Experimental results confirm that the new technique is faster than the best previously known approach and leads to cheaper realizations in terms of quantum costs.

Integrating design and verification becomes more and more important due to the increasing complexity of today's circuits and systems. SystemVerilog is a description language that embeds verification goals with the help of SystemVerilog assertions (SVAs). Often SVAs are used in simulation-based verification. But in the past first applications in formal verification have been considered, too. In this paper we present an approach to prove SVAs by induction based bounded model checking (BMC). Since checking SVAs is computationally very complex, we define a subset which is sufficient for many practical purposes. For each restriction a rationale is given.The creation of the BMC instance for this subset is explained in detail. Case studies show the application of our approach.

Constraint-based random simulation is state-of-the-art in verification of multi-million gate industrial designs. This method is based on stimulus generation by constraint solving. The resulting stimuli will particularly cover corner case test scenarios which are usually hard to identify manually by the verification engineer. Consequently, constraintbased random simulation will catch corner case bugs that would remain undetected otherwise. Therefore, the quality of design verification is increased significantly. However, in the process of constraint specification for a specific test scenario, the verification engineer is faced with the problem of over-constraining, i.e. the overall constraint specified for a test scenario has no solution. In this case the root cause of the contradiction has to be identified and resolved. Given the complexity of constraints used to describe test scenarios, this can be a very time-consuming process. In this paper we propose a fully automated contradiction analysis method. Our method determines all “non relevant” constraints and computes all reasons that lead to the over-constraining. Thus, we pinpoint the verification engineer to exactly the sets of constraints that have to be considered to resolve the over-constraining. Experiments have been conducted in a real-life SystemC-based verification environment at AMD Dresden Design Center. They demonstrate a significant reduction of the constraint contradiction debug time.

The research in the field of reversible logic is motivated by its application in low-power design, optical computing and quantum computing. Hence synthesis of reversible logic has become a very important research area in the last years. In this paper exact algorithms for the synthesis of generalized Toffoli networks are considered. We present an improvement of an existing synthesis approach that is based on Boolean Satisfiability. Furthermore, the principle limits of the original and the improved approach are shown. Then, we propose a new method using problem specific knowledge during the synthesis process to overcome these limits. Experimental results demonstrate improvements of the overall synthesis time up to four orders of magnitude.

Solvers for Boolean Satisfiabilily (SAT) are state-of-the-art to solve verification problems. But when arithmetic operations are considered, the verification performance degrades with increasing data-path width. Therefore, several approaches that handle a higher level of abstraction have been studied in the past. But the resulting solvers are still not robust enough to handle problems that mix word level structures with bit level descriptions. In this paper, we present the satisfiability solver SWORD — a SAT like solver that facilitates word level information. SWORD represents the problem in terms of modules that define operations over bit vectors. Thus, word level information and structural knowledge become available in the search process. The experimental results show that on our benchmarks SWORD is more robust than Boolean SAT, K⋆BMDs or SMT.