Search

Variational quantum computing offers a flexible computational paradigm with applications in diverse areas. However, a key obstacle to realizing their potential is the Barren Plateau (BP) phenomenon. When a model exhibits a BP, its parameter optimization landscape becomes exponentially flat and featureless as the problem size increases. Importantly, all the moving pieces of an algorithm -- choices of ansatz, initial state, observable, loss function and hardware noise -- can lead to BPs when ill-suited. Due to the significant impact of BPs on trainability, researchers have dedicated considerable effort to develop theoretical and heuristic methods to understand and mitigate their effects. As a result, the study of BPs has become a thriving area of research, influencing and cross-fertilizing other fields such as quantum optimal control, tensor networks, and learning theory. This article provides a comprehensive review of the current understanding of the BP phenomenon., Comment: 21 pages, 10 boxes

We present Noise-Directed Adaptive Remapping (NDAR), a heuristic algorithm for approximately solving binary optimization problems by leveraging certain types of noise. We consider access to a noisy quantum processor with dynamics that features a global attractor state. In a standard setting, such noise can be detrimental to the quantum optimization performance. Our algorithm bootstraps the noise attractor state by iteratively gauge-transforming the cost-function Hamiltonian in a way that transforms the noise attractor into higher-quality solutions. The transformation effectively changes the attractor into a higher-quality solution of the Hamiltonian based on the results of the previous step. The end result is that noise aids variational optimization, as opposed to hindering it. We present an improved Quantum Approximate Optimization Algorithm (QAOA) runs in experiments on Rigetti's quantum device. We report approximation ratios $0.9$-$0.96$ for random, fully connected graphs on $n=82$ qubits, using only depth $p=1$ QAOA with NDAR. This compares to $0.34$-$0.51$ for standard $p=1$ QAOA with the same number of function calls., Comment: 7+7 pages; 3+2 figures; comments and suggestions are welcome!; v2: updated references, fixed typos, improved narration

The construction of quantum circuits to simulate Hamiltonian evolution is central to many quantum algorithms. State-of-the-art circuits are based on oracles whose implementation is often omitted, and the complexity of the algorithm is estimated by counting oracle queries. However, in practical applications, an oracle implementation contributes a large constant factor to the overall complexity of the algorithm. The key finding of this work is the efficient procedure for representation of a tridiagonal matrix in the Pauli basis, which allows one to construct a Hamiltonian evolution circuit without the use of oracles. The procedure represents a general tridiagonal matrix $2^n \times 2^n$ by systematically determining all Pauli strings present in the decomposition, dividing them into commuting subsets. The efficiency is in the number of commuting subsets $O(n)$. The method is demonstrated using the one-dimensional wave equation, verifying numerically that the gate complexity as function of the number of qubits is lower than the oracle based approach for $n < 15$ and requires half the number of qubits. This method is applicable to other Hamiltonians based on the tridiagonal matrices.

Variational quantum algorithms have emerged as a cornerstone of contemporary quantum algorithms research. Practical implementations of these algorithms, despite offering certain levels of robustness against systematic errors, show a decline in performance due to the presence of stochastic errors and limited coherence time. In this work, we develop a recipe for mitigating quantum gate errors for variational algorithms using zero-noise extrapolation. We introduce an experimentally amenable method to control error strength in the circuit. We utilize the fact that gate errors in a physical quantum device are distributed inhomogeneously over different qubits and qubit pairs. As a result, one can achieve different circuit error sums based on the manner in which abstract qubits in the circuit are mapped to a physical device. We find that the estimated energy in the variational approach is approximately linear with respect to the circuit error sum (CES). Consequently, a linear fit through the energy-CES data, when extrapolated to zero CES, can approximate the energy estimated by a noiseless variational algorithm. We demonstrate this numerically and investigate the applicability range of the technique.

This work is devoted to the study Translation-Invariant (TI) Matrix Product State (MPS) representations of quantum states with periodic boundary conditions (PBC). We pursue two directions: we introduce new methods for constructing TI MPS representations of a certain class of TI states and study their optimality in terms of their bond dimension. We pay particular attention to the $n$-party $W$-state and construct a TI MPS representation of bond dimension $\left \lfloor \dfrac{n}{2} \right \rfloor +1$ for it. We further study properties of this class and show that we can can always achieve a bond dimension of $n$ for TI MPS representation of states in this class. In the framework of studying optimality of TI MPS representations with PBC, we study the optimal bond dimension $d(\psi)$ for a given state $\psi$. In particular we introduce a deterministic algorithm for the search of $d(\psi)$ for an arbitary state. Using numerical methods, we verify the optimality of our previous construction for the $n$-party $W$-state for small $n$.

Variational quantum algorithms are tailored to perform within the constraints of current quantum devices, yet they are limited by performance-degrading errors. In this study, we consider a noise model that reflects realistic gate errors inherent to variational quantum algorithms. We investigate the decoherence of a variationally prepared quantum state due to this noise model, which causes a deviation from the energy estimation in the variational approach. By performing a perturbative analysis of optimized circuits, we determine the noise threshold at which the criteria set by the stability lemma is met. We assess our findings against the variational quantum eigensolver and quantum approximate optimization algorithm for various problems with up to 14 qubits. Moreover, we show that certain gate errors have a significantly smaller impact on the coherence of the state, allowing us to reduce the execution time without compromising performance., Comment: 11 pages, 8 figures, published version

