Unitary decomposition is a widely used method to map quantum algorithms to an arbitrary set of quantum gates. Efficient implementation of this decomposition allows for the translation of bigger unitary gates into elementary quantum operations, which is key to executing these algorithms on existing quantum computers. The decomposition can be used as an aggressive optimization method for the whole circuit, as well as to test part of an algorithm on a quantum accelerator. For the selection and implementation of the decomposition algorithm, perfect qubits are assumed. We base our decomposition technique on Quantum Shannon Decomposition, which generates $O\left(\frac{3}{4}{4}^n\right)$ controlled-not gates for an n-qubit input gate. In addition, we implement optimizations to take advantage of the potential underlying structure in the input or intermediate matrices, as well as to minimize the execution time of the decomposition. Comparing our implementation to Qubiter and the UniversalQCompiler (UQC), we show that our implementation generates circuits that are much shorter than those of Qubiter and not much longer than the UQC. At the same time, it is also up to 10 times as fast as Qubiter and about 500 times as fast as the UQC.

Inferring algorithmic structure in data is essential for discovering causal generative models. In this research, we present a quantum computing framework using the circuit model, for estimating algorithmic information metrics. The canonical computation model of the Turing machine is restricted in time and space resources, to make the target metrics computable under realistic assumptions. The universal prior distribution for the automata is obtained as a quantum superposition, which is further conditioned to estimate the metrics. Specific cases are explored where the quantum implementation offers polynomial advantage, in contrast to the exhaustive enumeration needed in the corresponding classical case. The unstructured output data and the computational irreducibility of Turing machines make this algorithm impossible to approximate using heuristics. Thus, exploring the space of program-output relations is one of the most promising problems for demonstrating quantum supremacy using Grover search that cannot be dequantized. Experimental use cases for quantum acceleration are developed for self-replicating programs and algorithmic complexity of short strings. With quantum computing hardware rapidly attaining technological maturity, we discuss how this framework will have significant advantage for various genomics applications in meta-biology, phylogenetic tree analysis, protein-protein interaction mapping and synthetic biology. This is the first time experimental algorithmic information theory is implemented using quantum computation. Our implementation on the Qiskit quantum programming platform is copy-left and is publicly available on GitHub.

With small-scale quantum processors transitioning from experimental physics labs to industrial products, these processors in a few years are expected to scale up and be more robust for efficiently computing important algorithms in various fields. In this paper, we propose a quantum algorithm to address the challenging field of data processing for genome sequence reconstruction. This research describes an architecture-aware implementation of a quantum algorithm for sub-sequence alignment. A new algorithm named QiBAM (quantum indexed bidirectional associative memory) is proposed, which uses approximate pattern-matching based on Hamming distances. QiBAM extends the Grover’s search algorithm in two ways, allowing: (1) approximate matches needed for read errors in genomics, and (2) a distributed search for multiple solutions over the quantum encoding of DNA sequences. This approach gives a quadratic speedup over the classical algorithm. A full implementation of the algorithm is provided and verified using the OpenQL compiler and QX Simulator framework. Our implementation represents a first exploration towards a full-stack quantum accelerated genome sequencing pipeline design.

