We extend three related results from the analysis of influences of Boolean functions to the quantum setting, namely the KKL Theorem, Friedgut's Junta Theorem and Talagrand's variance inequality for geometric influences. Our results are derived by a joint use of recently studied hypercontractivity and gradient estimates. These generic tools also allow us to derive generalizations of these results in a general von Neumann algebraic setting beyond the case of the quantum hypercube, including examples in infinite dimensions relevant to quantum information theory such as continuous variables quantum systems. Finally, we comment on the implications of our results as regards to noncommutative extensions of isoperimetric type inequalities and the learnability of quantum observables.
The Kibble-Zurek mechanism (KZM) captures the essential physics of nonequilibrium quantum phase transitions with symmetry breaking. KZM predicts a universal scaling power law for the defect density which is fully determined by the system's critical exponents at equilibrium and the quenching rate. We experimentally tested the KZM for the simplest quantum case, a single qubit under the Landau-Zener evolution, on an open access IBM quantum computer (IBM-Q). We find that for this simple one-qubit model, experimental data validates the central KZM assumption of the adiabatic-impulse approximation for a well isolated qubit. Furthermore, we report on extensive IBM-Q experiments on individual qubits embedded in different circuit environments and topologies, separately elucidating the role of crosstalk between qubits and the increasing decoherence effects associated with the quantum circuit depth on the KZM predictions. Our results strongly suggest that increasing circuit depth acts as a decoherence source, producing a rapid deviation of experimental data from theoretical unitary predictions.
The ability to direct a Probabilistic Boolean Network (PBN) to a desired state is important to applications such as targeted therapeutics in cancer biology. Reinforcement Learning (RL) has been proposed as a framework that solves a discrete-time optimal control problem cast as a Markov Decision Process. We focus on an integrative framework powered by a model-free deep RL method that can address different flavours of the control problem (e.g., with or without control inputs; attractor state or a subset of the state space as the target domain). The method is agnostic to the distribution of probabilities for the next state, hence it does not use the probability transition matrix. The time complexity is linear on the time steps, or interactions between the agent (deep RL) and the environment (PBN), during training. Indeed, we explore the scalability of the deep RL approach to (set) stabilization of large-scale PBNs and demonstrate successful control on large networks, including a metastatic melanoma PBN with 200 nodes.
We develop a general method to study the Fisher information distance in central limit theorem for nonlinear statistics. We first construct completely new representations for the score function. We then use these representations to derive quantitative estimates for the Fisher information distance. To illustrate the applicability of our approach, explicit rates of Fisher information convergence for quadratic forms and the functions of sample means are provided. For the sums of independent random variables, we obtain the Fisher information bounds without requiring the finiteness of Poincar\'e constant. Our method can also be used to bound the Fisher information distance in non-central limit theorems.
Quantum machine learning promises to efficiently solve important problems. There are two persistent challenges in classical machine learning: the lack of labeled data, and the limit of computational power. We propose a novel framework that resolves both issues: quantum semi-supervised learning. Moreover, we provide a protocol in systematically designing quantum machine learning algorithms with quantum supremacy, which can be extended beyond quantum semi-supervised learning. In the meantime, we show that naive quantum matrix product estimation algorithm outperforms the best known classical matrix multiplication algorithm. We showcase two concrete quantum semi-supervised learning algorithms: a quantum self-training algorithm named the propagating nearest-neighbor classifier, and the quantum semi-supervised K-means clustering algorithm. By doing time complexity analysis, we conclude that they indeed possess quantum supremacy.
Four new centrality measures for directed networks based on unitary, continuous-time quantum walks (CTQW) in $n$ dimensions -- where $n$ is the number of nodes -- are presented, tested and discussed. The main idea behind these methods consists in re-casting the classical HITS and PageRank algorithms as eigenvector problems for symmetric matrices, and using these symmetric matrices as Hamiltonians for CTQWs, in order to obtain a unitary evolution operator. The choice of the initial state is also crucial. Two options were tested: a vector with uniform occupation and a vector weighted w.r.t.~in- or out-degrees (for authority and hub centrality, respectively). Two methods are based on a HITS-derived Hamiltonian, and two use a PageRank-derived Hamiltonian. Centrality scores for the nodes are defined as the average occupation values. All the methods have been tested on a set of small, simple graphs in order to spot possible evident drawbacks, and then on a larger number of artificially generated larger-sized graphs, in order to draw a comparison with classical HITS and PageRank. Numerical results show that, despite some pathologies found in three of the methods when analyzing small graphs, all the methods are effective in finding the first and top ten nodes in larger graphs. We comment on the results and offer some insight into the good accordance between classical and quantum approaches.
The Galois inner product is a generalization of the Euclidean inner product and Hermitian inner product. The Galois hull of a linear code is the intersection of itself and its Galois dual code, which has aroused the interest of researchers in these years. In this paper, we study Galois hulls of linear codes. Firstly, the symmetry of the dimensions of Galois hulls is found. Some new necessary and sufficient conditions for linear codes being Galois self-orthogonal codes, Galois self-dual codes and Galois linear complementary dual codes are characterized. Then, based on these properties, we develop the previous theory and propose explicit methods to construct Galois self-orthogonal codes of lengths $n+2i$ ($i\geq 0$) and $n+2i+1$ ($i\geq 1$) from Galois self-orthogonal codes of length $n$. As applications, linear codes of lengths $n+2i$ and $n+2i+1$ with Galois hulls of arbitrary dimensions are derived immediately. After this, two new classes of Hermitian self-orthogonal MDS codes are also constructed. Finally, applying all the results to the constructions of entanglement-assisted quantum error-correcting codes (EAQECCs), many new EAQECCs and MDS EAQECCs with rates greater than or equal to $\frac{1}{2}$ and positive net rates can be obtained.
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. The implementation is open source and publicly available as part of the equivalence checking tool QCEC (//github.com/cda-tum/qcec) which is part of the Munich Quantum Toolkit (MQT).
We study the rank of sub-matrices arising out of kernel functions, $F(\pmb{x},\pmb{y}): \mathbb{R}^d \times \mathbb{R}^d \mapsto \mathbb{R}$, where $\pmb{x},\pmb{y} \in \mathbb{R}^d$ with $F(\pmb{x},\pmb{y})$ is smooth everywhere except along the line $\pmb{x}=\pmb{y}$. Such kernel functions are frequently encountered in a wide range of applications such as $N$ body problems, Green's functions, integral equations, geostatistics, kriging, Gaussian processes, etc. One of the challenges in dealing with these kernel functions is that the corresponding matrix associated with these kernels is large and dense and thereby, the computational cost of matrix operations is high. In this article, we prove new theorems bounding the numerical rank of sub-matrices arising out of these kernel functions. Under reasonably mild assumptions, we prove that the rank of certain sub-matrices is rank-deficient in finite precision. This rank depends on the dimension of the ambient space and also on the type of interaction between the hyper-cubes containing the corresponding set of particles. This rank structure can be leveraged to reduce the computational cost of certain matrix operations such as matrix-vector products, solving linear systems, etc. We also present numerical results on the growth of rank of certain sub-matrices in $1$D, $2$D, $3$D and $4$D, which, not surprisingly, agrees with the theoretical results.
In this paper, we present Q# implementations for arbitrary single-variabled fixed-point arithmetic operations for a gate-based quantum computer based on lookup tables (LUTs). In general, this is an inefficent way of implementing a function since the number of inputs can be large or even infinite. However, if the input domain can be bounded and there can be some error tolerance in the output (both of which are often the case in practical use-cases), the quantum LUT implementation of certain quantum arithmetic functions can be more efficient than their corresponding reversible arithmetic implementations. We discuss the implementation of the LUT using Q\# and its approximation errors. We then show examples of how to use the LUT to implement quantum arithmetic functions and compare the resources required for the implementation with the current state-of-the-art bespoke implementations of some commonly used arithmetic functions. The implementation of the LUT is designed for use by practitioners to use when implementing end-to-end quantum algorithms. In addition, given its well-defined approximation errors, the LUT implementation makes for a clear benchmark for evaluating the efficiency of bespoke quantum arithmetic circuits .
Solving large systems of equations is a challenge for modeling natural phenomena, such as simulating subsurface flow. To avoid systems that are intractable on current computers, it is often necessary to neglect information at small scales, an approach known as coarse-graining. For many practical applications, such as flow in porous, homogenous materials, coarse-graining offers a sufficiently-accurate approximation of the solution. Unfortunately, fractured systems cannot be accurately coarse-grained, as critical network topology exists at the smallest scales, including topology that can push the network across a percolation threshold. Therefore, new techniques are necessary to accurately model important fracture systems. Quantum algorithms for solving linear systems offer a theoretically-exponential improvement over their classical counterparts, and in this work we introduce two quantum algorithms for fractured flow. The first algorithm, designed for future quantum computers which operate without error, has enormous potential, but we demonstrate that current hardware is too noisy for adequate performance. The second algorithm, designed to be noise resilient, already performs well for problems of small to medium size (order 10 to 1000 nodes), which we demonstrate experimentally and explain theoretically. We expect further improvements by leveraging quantum error mitigation and preconditioning.