A symmetric pseudo-Boolean function is a map from Boolean tuples to real numbers which is invariant under input variable interchange. We prove that any such function can be equivalently expressed as a power series or factorized. The kernel of a pseudo-Boolean function is the set of all inputs that cause the function to vanish identically. Any $n$-variable symmetric pseudo-Boolean function $f(x_1, x_2, \dots, x_n)$ has a kernel corresponding to at least one $n$-affine hyperplane, each hyperplane is given by a constraint $\sum_{l=1}^n x_l = \lambda$ for $\lambda\in \mathbb{C}$ constant. We use these results to analyze symmetric pseudo-Boolean functions appearing in the literature of spin glass energy functions (Ising models), quantum information and tensor networks., Comment: 10 pages

We argue that quantum computing underwent an inflection point circa 2017. Long promised funding materialised which prompted public and private investments around the world. Techniques from machine learning suddenly influenced central aspects of the field. On one hand, machine learning was used to emulate quantum systems. On the other hand, quantum algorithms became viewed as a new type of machine learning model (creating the new model of {\it variational} quantum computation). Here we sketch some milestones which have lead to this inflection point. We argue that the next inflection point would occur around when practical problems will be first solved by quantum computers. We anticipate that by 2050 this would have become commonplace, were the world would still be adjusting to the possibilities brought by quantum computers., Comment: to appear, Book Chapter in EPS Grand Challenges Physics for Society in the Horizon 2050, Institute of Physics Publishing, London, United Kingdom

A tensor network is a type of decomposition used to express and approximate large arrays of data. A given data-set, quantum state or higher dimensional multi-linear map is factored and approximated by a composition of smaller multi-linear maps. This is reminiscent to how a Boolean function might be decomposed into a gate array: this represents a special case of tensor decomposition, in which the tensor entries are replaced by 0, 1 and the factorisation becomes exact. The collection of associated techniques are called, tensor network methods: the subject developed independently in several distinct fields of study, which have more recently become interrelated through the language of tensor networks. The tantamount questions in the field relate to expressability of tensor networks and the reduction of computational overheads. A merger of tensor networks with machine learning is natural. On the one hand, machine learning can aid in determining a factorization of a tensor network approximating a data set. On the other hand, a given tensor network structure can be viewed as a machine learning model. Herein the tensor network parameters are adjusted to learn or classify a data-set. In this survey we recover the basics of tensor networks and explain the ongoing effort to develop the theory of tensor networks in machine learning., Comment: 7 pages

Variational quantum algorithms involve training parameterized quantum circuits using a classical co-processor. An important variational algorithm, designed for combinatorial optimization, is the quantum approximate optimization algorithm. Realization of this algorithm on any modern quantum processor requires either embedding a problem instance into a Hamiltonian or emulating the corresponding propagator by a gate sequence. For a vast range of problem instances this is impossible due to current circuit depth and hardware limitations. Hence we adapt the variational approach -- using ion native Hamiltonians -- to create ansatze families that can prepare the ground states of more general problem Hamiltonians. We analytically determine symmetry protected classes that make certain problem instances inaccessible unless this symmetry is broken. We exhaustively search over six qubits and consider upto twenty circuit layers, demonstrating that symmetry can be broken to solve all problem instances of the Sherrington-Kirkpatrick Hamiltonian. Going further, we numerically demonstrate training convergence and level-wise improvement for up to twenty qubits. Specifically these findings widen the class problem instances which might be solved by ion based quantum processors. Generally these results serve as a test-bed for quantum approximate optimization approaches based on system native Hamiltonians and symmetry protection., Comment: 9 pages; 5 figures; REVTeX

In the problem of quantum channel discrimination, one distinguishes between a given number of quantum channels, which is done by sending an input state through a channel and measuring the output state. This work studies applications of variational quantum circuits and machine learning techniques for discriminating such channels. In particular, we explore (i) the practical implementation of embedding this task into the framework of variational quantum computing, (ii) training a quantum classifier based on variational quantum circuits, and (iii) applying the quantum kernel estimation technique. For testing these three channel discrimination approaches, we considered a pair of entanglement-breaking channels and the depolarizing channel with two different depolarization factors. For the approach (i), we address solving the quantum channel discrimination problem using widely discussed parallel and sequential strategies. We show the advantage of the latter in terms of better convergence with less quantum resources. Quantum channel discrimination with a variational quantum classifier (ii) allows one to operate even with random and mixed input states and simple variational circuits. The kernel-based classification approach (iii) is also found effective as it allows one to discriminate depolarizing channels associated not with just fixed values of the depolarization factor, but with ranges of it. Additionally, we discovered that a simple modification of one of the commonly used kernels significantly increases the efficiency of this approach. Finally, our numerical findings reveal that the performance of variational methods of channel discrimination depends on the trace of the product of the output states. These findings demonstrate that quantum machine learning can be used to discriminate channels, such as those representing physical noise processes., Comment: 18 pages; 14 figures; RevTeX