Computer simulation is an indispensable tool for studying complex biological systems. In particular, agent-based modeling is an attractive method to describe biophysical dynamics. However, two barriers limit faster progress. First, simulators do not always take full advantage of parallel and heterogeneous hardware. Second, many agent-based simulators are written with a specific research problem in mind and lack a flexible software design. Consequently, researchers have to spend an unnecessarily long time implementing their simulation and have to compromise either on model resolution or system size. We present a novel simulation platform called BioDynaMo that alleviates both of these problems researchers face in computer simulation of complex biological systems. BioDynaMo features a general-purpose and high-performance simulation engine. The engine simulates cellular elements, their interactions within a 3D physical environment, and their cell-internal genetic dynamics. Cell-internal dynamics can be described in C++ code or using system biology markup language (SBML). We demonstrate BioDynaMo’s wide range of application with three example use cases: soma clustering, neural development, and tumor spheroid growth. We validate our results with experimental data, and evaluate the performance of the simulation engine. We compare BioDynaMo’s performance with a state-of-the-art baseline, and analyze its scalability. We observe a speedup of 20–124× over the state-of-the-art baseline using one CPU core and a parallel speedup between 67× and 76× using 72 physical CPU cores with hyperthreading enabled. Combining these two results, we conclude that, on our test system, BioDynaMo is at least three orders of magnitude faster than the state-of-the-art serial baseline. These improvements make it feasible to simulate neural development with 1.24 billion agents on a single server with 1TB memory, and 12 million agents on a laptop with 16GB memory. BioDynaMo is an open-source project under the Apache 2.0 license and is available at www.biodynamo.org. Author summary Computer simulations of biological systems are crucial to gain insights into complex processes of living organisms. However, the development of increasingly large and complex simulations is a difficult task, partly because a strong background in biology as well as computer science is required. In this paper, we introduce BioDynaMo, an agent-based simulation platform with which life scientists can create simulations that are three orders of magnitude faster than the state-of-the-art baseline. By taking advantage of the latest developments in computing hardware, we build a platform that is highly optimized. This enables the simulation of 1.24 billion agents on a single server and 12 million agents on a laptop. BioDynaMo places a lot of focus on hiding computational complexity and providing an easy-to-use interface, such that the life scientist can concentrate on biological aspects, rather than computational. BioDynaMo helps scientists to translate an idea quickly into a simulation by providing common building blocks, and a modular and extensible software design. We analyze the performance of the platform and demonstrate the capabilities with three example use cases: soma clustering, neural development, and tumor spheroid growth. The results support the view that BioDynaMo will help open up new research opportunities for large-scale biological simulations.

Many researchers have proposed replacing the aggregation server in federated learning with a blockchain system to improve privacy, robustness, and scalability. In this approach, clients would upload their updated models to the blockchain ledger and use a smart contract to perform model averaging. However, the significant delay and limited computational capabilities of blockchain systems make it inefficient to support machine learning applications on the blockchain. In this article, we propose a new public blockchain architecture called DFL, which is specially optimized for distributed federated machine learning. Our architecture inherits the merits of traditional blockchain systems while achieving low latency and low resource consumption by waiving global consensus. To evaluate the performance and robustness of our architecture, we implemented a prototype and tested it on a physical four-node network, and also developed a simulator to simulate larger networks and more complex situations. Our experiments show that the DFL architecture can reach over 90% accuracy for non-I.I.D. datasets, even in the presence of model poisoning attacks, while ensuring that the blockchain part consumes less than 5% of hardware resources.

Pairwise sequence alignment is widely used in many biological tools and applications. Existing GPU accelerated implementations mainly focus on calculating optimal alignment score and omit identifying the optimal alignment itself. In GATK HaplotypeCaller (HC), the semi-global pairwise sequence alignment with traceback has so far been difficult to accelerate effectively on GPUs. We first analyze the characteristics of the semi-global alignment with traceback in GATK HC and then propose a new algorithm that allows for retrieving the optimal alignment efficiently on GPUs. For the first stage, we choose intra-task parallelization model to calculate the position of the optimal alignment score and the backtracking matrix. Moreover, in the first stage, our GPU implementation also records the length of consecutive matches/mismatches in addition to lengths of consecutive insertions and deletions as in the CPU-based implementation. This helps efficiently retrieve the backtracking matrix to obtain the optimal alignment in the second stage. Experimental results show that our alignment kernel with traceback is up to 80x and 14.14x faster than its CPU counterpart with synthetic datasets and real datasets, respectively. When integrated into GATK HC (alongside a GPU accelerated pair-HMMs forward kernel), the overall acceleration is 2.3x faster than the baseline GATK HC implementation, and 1.34x faster than the GATK HC implementation with the integrated GPU-based pair-HMMs forward algorithm. Although the methods proposed in this paper is to improve the performance of GATK HC, they can also be used in other pairwise alignments and applications.