Quantum computing promises to enhance machine learning and artificial intelligence. Different quantum algorithms have been proposed to improve a wide spectrum of machine learning tasks. Yet, recent theoretical works show that, similar to traditional classifiers based on deep classical neural networks, quantum classifiers would suffer from the vulnerability problem: adding tiny carefully-crafted perturbations to the legitimate original data samples would facilitate incorrect predictions at a notably high confidence level. This will pose serious problems for future quantum machine learning applications in safety and security-critical scenarios. Here, we report the first experimental demonstration of quantum adversarial learning with programmable superconducting qubits. We train quantum classifiers, which are built upon variational quantum circuits consisting of ten transmon qubits featuring average lifetimes of 150 $\mu$s, and average fidelities of simultaneous single- and two-qubit gates above 99.94% and 99.4% respectively, with both real-life images (e.g., medical magnetic resonance imaging scans) and quantum data. We demonstrate that these well-trained classifiers (with testing accuracy up to 99%) can be practically deceived by small adversarial perturbations, whereas an adversarial training process would significantly enhance their robustness to such perturbations. Our results reveal experimentally a crucial vulnerability aspect of quantum learning systems under adversarial scenarios and demonstrate an effective defense strategy against adversarial attacks, which provide a valuable guide for quantum artificial intelligence applications with both near-term and future quantum devices., Comment: 26 pages, 17 figures, 8 algorithms

Implementing variational quantum algorithms with noisy intermediate-scale quantum machines of up to a hundred qubits is nowadays considered as one of the most promising routes towards achieving a quantum practical advantage. In multiqubit circuits, running advanced quantum algorithms is hampered by the noise inherent to quantum gates which distances us from the idea of universal quantum computing. Based on a one-dimensional quantum spin chain with competing symmetric and asymmetric pairwise exchange interactions, herein we discuss the capabilities of quantum algorithms with special attention paid to a hardware-efficient variational eigensolver. A delicate interplay between magnetic interactions allows one to stabilize a chiral state that destroys the homogeneity of magnetic ordering, thus making this solution highly entangled. Quantifying entanglement in terms of quantum concurrence, we argue that, while being capable of correctly reproducing a uniform magnetic configuration, the hardware-efficient ansatz meets difficulties in providing a detailed description to a noncollinear magnetic structure. The latter naturally limits the application range of variational quantum computing to solve quantum simulation tasks., Comment: 6 pages, 4 figures, Supplemental Material

Variational quantum algorithms rely on gradient based optimization to iteratively minimize a cost function evaluated by measuring output(s) of a quantum processor. A barren plateau is the phenomenon of exponentially vanishing gradients in sufficiently expressive parametrized quantum circuits. It has been established that the onset of a barren plateau regime depends on the cost function, although the particular behavior has been demonstrated only for certain classes of cost functions. Here we derive a lower bound on the variance of the gradient, which depends mainly on the width of the circuit causal cone of each term in the Pauli decomposition of the cost function. Our result further clarifies the conditions under which barren plateaus can occur., Comment: 26 pages, RevTeX

Variational quantum algorithms dominate gate-based applications of modern quantum processors. The so called, {\it layer-wise trainability conjecture} appears in various works throughout the variational quantum computing literature. The conjecture asserts that a quantum circuit can be trained piece-wise, e.g.~that a few layers can be trained in sequence to minimize an objective function. Here we prove this conjecture false. Counterexamples are found by considering objective functions that are exponentially close (in the number of qubits) to the identity matrix. In the finite setting, we found abrupt transitions in the ability of quantum circuits to be trained to minimize these objective functions. Specifically, we found that below a critical (target gate dependent) threshold, circuit training terminates close to the identity and remains near to the identity for subsequently added blocks trained piece-wise. A critical layer depth will abruptly train arbitrarily close to the target, thereby minimizing the objective function. These findings shed new light on the divide-and-conquer trainability of variational quantum circuits and apply to a wide collection of contemporary literature., Comment: 11 pages, 8 figures, RevTeX

Determining properties of ground states of spin Hamiltonians remains a topic of central relevance connecting disciplines of mathematical, theoretical and applied physics. In the last few decades, ground state properties of physical systems have been increasingly considered as computational resources. This thesis develops parts of the mathematical apparatus to create (program) ground states relevant for quantum and classical computation. The core findings presented in this thesis (now over a decade old) including that (i) logic operations (gates) can be embedded into the low-energy sector of Ising spins whereas three (and higher) body Ising interaction terms can be mimicked through the minimisation of 2- and 1-body Ising terms yet require the introduction of slack spins; (ii) Perturbation theory gadgets enable the emulation of interactions not present in a given Hamiltonian, e.g.~$YY$ interactions can be realized from $ZZ$, $XX$, the thesis contains a result from 2007 showing that physically relevant two-body model Hamiltonian's have a QMA-hard ground state energy decision problem. Merged with other results, this established that these models provide a universal resource for ground state quantum computation. More recent findings include the proof that an idealised version of the contemporary variational approach to quantum algorithms enables a universal model of quantum computation. Other related results are also presented as they relate to ground state quantum computation and the minimisation of Hamiltonians by quantum circuits. The topics covered include: Ising model reductions, stochastic versus quantum processes on graphs, quantum gates and circuits as tensor networks, variational quantum algorithms and Hamiltonian gadgets., Comment: 241 pages, Dissertation draft submitted for the degree of Doctor of Physical and Mathematical Sciences

While there are various approaches to benchmark physical processors, recent findings have focused on computational phase transitions. This is due to several factors. Importantly, the hardest instances appear to be well-concentrated in a narrow region, with a control parameter allowing uniform random distributions of problem instances with similar computational challenge. It has been established that one could observe a computational phase transition in a distribution produced from coherent Ising machine(s). In terms of quantum approximate optimisation, the ability for the quantum algorithm to function depends critically on the ratio of a problems constraint to variable ratio (called density). The critical density dependence on performance resulted in what was called, reachability deficits. In this perspective we recall the background needed to understand how to apply computational phase transitions in various bench-marking tasks and we survey several such contemporary findings., Comment: 11 pages, 2+1 figures, JPhys Complexity (invited perspective)

Complex systems are large collections of entities that organize themselves into non-trivial structures that can be represented by networks. A key emergent property of such systems is robustness against random failures or targeted attacks ---i.e. the capacity of a network to maintain its integrity under removal of nodes or links. Here, we introduce network entanglement to study network robustness through a multi-scale lens, encoded by the time required to diffuse information through the system. Our measure's foundation lies upon a recently proposed framework, manifestly inspired by quantum statistical physics, where networks are interpreted as collections of entangled units and can be characterized by Gibbsian-like density matrices. We show that at the smallest temporal scales entanglement reduces to node degree, whereas at the large scale we show its ability to measure the role played by each node in network integrity. At the meso-scale, entanglement incorporates information beyond the structure, such as system's transport properties. As an application, we show that network dismantling of empirical social, biological and transportation systems unveils the existence of a optimal temporal scale driving the network to disintegration. Our results open the door for novel multi-scale analysis of network contraction process and its impact on dynamical processes., Comment: 20 pages, 4 figures

Solutions to many-body problem instances often involve an intractable number of degrees of freedom and admit no known approximations in general form. In practice, representing quantum-mechanical states of a given Hamiltonian using available numerical methods, in particular those based on variational Monte Carlo simulations, become exponentially more challenging with increasing system size. Recently quantum algorithms implemented as variational models have been proposed to accelerate such simulations. The variational ansatz states are characterized by a polynomial number of parameters devised in a way to minimize the expectation value of a given Hamiltonian, which is emulated by local measurements. In this study, we develop a means to certify the termination of variational algorithms. We demonstrate our approach by applying it to three models: the transverse field Ising model, the model of one-dimensional spinless fermions with competing interactions, and the Schwinger model of quantum electrodynamics. By means of comparison, we observe that our approach shows better performance near critical points in these models. We hence take a further step to improve the applicability and to certify the results of variational quantum simulators., Comment: 9 pages; 6 figures; REVTeX4-1

Hybrid quantum-classical algorithms have been proposed as a potentially viable application of quantum computers. A particular example - the variational quantum eigensolver, or VQE - is designed to determine a global minimum in an energy landscape specified by a quantum Hamiltonian, which makes it appealing for the needs of quantum chemistry. Experimental realizations have been reported in recent years and theoretical estimates of its efficiency are a subject of intense effort. Here we consider the performance of the VQE technique for a Hubbard-like model describing a one-dimensional chain of fermions with competing nearest- and next-nearest-neighbor interactions. We find that recovering the VQE solution allows one to obtain the correlation function of the ground state consistent with the exact result. We also study the barren plateau phenomenon for the Hamiltonian in question and find that the severity of this effect depends on the encoding of fermions to qubits. Our results are consistent with the current knowledge about the barren plateaus in quantum optimization., Comment: 7 pages, 7 figures, REVTeX4.2

Situated as a language between computer science, quantum physics and mathematics, tensor network theory has steadily grown in popularity and can now be found in applications ranging across the entire field of quantum information processing. This book aims to present the best contemporary practices in the use of tensor networks as a reasoning tool, placing quantum states, operators and processes on the same compositional footing. The book has 7 parts and over 40 subsections which took shape in over a decade of teaching. In addition to covering the foundations, the book covers important applications such as matrix product states, open quantum systems and entanglement $-$ all cast into the diagrammatic tensor network language. The intended audience includes those in quantum information science wishing to learn about tensor networks. It includes scientists who have employed tensor networks in their modeling codes who have interest in the tools graphical reasoning capacity. The audience further includes the graduate student researcher, whom with some effort, should find this book accessible. I would appreciate it if you emailed me about any mistakes or typos you find., Comment: 178 page book in LaTeX. Please email me about any mistakes or typos. Current version always available on overleaf, see http://www.overleaf.com/read/jkccbhcdqwnh

The quantum approximate optimization algorithm (QAOA) is considered to be one of the most promising approaches towards using near-term quantum computers for practical application. In its original form, the algorithm applies two different Hamiltonians, called the mixer and the cost Hamiltonian, in alternation with the goal being to approach the ground state of the cost Hamiltonian. Recently, it has been suggested that one might use such a set-up as a parametric quantum circuit with possibly some other goal than reaching ground states. From this perspective, a recent work [S. Lloyd, arXiv:1812.11075] argued that for one-dimensional local cost Hamiltonians, composed of nearest neighbor ZZ terms, this set-up is quantum computationally universal, i.e., all unitaries can be reached up to arbitrary precision. In the present paper, we give the complete proof of this statement and the precise conditions under which such a one-dimensional QAOA might be considered universal. We further generalize this type of universality for certain cost Hamiltonians with ZZ and ZZZ terms arranged according to the adjacency structure of certain graphs and hypergraphs., Comment: 18+6 pages, 3 figures

Machine learning has emerged as a promising approach to study the properties of many-body systems. Recently proposed as a tool to classify phases of matter, the approach relies on classical simulation methods$-$such as Monte Carlo$-$which are known to experience an exponential slowdown when simulating certain quantum systems. To overcome this slowdown while still leveraging machine learning, we propose a variational quantum algorithm which merges quantum simulation and quantum machine learning to classify phases of matter. Our classifier is directly fed labeled states recovered by the variational quantum eigensolver algorithm, thereby avoiding the data reading slowdown experienced in many applications of quantum enhanced machine learning. We propose families of variational ansatz states that are inspired directly by tensor networks. This allows us to use tools from tensor network theory to explain properties of the phase diagrams the presented method recovers. Finally, we propose a nearest-neighbour (checkerboard) quantum neural network. This majority vote quantum classifier is successfully trained to recognize phases of matter with $99\%$ accuracy for the transverse field Ising model and $94\%$ accuracy for the XXZ model. These findings suggest that our merger between quantum simulation and quantum enhanced machine learning offers a fertile ground to develop computational insights into quantum systems., Comment: feedback welcome; 10 pages; 10 figures; RevTex

This $Physics$ viewpoint considers recent work by Tilloy and Cirac [Phys. Rev. X 9, 021040 (2019), arXiv:1808.00976]; those authors overcame several past limitations in the generalization of tensor networks to the continuum and proposed a new class of continuous tensor network states (cMPS) which apply to spatial dimensions of two and higher., Comment: Published version; 2 pages; 1 figure

Quantum tomography is currently ubiquitous for testing any implementation of a quantum information processing device. Various sophisticated procedures for state and process reconstruction from measured data are well developed and benefit from precise knowledge of the model describing state preparation and the measurement apparatus. However, physical models suffer from intrinsic limitations as actual measurement operators and trial states cannot be known precisely. This scenario inevitably leads to state-preparation-and-measurement (SPAM) errors degrading reconstruction performance. Here we develop and experimentally implement a machine learning based protocol reducing SPAM errors. We trained a supervised neural network to filter the experimental data and hence uncovered salient patterns that characterize the measurement probabilities for the original state and the ideal experimental apparatus free from SPAM errors. We compared the neural network state reconstruction protocol with a protocol treating SPAM errors by process tomography, as well as to a SPAM-agnostic protocol with idealized measurements. The average reconstruction fidelity is shown to be enhanced by 10\% and 27\%, respectively. The presented methods apply to the vast range of quantum experiments which rely on tomography., Comment: 11 pages, 3+6 figures; All data and source code are available online; RevTeX

Variational quantum algorithms dominate contemporary gate-based quantum enhanced optimisation, eigenvalue estimation and machine learning. Here we establish the quantum computational universality of variational quantum computation by developing two objective functions which minimise to prepare outputs of arbitrary quantum circuits. The fleeting resource of variational quantum computation is the number of expected values which must be iteratively minimised using classical-to-quantum outer loop optimisation. An efficient solution to this optimisation problem is given by the quantum circuit being simulated itself. The first construction is efficient in the number of expected values for $n$-qubit circuits containing $\mathcal{O}({poly} \ln n)$ non-Clifford gates -- the number of expected values has no dependence on Clifford gates appearing in the simulated circuit. The second approach yields $\mathcal{O}(L^2)$ expected values while introducing not more than $\mathcal{O}(\ln L)$ slack qubits, for a quantum circuit partitioned into $L$ gates. Hence, the utilitarian variational quantum programming procedure -- based on the classical evaluation of objective functions and iterated feedback -- is in principle as powerful as any other model of quantum computation. This result elevates the formal standing of the variational approach while establishing a new universal model of quantum computation., Comment: 12 pages, RevTeX

Complex network theory has shown success in understanding the emergent and collective behavior of complex systems [1]. Many real-world complex systems were recently discovered to be more accurately modeled as multiplex networks [2-6]---in which each interaction type is mapped to its own network layer; e.g.~multi-layer transportation networks, coupled social networks, metabolic and regulatory networks, etc. A salient physical phenomena emerging from multiplexity is super-diffusion: exhibited by an accelerated diffusion admitted by the multi-layer structure as compared to any single layer. Theoretically super-diffusion was only known to be predicted using the spectral gap of the full Laplacian of a multiplex network and its interacting layers. Here we turn to machine learning which has developed techniques to recognize, classify, and characterize complex sets of data. We show that modern machine learning architectures, such as fully connected and convolutional neural networks, can classify and predict the presence of super-diffusion in multiplex networks with 94.12\% accuracy. Such predictions can be done {\it in situ}, without the need to determine spectral properties of a network., Comment: 12 pages, 6 figures

A contemporary technological milestone is to build a quantum device performing a computational task beyond the capability of any classical computer, an achievement known as quantum adversarial advantage. In what ways can the entanglement realized in such a demonstration be quantified? Inspired by the area law of tensor networks, we derive an upper bound for the minimum random circuit depth needed to generate the maximal bipartite entanglement correlations between all problem variables (qubits). This bound is (i) lattice geometry dependent and (ii) makes explicit a nuance implicit in other proposals with physical consequence. The hardware itself should be able to support super-logarithmic ebits of entanglement across some poly($n$) number of qubit-bipartitions, otherwise the quantum state itself will not possess volumetric entanglement scaling and full-lattice-range correlations. Hence, as we present a connection between quantum advantage protocols and quantum entanglement, the entanglement implicitly generated by such protocols can be tested separately to further ascertain the validity of any quantum advantage claim., Comment: updates and improvements from the review process; 8 pages; 3 figures

Given a parameterized quantum circuit such that a certain setting of these real-valued parameters corresponds to Grover's celebrated search algorithm, can a variational algorithm recover these settings and hence learn Grover's algorithm? We studied several constrained variations of this problem and answered this question in the affirmative, with some caveats. Grover's quantum search algorithm is optimal up to a constant. The success probability of Grover's algorithm goes from unity for two-qubits, decreases for three- and four-qubits and returns near unity for five-qubits then oscillates ever-so-close to unity, reaching unity in the infinite qubit limit. The variationally approach employed here found an experimentally discernible improvement of $5.77\%$ and $3.95\%$ for three- and four-qubits respectively. Our findings are interesting as an extreme example of variational search, and illustrate the promise of using hybrid quantum classical approaches to improve quantum algorithms. This paper further demonstrates that to find optimal parameters one doesn't need to vary over a family of quantum circuits to find an optimal solution. This result looks promising and points out that there is a set of variational quantum problems with parameters that can be efficiently found on a classical computer for arbitrary number of qubits., Comment: Accepted version (PRA); All supporting data and source code are available online; 8 pages; 4 figures; RevTeX

Tensor network algorithms seek to minimize correlations to compress the classical data representing quantum states. Tensor network algorithms and similar tools---called tensor network methods---form the backbone of modern numerical methods used to simulate many-body physics and have a further range of applications in machine learning. Finding and contracting tensor network states is a computational task which quantum computers might be used to accelerate. We present a quantum algorithm which returns a classical description of a rank-$r$ tensor network state satisfying an area law and approximating an eigenvector given black-box access to a unitary matrix. Our work creates a bridge between several contemporary approaches, including tensor networks, the variational quantum eigensolver (VQE), quantum approximate optimization (QAOA), and quantum computation., Comment: 6 pages, 2 figures, numerics added

Can near-term gate model based quantum processors offer quantum advantage for practical applications in the pre-fault tolerance noise regime? A class of algorithms which have shown some promise in this regard are the so-called classical-quantum hybrid variational algorithms. Here we develop a low-depth quantum algorithm to generative neural networks using variational quantum circuits. We introduce a method which employs the quantum approximate optimization algorithm as a subroutine in order produce then sample low-energy distributions of Ising Hamiltonians. We sample these states to train neural networks and demonstrate training convergence for numerically simulated noisy circuits with depolarizing errors of rates of up to $4\%$., Comment: 9 pages, 4 figures, submitted to review in a journal

Tensor network methods are taking a central role in modern quantum physics and beyond. They can provide an efficient approximation to certain classes of quantum states, and the associated graphical language makes it easy to describe and pictorially reason about quantum circuits, channels, protocols, open systems and more. Our goal is to explain tensor networks and some associated methods as quickly and as painlessly as possible. Beginning with the key definitions, the graphical tensor network language is presented through examples. We then provide an introduction to matrix product states. We conclude the tutorial with tensor contractions evaluating combinatorial counting problems. The first one counts the number of solutions for Boolean formulae, whereas the second is Penrose's tensor contraction algorithm, returning the number of $3$-edge-colorings of $3$-regular planar graphs., Comment: to appear in Contemporary Physics, 34 pages

Understanding which physical processes are symmetric with respect to time inversion is a ubiquitous problem in physics. In quantum physics, effective gauge fields allow emulation of matter under strong magnetic fields, realizing the Harper-Hofstadter, the Haldane models, demonstrating one-way waveguides and topologically protected edge states. Central to these discoveries is the chirality induced by time-symmetry breaking. In quantum walk algorithms, recent work has discovered implications time-reversal symmetry breaking has on the transport of quantum states which has enabled a host of new experimental implementations. We provide a full topological classification of the Hamiltonians of operators breaking time-reversal symmetry in their induced transition probabilities between elements in a preferred site-basis. We prove that a quantum process is necessarily time-symmetric for any choice of time-independent Hamiltonian precisely when the underlying support graph is bipartite or no Aharonov-Bohm phases are present in the gauge field. We further prove that certain bipartite graphs exhibit transition probability suppression, but not broken time-reversal symmetry. Furthermore, our development of a general framework characterizes gauge potentials on combinatorial graphs. These results and techniques fill an important missing gap in understanding the role this omnipresent effect has in quantum information and computation.

Tensor network methods provide an intuitive graphical language to describe quantum states, channels, open quantum systems and a class of numerical approximation methods that efficiently simulate certain many-body states in one spatial dimension. There are two fundamental types of tensor networks in wide use today. The most common is similar to quantum circuits. The second is the braided class of tensor networks, used in topological quantum computing. Recently a third class of tensor networks was discovered by Jaffe, Liu and Wozniakowski---the JLW-model---notably, the wires carry charge excitations. The rules in which network components can be moved, merged and manipulated in a graphical form of reasoning take an elegant form. For instance the relative charge locations on wires carries precise meaning and changing the ordering modifies a connected network specifically by a complex number. The type of isotopy discovered in the topological JLW-model provides an alternative means to reason about quantum information, computation and protocols. Here we recall the tensor-network building blocks used in a controlled-NOT gate. Some open problems related to the JLW-model are given., Comment: published version + significance statement/abstract

Recent progress in applying complex network theory to problems in quantum information has resulted in a beneficial crossover. Complex network methods have successfully been applied to transport and entanglement models while information physics is setting the stage for a theory of complex systems with quantum information-inspired methods. Novel quantum induced effects have been predicted in random graphs---where edges represent entangled links---and quantum computer algorithms have been proposed to offer enhancement for several network problems. Here we review the results at the cutting edge, pinpointing the similarities and the differences found at the intersection of these two fields., Comment: 12 pages, 4 figures, REVTeX 4-1, accepted version

Fuelled by increasing computer power and algorithmic advances, machine learning techniques have become powerful tools for finding patterns in data. Since quantum systems produce counter-intuitive patterns believed not to be efficiently produced by classical systems, it is reasonable to postulate that quantum computers may outperform classical computers on machine learning tasks. The field of quantum machine learning explores how to devise and implement concrete quantum software that offers such advantages. Recent work has made clear that the hardware and software challenges are still considerable but has also opened paths towards solutions., Comment: 24 pages, 2 figures

Any physical system can be viewed from the perspective that information is implicitly represented in its state. However, the quantification of this information when it comes to complex networks has remained largely elusive. In this work, we use techniques inspired by quantum statistical mechanics to define an entropy measure for complex networks and to develop a set of information-theoretic tools, based on network spectral properties, such as Renyi q-entropy, generalized Kullback-Leibler and Jensen-Shannon divergences, the latter allowing us to define a natural distance measure between complex networks. First we show that by minimizing the Kullback-Leibler divergence between an observed network and a parametric network model, inference of model parameter(s) by means of maximum-likelihood estimation can be achieved and model selection can be performed appropriate information criteria. Second, we show that the information-theoretic metric quantifies the distance between pairs of networks and we can use it, for instance, to cluster the layers of a multilayer system. By applying this framework to networks corresponding to sites of the human microbiome, we perform hierarchical cluster analysis and recover with high accuracy existing community-based associations. Our results imply that spectral based statistical inference in complex networks results in demonstrably superior performance as well as a conceptual backbone, filling a gap towards a network information theory., Comment: 13 pages, 6 figures

The computational cost of counting the number of solutions satisfying a Boolean formula, which is a problem instance of #SAT, has proven subtle to quantify. Even when finding individual satisfying solutions is computationally easy (e.g. 2-SAT, which is in P), determining the number of solutions is #P-hard. Recently, computational methods simulating quantum systems experienced advancements due to the development of tensor network algorithms and associated quantum physics-inspired techniques. By these methods, we give an algorithm using an axiomatic tensor contraction language for n-variable #SAT instances with complexity $O((g+cd)^{O(1)} 2^c)$ where $c$ is the number of COPY-tensors, $g$ is the number of gates, and $d$ is the maximal degree of any COPY-tensor. Thus, counting problems can be solved efficiently when their tensor network expression has at most $O(\log c)$ COPY-tensors and polynomial fan-out. This framework also admits an intuitive proof of a variant of the Tovey conjecture (the r,1-SAT instance of the Dubois-Tovey theorem). This study increases the theory, expressiveness and application of tensor based algorithmic tools and provides an alternative insight on these problems which have a long history in statistical physics and computer science., Comment: 16 pages, 8 diagrams

Given its importance to many other areas of physics, from condensed matter physics to thermodynamics, time-reversal symmetry has had relatively little influence on quantum information science. Here we develop a network-based picture of time-reversal theory, classifying Hamiltonians and quantum circuits as time-symmetric or not in terms of the elements and geometries of their underlying networks. Many of the typical circuits of quantum information science are found to exhibit time-asymmetry. Moreover, we show that time-asymmetry in circuits can be controlled using local gates only, and can simulate time-asymmetry in Hamiltonian evolution. We experimentally implement a fundamental example in which controlled time-reversal asymmetry in a palindromic quantum circuit leads to near-perfect transport. Our results pave the way for using time-symmetry breaking to control coherent transport, and imply that time-asymmetry represents an omnipresent yet poorly understood effect in quantum information science., Comment: 9 pages, 4 figures, REVTeX 4.1 - published version

\emph{Ab initio} computation of molecular properties is one of the most promising applications of quantum computing. While this problem is widely believed to be intractable for classical computers, efficient quantum algorithms exist which have the potential to vastly accelerate research throughput in fields ranging from material science to drug discovery. Using a solid-state quantum register realized in a nitrogen-vacancy (NV) defect in diamond, we compute the bond dissociation curve of the minimal basis helium hydride cation, HeH$^+$. Moreover, we report an energy uncertainty (given our model basis) of the order of $10^{-14}$ Hartree, which is ten orders of magnitude below desired chemical precision. As NV centers in diamond provide a robust and straightforward platform for quantum information processing, our work provides several important steps towards a fully scalable solid state implementation of a quantum chemistry simulator., Comment: 9 pages, 4 figures

Application of the adiabatic model of quantum computation requires efficient encoding of the solution to computational problems into the lowest eigenstate of a Hamiltonian that supports universal adiabatic quantum computation. Experimental systems are typically limited to restricted forms of 2-body interactions. Therefore, universal adiabatic quantum computation requires a method for approximating quantum many-body Hamiltonians up to arbitrary spectral error using at most 2-body interactions. Hamiltonian gadgets, introduced around a decade ago, offer the only current means to address this requirement. Although the applications of Hamiltonian gadgets have steadily grown since their introduction, little progress has been made in overcoming the limitations of the gadgets themselves. In this experimentally motivated theoretical study, we introduce several gadgets which require significantly more realistic control parameters than similar gadgets in the literature. We employ analytical techniques which result in a reduction of the resource scaling as a function of spectral error for the commonly used subdivision, 3- to 2-body and $k$-body gadgets. Accordingly, our improvements reduce the resource requirements of all proofs and experimental proposals making use of these common gadgets. Next, we numerically optimize these new gadgets to illustrate the tightness of our analytical bounds. Finally, we introduce a new gadget that simulates a $YY$ interaction term using Hamiltonians containing only $\{X,Z,XX,ZZ\}$ terms. Apart from possible implications in a theoretical context, this work could also be useful for a first experimental implementation of these key building blocks by requiring less control precision without introducing extra ancillary qubits., Comment: 33 pages, 9 figures

Determining community structure is a central topic in the study of complex networks, be it technological, social, biological or chemical, in static or interacting systems. In this paper, we extend the concept of community detection from classical to quantum systems---a crucial missing component of a theory of complex networks based on quantum mechanics. We demonstrate that certain quantum mechanical effects cannot be captured using current classical complex network tools and provide new methods that overcome these problems. Our approaches are based on defining closeness measures between nodes, and then maximizing modularity with hierarchical clustering. Our closeness functions are based on quantum transport probability and state fidelity, two important quantities in quantum information theory. To illustrate the effectiveness of our approach in detecting community structure in quantum systems, we provide several examples, including a naturally occurring light-harvesting complex, LHCII. The prediction of our simplest algorithm, semiclassical in nature, mostly agrees with a proposed partitioning for the LHCII found in quantum chemistry literature, whereas our fully quantum treatment of the problem uncovers a new, consistent, and appropriately quantum community structure., Comment: 16 pages, 4 figures, 1 table

Precise control of quantum systems is of fundamental importance for quantum device engineering, such as is needed in the fields of quantum information processing, high-resolution spectroscopy and quantum metrology. When scaling up the quantum registers in such devices, several challenges arise: individual addressing of qubits in a dense spectrum while suppressing crosstalk, creation of entanglement between distant nodes, and decoupling from unwanted interactions. The experimental implementation of optimal control is a prerequisite to meeting these challenges. Using engineered microwave pulses, we experimentally demonstrate optimal control of a prototype solid state spin qubit system comprising thirty six energy levels. The spin qubits are associated with proximal nitrogen-vacancy (NV) centers in diamond. We demonstrate precise single-electron spin qubit operations with an unprecedented fidelity F \approx 0.99 in combination with high-efficiency storage of electron spin states in a nuclear spin quantum memory. Matching single-electron spin operations with spin-echo techniques, we further realize high-quality entangled states (F > 0.82) between two electron spins on demand. After exploiting optimal control, the fidelity is mostly limited by the coherence time and imperfect initialization. Errors from crosstalk in a crowded spectrum of 8 lines as well as detrimental effects from active dipolar couplings have been simultaneously eliminated to unprecedented extent. Finally, by entanglement swapping to nuclear spins, nuclear spin entanglement over a length scale of 25 nm is demonstrated. This experiment underlines the importance of optimal control for scalable room temperature spin-based quantum information devices., Comment: 10+6 pages, 6 figures

In this theoretical study, we analyze quantum walks on complex networks, which model network-based processes ranging from quantum computing to biology and even sociology. Specifically, we analytically relate the average long time probability distribution for the location of a unitary quantum walker to that of a corresponding classical walker. The distribution of the classical walker is proportional to the distribution of degrees, which measures the connectivity of the network nodes and underlies many methods for analyzing classical networks including website ranking. The quantum distribution becomes exactly equal to the classical distribution when the walk has zero energy and at higher energies the difference, the so-called quantumness, is bounded by the energy of the initial state. We give an example for which the quantumness equals a Renyi entropy of the normalized weighted degrees, guiding us to regimes for which the classical degree-dependent result is recovered and others for which quantum effects dominate., Comment: 8 pages, 4 figures; improved description and new examples; accepted for publication in Phys. Rev. X

Some ideas from quantum theory are just beginning to percolate back to classical probability theory. For example, there is a widely used and successful theory of "chemical reaction networks", which describes the interactions of molecules in a stochastic rather than quantum way. Computer science and population biology use the same ideas under a different name: "stochastic Petri nets". But if we look at these theories from the perspective of quantum theory, they turn out to involve creation and annihilation operators, coherent states and other well-known ideas - but in a context where probabilities replace amplitudes. We explain this connection as part of a detailed analogy between quantum mechanics and stochastic mechanics. We use this analogy to present new proofs of two major results in the theory of chemical reaction networks: the deficiency zero theorem and the Anderson-Craciun-Kurtz theorem. We also study the overlap of quantum mechanics and stochastic mechanics, which involves Hamiltonians that can generate either unitary or stochastic time evolution. These Hamiltonians are called "Dirichlet forms", and they arise naturally from electrical circuits made only of resistors., Comment: 274 pages, many figures

Invariant theory is concerned with functions that do not change under the action of a given group. Here we communicate an approach based on tensor networks to represent polynomial local unitary invariants of quantum states. This graphical approach provides an alternative to the polynomial equations that describe invariants, which often contain a large number of terms with coefficients raised to high powers. This approach also enables one to use known methods from tensor network theory (such as the matrix product state factorization) when studying polynomial invariants. As our main example, we consider invariants of matrix product states. We generate a family of tensor contractions resulting in a complete set of local unitary invariants that can be used to express the R\'enyi entropies. We find that the graphical approach to representing invariants can provide structural insight into the invariants being contracted, as well as an alternative, and sometimes much simpler, means to study polynomial invariants of quantum states. In addition, many tensor network methods, such as matrix product states, contain excellent tools that can be applied in the study of invariants., Comment: 21 pages

Quantum mechanics still provides new unexpected effects when considering the transport of energy and information. Models of continuous time quantum walks, which implicitly use time-reversal symmetric Hamiltonians, have been intensely used to investigate the effectiveness of transport. Here we show how breaking time-reversal symmetry of the unitary dynamics in this model can enable directional control, enhancement, and suppression of quantum transport. Examples ranging from exciton transport to complex networks are presented. This opens new prospects for more efficient methods to transport energy and information., Comment: 6+5 pages