BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Nathan Wiebe

Nathan Wiebe appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phMachine Learningphysics.chem-phcond-mat.str-elmath-phmath.MPNumerical AnalysisData Structures and AlgorithmsEmerging Technologiesmath.NANeural and Evolutionary Computingcond-mat.stat-mechhep-latmath.OCnucl-th

Catalog footprint

What is connected

50works
15topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

50 published item(s)

preprint2025arXiv

Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications

Quantum computing with discrete variable (DV, qubit) hardware is approaching the large scales necessary for computations beyond the reach of classical computers. However, important use cases such as quantum simulations of physical models containing bosonic modes, and quantum error correction are challenging for DV-only systems. Separately, hardware containing native continuous-variable (CV, oscillator) systems has received attention as an alternative approach, yet the universal control of such systems is non-trivial. In this work, we show that hybrid CV-DV hardware offers a great advantage in meeting these challenges, offering a powerful computational paradigm that inherits the strengths of both DV and CV processors. We provide a pedagogical introduction to CV-DV systems and the multiple abstraction layers needed to produce a full software stack connecting applications to hardware. We present a variety of new hybrid CV-DV compilation techniques, algorithms, and applications, including the extension of quantum signal processing concepts to CV-DV systems and strategies to simulate systems of interacting spins, fermions, and bosons. To facilitate the development of hybrid CV-DV processor systems, we introduce formal Abstract Machine Models and Instruction Set Architectures -- essential abstractions that enable developers to formulate applications, compile algorithms, and explore the potential of current and future hardware for realizing fault-tolerant circuits, modules, and processors. Hybrid CV-DV quantum computations are beginning to be performed in superconducting, trapped ion, and neutral atom platforms, and large-scale experiments are set to be demonstrated in the near future. We present a timely and comprehensive guide to this relatively unexplored yet promising approach to quantum computation and providing an architectural backbone to guide future development.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Generating Approximate Ground States of Molecules Using Quantum Machine Learning

The potential energy surface (PES) of molecules with respect to their nuclear positions is a primary tool in understanding chemical reactions from first principles. However, obtaining this information is complicated by the fact that sampling a large number of ground states over a high-dimensional PES can require a vast number of state preparations. In this work, we propose using a generative quantum machine learning model to prepare quantum states at arbitrary points on the PES. The model is trained using quantum data consisting of ground-state wavefunctions associated with different classical nuclear coordinates. Our approach uses a classical neural network to convert the nuclear coordinates of a molecule into quantum parameters of a variational quantum circuit. The model is trained using a fidelity loss function to optimize the neural network parameters. We show that gradient evaluation is efficient and numerically demonstrate our method's ability to prepare wavefunctions on the PES of hydrogen chains, water, and beryllium hydride. In all cases, we find that a small number of training points are needed to achieve very high overlap with the groundstates in practice. From a theoretical perspective, we further prove limitations on these protocols by showing that if we were able to learn across an avoided crossing using a small number of samples, then we would be able to violate Grover's lower bound. Additionally, we prove lower bounds on the amount of quantum data needed to learn a locally optimal neural network function using arguments from quantum Fisher information. This work further identifies that quantum chemistry can be an important use case for quantum machine learning.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Hybridized Methods for Quantum Simulation in the Interaction Picture

Conventional methods of quantum simulation involve trade-offs that limit their applicability to specific contexts where their use is optimal. In particular, the interaction picture simulation has been found to provide substantial asymptotic advantages for some Hamiltonians, but incurs prohibitive constant factors and is incompatible with methods like qubitization. We provide a framework that allows different simulation methods to be hybridized and thereby improve performance for interaction picture simulations over known algorithms. These approaches show asymptotic improvements over the individual methods that comprise them and further make interaction picture simulation methods practical in the near term. Physical applications of these hybridized methods yield a gate complexity scaling as $\log^2 Λ$ in the electric cutoff $Λ$ for the Schwinger Model and independent of the electron density for collective neutrino oscillations, outperforming the scaling for all current algorithms with these parameters. For the general problem of Hamiltonian simulation subject to dynamical constraints, these methods yield a query complexity independent of the penalty parameter $λ$ used to impose an energy cost on time-evolution into an unphysical subspace.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quantum Machine Learning with SQUID

In this work we present the Scaled QUantum IDentifier (SQUID), an open-source framework for exploring hybrid Quantum-Classical algorithms for classification problems. The classical infrastructure is based on PyTorch and we provide a standardized design to implement a variety of quantum models with the capability of back-propagation for efficient training. We present the structure of our framework and provide examples of using SQUID in a standard binary classification problem from the popular MNIST dataset. In particular, we highlight the implications for scalability for gradient-based optimization of quantum models on the choice of output for variational quantum models.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Simulating Effective QED on Quantum Computers

In recent years simulations of chemistry and condensed materials has emerged as one of the preeminent applications of quantum computing, offering an exponential speedup for the solution of the electronic structure for certain strongly correlated electronic systems. To date, most treatments have ignored the question of whether relativistic effects, which are described most generally by quantum electrodynamics (QED), can also be simulated on a quantum computer in polynomial time. Here we show that effective QED, which is equivalent to QED to second order in perturbation theory, can be simulated in polynomial time under reasonable assumptions while properly treating all four components of the wavefunction of the fermionic field. In particular, we provide a detailed analysis of such simulations in position and momentum basis using Trotter-Suzuki formulas. We find that the number of $T$-gates needed to perform such simulations on a $3D$ lattice of $n_s$ sites scales at worst as $O(n_s^3/ε)^{1+o(1)}$ in the thermodynamic limit for position basis simulations and $O(n_s^{4+2/3}/ε)^{1+o(1)}$ in momentum basis. We also find that qubitization scales slightly better with a worst case scaling of $\widetilde{O}(n_s^{2+2/3}/ε)$ for lattice eQED and complications in the prepare circuit leads to a slightly worse scaling in momentum basis of $\widetilde{O}(n_s^{5+2/3}/ε)$. We further provide concrete gate counts for simulating a relativistic version of the uniform electron gas that show challenging problems can be simulated using fewer than $10^{13}$ non-Clifford operations and also provide a detailed discussion of how to prepare multi-reference configuration interaction states in effective QED which can provide a reasonable initial guess for the ground state. Finally, we estimate the planewave cutoffs needed to accurately simulate heavy elements such as gold.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Towards solving the Fermi-Hubbard model via tailored quantum annealers

The Fermi-Hubbard model (FHM) on a two dimensional square lattice has long been an important testbed and target for simulating fermionic Hamiltonians on quantum hardware. We present an alternative for quantum simulation of FHMs based on an adiabatic protocol that could be an attractive target for next generations of quantum annealers. Our results rely on a recently introduced low-weight encoding that allows the FHM to be expressed in terms of Pauli operators with locality of at most three. We theoretically and numerically determine promising quantum annealing setups for both interacting 2D spinless and spinful systems, that enable to reach near the ground state solution with high fidelity for systems as big as $6\times 6$ (spinless) and $4\times 3$ (spinful). Moreover, we demonstrate the scaling properties of the minimal gap and analyze robustness of the protocol against control noise. Additionally, we identify and discuss basic experimental requirements to construct near term annealing hardware tailored to simulate these problems. Finally, we perform a detailed resource estimation for the introduced adiabatic protocol, and discuss pros and cons of this approach relative to gate-based approaches for near-term platforms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Using Random Walks for Iterative Phase Estimation

In recent years there has been substantial development in algorithms for quantum phase estimation. In this work we provide a new approach to online Bayesian phase estimation that achieves Heisenberg limited scaling that requires exponentially less classical processing time with the desired error tolerance than existing Bayesian methods. This practically means that we can perform an update in microseconds on a CPU as opposed to milliseconds for existing particle filter methods. Our approach assumes that the prior distribution is Gaussian and exploits the fact, when optimal experiments are chosen, the mean of the prior distribution is given by the position of a random walker whose moves are dictated by the measurement outcomes. We then argue from arguments based on the Fisher information that our algorithm provides a near-optimal analysis of the data. This work shows that online Bayesian inference is practical, efficient and ready for deployment in modern FPGA driven adaptive experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A Theory of Trotter Error

The Lie-Trotter formula, together with its higher-order generalizations, provides a direct approach to decomposing the exponential of a sum of operators. Despite significant effort, the error scaling of such product formulas remains poorly understood. We develop a theory of Trotter error that overcomes the limitations of prior approaches based on truncating the Baker-Campbell-Hausdorff expansion. Our analysis directly exploits the commutativity of operator summands, producing tighter error bounds for both real- and imaginary-time evolutions. Whereas previous work achieves similar goals for systems with geometric locality or Lie-algebraic structure, our approach holds in general. We give a host of improved algorithms for digital quantum simulation and quantum Monte Carlo methods, including simulations of second-quantized plane-wave electronic structure, $k$-local Hamiltonians, rapidly decaying power-law interactions, clustered Hamiltonians, the transverse field Ising model, and quantum ferromagnets, nearly matching or even outperforming the best previous results. We obtain further speedups using the fact that product formulas can preserve the locality of the simulated system. Specifically, we show that local observables can be simulated with complexity independent of the system size for power-law interacting systems, which implies a Lieb-Robinson bound as a byproduct. Our analysis reproduces known tight bounds for first- and second-order formulas. Our higher-order bound overestimates the complexity of simulating a one-dimensional Heisenberg model with an even-odd ordering of terms by only a factor of $5$, and is close to tight for power-law interactions and other orderings of terms. This suggests that our theory can accurately characterize Trotter error in terms of both asymptotic scaling and constant prefactor.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Quantum Model Learning Agent: characterisation of quantum systems through machine learning

Accurate models of real quantum systems are important for investigating their behaviour, yet are difficult to distill empirically. Here, we report an algorithm -- the Quantum Model Learning Agent (QMLA) -- to reverse engineer Hamiltonian descriptions of a target system. We test the performance of QMLA on a number of simulated experiments, demonstrating several mechanisms for the design of candidate Hamiltonian models and simultaneously entertaining numerous hypotheses about the nature of the physical interactions governing the system under study. QMLA is shown to identify the true model in the majority of instances, when provided with limited a priori information, and control of the experimental setup. Our protocol can explore Ising, Heisenberg and Hubbard families of models in parallel, reliably identifying the family which best describes the system dynamics. We demonstrate QMLA operating on large model spaces by incorporating a genetic algorithm to formulate new hypothetical models. The selection of models whose features propagate to the next generation is based upon an objective function inspired by the Elo rating scheme, typically used to rate competitors in games such as chess and football. In all instances, our protocol finds models that exhibit $F_1$-score $\geq 0.88$ when compared with the true model, and it precisely identifies the true model in 72% of cases, whilst exploring a space of over $250,000$ potential models. By testing which interactions actually occur in the target system, QMLA is a viable tool for both the exploration of fundamental physics and the characterisation and calibration of quantum devices.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Variational Quantum Algorithm for Preparing Quantum Gibbs States

Preparation of Gibbs distributions is an important task for quantum computation. It is a necessary first step in some types of quantum simulations and further is essential for quantum algorithms such as quantum Boltzmann training. Despite this, most methods for preparing thermal states are impractical to implement on near-term quantum computers because of the memory overheads required. Here we present a variational approach to preparing Gibbs states that is based on minimizing the free energy of a quantum system. The key insight that makes this practical is the use of Fourier series approximations to the logarithm that allows the entropy component of the free-energy to be estimated through a sequence of simpler measurements that can be combined together using classical post processing. We further show that this approach is efficient for generating high-temperature Gibbs states, within constant error, if the initial guess for the variational parameters for the programmable quantum circuit are sufficiently close to a global optima. Finally, we examine the procedure numerically and show the viability of our approach for five-qubit Hamiltonians using Trotterized adiabatic state preparation as an ansatz.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Bayesian phase estimation with adaptive grid refinement

We introduce a novel Bayesian phase estimation technique based on adaptive grid refinement method. This method automatically chooses the number particles needed for accurate phase estimation using grid refinement and cell merging strategies such that the total number of particles needed at each step is minimal. The proposed method provides a powerful alternative to traditional sampling based sequential Monte Carlo method which tend to fail in certain instances such as when the posterior distribution is bimodal. We also combine grid based and sampling based methods as hybrid particle filter where grid based method can be used to estimate a small but dominant set of parameters and Liu-West (LW) based SMC for the remaining set of parameters. Principal kurtosis analysis can be used to decide the choice of parameters for grid refinement method and for sampling based methods. We provide numerical results comparing the performance of the proposed grid refinement method with Liu-West resampling based SMC. Numerical results suggest that the proposed method is quite promising for quantum phase estimation. It can be easily adapted to Hamiltonian learning which is a very useful technique for estimating unknown parameters of a Hamiltonian and for characterizing unknown quantum devices.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Efficient and Noise Resilient Measurements for Quantum Chemistry on Near-Term Quantum Computers

Variational algorithms are a promising paradigm for utilizing near-term quantum devices for modeling electronic states of molecular systems. However, previous bounds on the measurement time required have suggested that the application of these techniques to larger molecules might be infeasible. We present a measurement strategy based on a low rank factorization of the two-electron integral tensor. Our approach provides a cubic reduction in term groupings over prior state-of-the-art and enables measurement times three orders of magnitude smaller than those suggested by commonly referenced bounds for the largest systems we consider. Although our technique requires execution of a linear-depth circuit prior to measurement, this is compensated for by eliminating challenges associated with sampling non-local Jordan-Wigner transformed operators in the presence of measurement error, while enabling a powerful form of error mitigation based on efficient postselection. We numerically characterize these benefits with noisy quantum circuit simulations for ground state energies of strongly correlated electronic systems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Hartree-Fock on a superconducting qubit quantum computer

As the search continues for useful applications of noisy intermediate scale quantum devices, variational simulations of fermionic systems remain one of the most promising directions. Here, we perform a series of quantum simulations of chemistry the largest of which involved a dozen qubits, 78 two-qubit gates, and 114 one-qubit gates. We model the binding energy of ${\rm H}_6$, ${\rm H}_8$, ${\rm H}_{10}$ and ${\rm H}_{12}$ chains as well as the isomerization of diazene. We also demonstrate error-mitigation strategies based on $N$-representability which dramatically improve the effective fidelity of our experiments. Our parameterized ansatz circuits realize the Givens rotation approach to non-interacting fermion evolution, which we variationally optimize to prepare the Hartree-Fock wavefunction. This ubiquitous algorithmic primitive corresponds to a rotation of the orbital basis and is required by many proposals for correlated simulations of molecules and Hubbard models. Because non-interacting fermion evolutions are classically tractable to simulate, yet still generate highly entangled states over the computational basis, we use these experiments to benchmark the performance of our hardware while establishing a foundation for scaling up more complex correlated quantum simulations of chemistry.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization

Recent work has deployed linear combinations of unitaries techniques to reduce the cost of fault-tolerant quantum simulations of correlated electron models. Here, we show that one can sometimes improve upon those results with optimized implementations of Trotter-Suzuki-based product formulas. We show that low-order Trotter methods perform surprisingly well when used with phase estimation to compute relative precision quantities (e.g. energies per unit cell), as is often the goal for condensed-phase systems. In this context, simulations of the Hubbard and plane-wave electronic structure models with $N < 10^5$ fermionic modes can be performed with roughly $O(1)$ and $O(N^2)$ T complexities. We perform numerics revealing tradeoffs between the error and gate complexity of a Trotter step; e.g., we show that split-operator techniques have less Trotter error than popular alternatives. By compiling to surface code fault-tolerant gates and assuming error rates of one part per thousand, we show that one can error-correct quantum simulations of interesting, classically intractable instances with a few hundred thousand physical qubits.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Pattern recognition techniques for Boson Sampling validation

The difficulty of validating large-scale quantum devices, such as Boson Samplers, poses a major challenge for any research program that aims to show quantum advantages over classical hardware. To address this problem, we propose a novel data-driven approach wherein models are trained to identify common pathologies using unsupervised machine learning methods. We illustrate this idea by training a classifier that exploits K-means clustering to distinguish between Boson Samplers that use indistinguishable photons from those that do not. We train the model on numerical simulations of small-scale Boson Samplers and then validate the pattern recognition technique on larger numerical simulations as well as on photonic chips in both traditional Boson Sampling and scattershot experiments. The effectiveness of such method relies on particle-type-dependent internal correlations present in the output distributions. This approach performs substantially better on the test data than previous methods and underscores the ability to further generalize its operation beyond the scope of the examples that it was trained on.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Quantum Algorithms for Simulating the Lattice Schwinger Model

The Schwinger model (quantum electrodynamics in 1+1 dimensions) is a testbed for the study of quantum gauge field theories. We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In particular, we perform a tight analysis of low-order Trotter formula simulations of the Schwinger model, using recently derived commutator bounds, and give upper bounds on the resources needed for simulations in both scenarios. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x^{-1/2}$ and electric field cutoff $x^{-1/2}Λ$ can be simulated on a quantum computer for time $2xT$ using a number of $T$-gates or CNOTs in $\widetilde{O}( N^{3/2} T^{3/2} \sqrt{x} Λ)$ for fixed operator error. This scaling with the truncation $Λ$ is better than that expected from algorithms such as qubitization or QDRIFT. Furthermore, we give scalable measurement schemes and algorithms to estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density. Finally, we bound the root-mean-square error in estimating this observable via simulation as a function of the diamond distance between the ideal and actual CNOT channels. This work provides a rigorous analysis of simulating the Schwinger model, while also providing benchmarks against which subsequent simulation algorithms can be tested.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Time-dependent Hamiltonian simulation with $L^1$-norm scaling

The difficulty of simulating quantum dynamics depends on the norm of the Hamiltonian. When the Hamiltonian varies with time, the simulation complexity should only depend on this quantity instantaneously. We develop quantum simulation algorithms that exploit this intuition. For sparse Hamiltonian simulation, the gate complexity scales with the $L^1$ norm $\int_{0}^{t}\mathrm{d}τ\left\lVert H(τ)\right\lVert_{\max}$, whereas the best previous results scale with $t\max_{τ\in[0,t]}\left\lVert H(τ)\right\lVert_{\max}$. We also show analogous results for Hamiltonians that are linear combinations of unitaries. Our approaches thus provide an improvement over previous simulation algorithms that can be substantial when the Hamiltonian varies significantly. We introduce two new techniques: a classical sampler of time-dependent Hamiltonians and a rescaling principle for the Schrödinger equation. The rescaled Dyson-series algorithm is nearly optimal with respect to all parameters of interest, whereas the sampling-based approach is easier to realize for near-term simulation. These algorithms could potentially be applied to semi-classical simulations of scattering processes in quantum chemistry.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Ordering of Trotterization: Impact on Errors in Quantum Simulation of Electronic Structure

Trotter-Suzuki decompositions are frequently used in the quantum simulation of quantum chemistry. They transform the evolution operator into a form implementable on a quantum device, while incurring an error---the Trotter error. The Trotter error can be made arbitrarily small by increasing the Trotter number. However, this increases the length of the quantum circuits required, which may be impractical. It is therefore desirable to find methods of reducing the Trotter error through alternate means. The Trotter error is dependent on the order in which individual term unitaries are applied. Due to the factorial growth in the number of possible orderings with respect to the number of terms, finding an optimal strategy for ordering Trotter sequences is difficult. In this paper, we propose three ordering strategies, and assess their impact on the Trotter error incurred. Initially, we exhaustively examine the possible orderings for molecular hydrogen in a STO-3G basis. We demonstrate how the optimal ordering scheme depends on the compatibility graph of the Hamiltonian, and show how it varies with increasing bond length. We then use 44 molecular Hamiltonians to evaluate two strategies based on coloring their incompatibility graphs, while considering the properties of the obtained colorings. We find that the Trotter error for most systems involving heavy atoms, using a reference magnitude ordering, is less than 1 kcal/mol. Relative to this, the difference between ordering schemes can be substantial, being approximately on the order of millihartrees. The coloring-based ordering schemes are reasonably promising, however further work is required. Finally, we consider ordering strategies based on the norm of the Trotter error operator, including an iterative method for generating the new error operator terms added upon insertion of a term into an ordered Hamiltonian.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Circuit-centric quantum classifiers

The current generation of quantum computing technologies call for quantum algorithms that require a limited number of qubits and quantum gates, and which are robust against errors. A suitable design approach are variational circuits where the parameters of gates are learnt, an approach that is particularly fruitful for applications in machine learning. In this paper, we propose a low-depth variational quantum algorithm for supervised learning. The input feature vectors are encoded into the amplitudes of a quantum system, and a quantum circuit of parametrised single and two-qubit gates together with a single-qubit measurement is used to classify the inputs. This circuit architecture ensures that the number of learnable parameters is poly-logarithmic in the input dimension. We propose a quantum-classical training scheme where the analytical gradients of the model can be estimated by running several slightly adapted versions of the variational circuit. We show with simulations that the circuit-centric quantum classifier performs well on standard classical benchmark datasets while requiring dramatically fewer parameters than other methods. We also evaluate sensitivity of the classification to state preparation and parameter noise, introduce a quantum version of dropout regularisation and provide a graphical representation of quantum gates as highly symmetric linear layers of a neural network.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

Quantum computing is powerful because unitary operators describing the time-evolution of a quantum system have exponential size in terms of the number of qubits present in the system. We develop a new "Singular value transformation" algorithm capable of harnessing this exponential advantage, that can apply polynomial transformations to the singular values of a block of a unitary, generalizing the optimal Hamiltonian simulation results of Low and Chuang. The proposed quantum circuits have a very simple structure, often give rise to optimal algorithms and have appealing constant factors, while usually only use a constant number of ancilla qubits. We show that singular value transformation leads to novel algorithms. We give an efficient solution to a certain "non-commutative" measurement problem and propose a new method for singular value estimation. We also show how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum. Finally, as a quantum machine learning application we show how to efficiently implement principal component regression. "Singular value transformation" is conceptually simple and efficient, and leads to a unified framework of quantum algorithms incorporating a variety of quantum speed-ups. We illustrate this by showing how it generalizes a number of prominent quantum algorithms, including: optimal Hamiltonian simulation, implementing the Moore-Penrose pseudoinverse with exponential precision, fixed-point amplitude amplification, robust oblivious amplitude amplification, fast QMA amplification, fast quantum OR lemma, certain quantum walk results and several quantum machine learning algorithms. In order to exploit the strengths of the presented method it is useful to know its limitations too, therefore we also prove a lower bound on the efficiency of singular value transformation, which often gives optimal bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Design Automation and Design Space Exploration for Quantum Computers

A major hurdle to the deployment of quantum linear systems algorithms and recent quantum simulation algorithms lies in the difficulty to find inexpensive reversible circuits for arithmetic using existing hand coded methods. Motivated by recent advances in reversible logic synthesis, we synthesize arithmetic circuits using classical design automation flows and tools. The combination of classical and reversible logic synthesis enables the automatic design of large components in reversible logic starting from well-known hardware description languages such as Verilog. As a prototype example for our approach we automatically generate high quality networks for the reciprocal $1/x$, which is necessary for quantum linear systems algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Quantum Perceptron Models

We demonstrate how quantum computation can provide non-trivial improvements in the computational and statistical complexity of the perceptron model. We develop two quantum algorithms for perceptron learning. The first algorithm exploits quantum information processing to determine a separating hyperplane using a number of steps sublinear in the number of data points $N$, namely $O(\sqrt{N})$. The second algorithm illustrates how the classical mistake bound of $O(\frac{1}{γ^2})$ can be further improved to $O(\frac{1}{\sqrtγ})$ through quantum means, where $γ$ denotes the margin. Such improvements are achieved through the application of quantum amplitude amplification to the version space interpretation of the perceptron model.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Randomized gap and amplitude estimation

We provide a method for estimating spectral gaps in low-dimensional systems. Unlike traditional phase estimation, our approach does not require ancillary qubits nor does it require well characterised gates. Instead, it only requires the ability to perform approximate Haar-random unitary operations, applying the unitary whose eigenspectrum is sought out and performing measurements in the computational basis. We discuss application of these ideas to in-place amplitude estimation and quantum device calibration.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Bayesian inference via rejection filtering

We provide a method for approximating Bayesian inference using rejection sampling. We not only make the process efficient, but also dramatically reduce the memory required relative to conventional methods by combining rejection sampling with particle filtering. We also provide an approximate form of rejection sampling that makes rejection filtering tractable in cases where exact rejection sampling is not efficient. Finally, we present several numerical examples of rejection filtering that show its ability to track time dependent parameters in online settings and also benchmark its performance on MNIST classification problems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Can small quantum systems learn?

We examine the question of whether quantum mechanics places limitations on the ability of small quantum devices to learn. We specifically examine the question in the context of Bayesian inference, wherein the prior and posterior distributions are encoded in the quantum state vector. We conclude based on lower bounds from Grover's search that an efficient blackbox method for updating the distribution is impossible. We then address this by providing a new adaptive form of approximate quantum Bayesian inference that is polynomially faster than its classical analogue and tractable if the quantum system is augmented with classical memory or if the low-order moments of the distribution are protected using a repetition code. This work suggests that there may be a connection between fault tolerance and the capacity of a quantum system to learn from its surroundings.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation

Although the simulation of quantum chemistry is one of the most anticipated applications of quantum computing, the scaling of known upper bounds on the complexity of these algorithms is daunting. Prior work has bounded errors due to Trotterization in terms of the norm of the error operator and analyzed scaling with respect to the number of spin-orbitals. However, we find that these error bounds can be loose by up to sixteen orders of magnitude for some molecules. Furthermore, numerical results for small systems fail to reveal any clear correlation between ground state error and number of spin-orbitals. We instead argue that chemical properties, such as the maximum nuclear charge in a molecule and the filling fraction of orbitals, can be decisive for determining the cost of a quantum simulation. Our analysis motivates several strategies to use classical processing to further reduce the required Trotter step size and to estimate the necessary number of steps, without requiring additional quantum resources. Finally, we demonstrate improved methods for state preparation techniques which are asymptotically superior to proposals in the simulation literature.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Efficient Bayesian Phase Estimation

We provide a new efficient adaptive algorithm for performing phase estimation that does not require that the user infer the bits of the eigenphase in reverse order; rather it directly infers the phase and estimates the uncertainty in the phase directly from experimental data. Our method is highly flexible, recovers from failures, and can be run in the presence of substantial decoherence and other experimental imperfections and is as fast or faster than existing algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Partial Reinitialisation for Optimisers

Heuristic optimisers which search for an optimal configuration of variables relative to an objective function often get stuck in local optima where the algorithm is unable to find further improvement. The standard approach to circumvent this problem involves periodically restarting the algorithm from random initial configurations when no further improvement can be found. We propose a method of partial reinitialization, whereby, in an attempt to find a better solution, only sub-sets of variables are re-initialised rather than the whole configuration. Much of the information gained from previous runs is hence retained. This leads to significant improvements in the quality of the solution found in a given time for a variety of optimisation problems in machine learning.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Quantum Bootstrapping via Compressed Quantum Hamiltonian Learning

Recent work has shown that quantum simulation is a valuable tool for learning empirical models for quantum systems. We build upon these results by showing that a small quantum simulators can be used to characterize and learn control models for larger devices for wide classes of physically realistic Hamiltonians. This leads to a new application for small quantum computers: characterizing and controlling larger quantum computers. Our protocol achieves this by using Bayesian inference in concert with Lieb-Robinson bounds and interactive quantum learning methods to achieve compressed simulations for characterization. Whereas Fisher information analysis shows that current methods which employ short-time evolution are suboptimal, interactive quantum learning allows us to overcome this limitation. We illustrate the efficiency of our bootstrapping protocol by showing numerically that an 8-qubit Ising model simulator can be used to calibrate and control a 50 qubit Ising simulator while using only about 750 kilobits of experimental data.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Quantum Deep Learning

In recent years, deep learning has had a profound impact on machine learning and artificial intelligence. At the same time, algorithms for quantum computers have been shown to efficiently solve some problems that are intractable on conventional, classical computers. We show that quantum computing not only reduces the time required to train a deep restricted Boltzmann machine, but also provides a richer and more comprehensive framework for deep learning than classical computing and leads to significant improvements in the optimization of the underlying objective function. Our quantum methods also permit efficient training of full Boltzmann machines and multi-layer, fully connected models and do not have well known classical counterparts.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Quantum Inspired Training for Boltzmann Machines

We present an efficient classical algorithm for training deep Boltzmann machines (DBMs) that uses rejection sampling in concert with variational approximations to estimate the gradients of the training objective function. Our algorithm is inspired by a recent quantum algorithm for training DBMs. We obtain rigorous bounds on the errors in the approximate gradients; in turn, we find that choosing the instrumental distribution to minimize the alpha=2 divergence with the Gibbs state minimizes the asymptotic algorithmic complexity. Our rejection sampling approach can yield more accurate gradients than low-order contrastive divergence training and the costs incurred in finding increasingly accurate gradients can be easily parallelized. Finally our algorithm can train full Boltzmann machines and scales more favorably with the number of layers in a DBM than greedy contrastive divergence training.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Solving strongly correlated electron models on a quantum computer

One of the main applications of future quantum computers will be the simulation of quantum models. While the evolution of a quantum state under a Hamiltonian is straightforward (if sometimes expensive), using quantum computers to determine the ground state phase diagram of a quantum model and the properties of its phases is more involved. Using the Hubbard model as a prototypical example, we here show all the steps necessary to determine its phase diagram and ground state properties on a quantum computer. In particular, we discuss strategies for efficiently determining and preparing the ground state of the Hubbard model starting from various mean-field states with broken symmetry. We present an efficient procedure to prepare arbitrary Slater determinants as initial states and present the complete set of quantum circuits needed to evolve from these to the ground state of the Hubbard model. We show that, using efficient nesting of the various terms each time step in the evolution can be performed with just $\mathcal{O}(N)$ gates and $\mathcal{O}(\log N)$ circuit depth. We give explicit circuits to measure arbitrary local observables and static and dynamic correlation functions, both in the time and frequency domain. We further present efficient non-destructive approaches to measurement that avoid the need to re-prepare the ground state after each measurement and that quadratically reduce the measurement error.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On The Power Of Coherently Controlled Quantum Adiabatic Evolutions

A major challenge facing adiabatic quantum computing is that algorithm design and error correction can be difficult for adiabatic quantum computing. Recent work has considered addressing his challenge by using coherently controlled adiabatic evolutions in the place of classically controlled evolution. An important question remains: what is the relative power of controlled adiabatic evolution to traditional adiabatic evolutions? We address this by showing that coherent control and measurement provides a way to average different adiabatic evolutions in ways that cause their diabatic errors to cancel, allowing for adiabatic evolutions to combine the best characteristics of existing adiabatic optimizations strategies that are mutually exclusive in conventional adiabatic QIP. This result shows that coherent control and measurement can provide advantages for adiabatic state preparation. We also provide upper bounds on the complexity of simulating such evolutions on a circuit based quantum computer and provide sufficiency conditions for the equivalence of controlled adiabatic evolutions to adiabatic quantum computing.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Quantum Algorithms for Nearest-Neighbor Methods for Supervised and Unsupervised Learning

We present several quantum algorithms for performing nearest-neighbor learning. At the core of our algorithms are fast and coherent quantum methods for computing distance metrics such as the inner product and Euclidean distance. We prove upper bounds on the number of queries to the input data required to compute these metrics. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to the corresponding classical algorithm. In certain cases, we show exponential or even super-exponential reductions over the classical analog. We study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Quantum arithmetic and numerical analysis using Repeat-Until-Success circuits

We develop a method for approximate synthesis of single--qubit rotations of the form $e^{-i f(ϕ_1,\ldots,ϕ_k)X}$ that is based on the Repeat-Until-Success (RUS) framework for quantum circuit synthesis. We demonstrate how smooth computable functions $f$ can be synthesized from two basic primitives. This synthesis approach constitutes a manifestly quantum form of arithmetic that differs greatly from the approaches commonly used in quantum algorithms. The key advantage of our approach is that it requires far fewer qubits than existing approaches: as a case in point, we show that using as few as $3$ ancilla qubits, one can obtain RUS circuits for approximate multiplication and reciprocals. We also analyze the costs of performing multiplication and inversion on a quantum computer using conventional approaches and find that they can require too many qubits to execute on a small quantum computer, unlike our approach.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Quantum Hamiltonian Learning Using Imperfect Quantum Resources

Identifying an accurate model for the dynamics of a quantum system is a vexing problem that underlies a range of problems in experimental physics and quantum information theory. Recently, a method called quantum Hamiltonian learning has been proposed by the present authors that uses quantum simulation as a resource for modeling an unknown quantum system. This approach can, under certain circumstances, allow such models to be efficiently identified. A major caveat of that work is the assumption of that all elements of the protocol are noise-free. Here, we show that quantum Hamiltonian learning can tolerate substantial amounts of depolarizing noise and show numerical evidence that it can tolerate noise drawn from other realistic models. We further provide evidence that the learning algorithm will find a model that is maximally close to the true model in cases where the hypothetical model lacks terms present in the true model. Finally, we also provide numerical evidence that the algorithm works for non-commuting models. This work illustrates that quantum Hamiltonian learning can be performed using realistic resources and suggests that even imperfect quantum resources may be valuable for characterizing quantum systems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Trotter Step Size Required for Accurate Quantum Simulation of Quantum Chemistry

The simulation of molecules is a widely anticipated application of quantum computers. However, recent studies \cite{WBCH13a,HWBT14a} have cast a shadow on this hope by revealing that the complexity in gate count of such simulations increases with the number of spin orbitals $N$ as $N^8$, which becomes prohibitive even for molecules of modest size $N\sim 100$. This study was partly based on a scaling analysis of the Trotter step required for an ensemble of random artificial molecules. Here, we revisit this analysis and find instead that the scaling is closer to $N^6$ in worst case for real model molecules we have studied, indicating that the random ensemble fails to accurately capture the statistical properties of real-world molecules. Actual scaling may be significantly better than this due to averaging effects. We then present an alternative simulation scheme and show that it can sometimes outperform existing schemes, but that this possibility depends crucially on the details of the simulated molecule. We obtain further improvements using a version of the coalescing scheme of \cite{WBCH13a}; this scheme is based on using different Trotter steps for different terms. The method we use to bound the complexity of simulating a given molecule is efficient, in contrast to the approach of \cite{WBCH13a,HWBT14a} which relied on exponentially costly classical exact simulation.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Using Quantum Computers to Learn Physics

Since its inception at the beginning of the twentieth century, quantum mechanics has challenged our conceptions of how the universe ought to work; however, the equations of quantum mechanics can be too computationally difficult to solve using existing computers for even modestly large systems. Here I will show that quantum computers can sometimes be used to address such problems and that quantum computer science can assign formal complexities to learning facts about nature. Hence, computer science should not only be regarded as an applied science; it is also of central importance to the foundations of science.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Floating Point Representations in Quantum Circuit Synthesis

We provide a non-deterministic quantum protocol that approximates the single qubit rotations R_x(2a^2 b^2)$ using R_x(2a) and R_x(2b) and a constant number of Clifford and T operations. We then use this method to construct a "floating point" implementation of a small rotation wherein we use the aforementioned method to construct the exponent part of the rotation and also to combine it with a mantissa. This causes the cost of the synthesis to depend more strongly on the relative (rather than absolute) precision required. We analyze the mean and variance of the \Tcount required to use our techniques and provide new lower bounds for the T-count for ancilla free synthesis of small single-qubit axial rotations. We further show that our techniques can use ancillas to beat these lower bounds with high probability. We also discuss the T-depth of our method and see that the vast majority of the cost of the resultant circuits can be shifted to parallel computation paths.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Hamiltonian Learning and Certification Using Quantum Resources

In recent years quantum simulation has made great strides culminating in experiments that operate in a regime that existing supercomputers cannot easily simulate. Although this raises the possibility that special purpose analog quantum simulators may be able to perform computational tasks that existing computers cannot, it also introduces a major challenge: certifying that the quantum simulator is in fact simulating the correct quantum dynamics. We provide an algorithm that, under relatively weak assumptions, can be used to efficiently infer the Hamiltonian of a large but untrusted quantum simulator using a trusted quantum simulator. We illustrate the power of this approach by showing numerically that it can inexpensively learn the Hamiltonians for large frustrated Ising models, demonstrating that quantum resources can make certifying analog quantum simulators tractable.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Information-theoretic equilibration: the appearance of irreversibility under complex quantum dynamics

The question of how irreversibility can emerge as a generic phenomena when the underlying mechanical theory is reversible has been a long-standing fundamental problem for both classical and quantum mechanics. We describe a mechanism for the appearance of irreversibility that applies to coherent, isolated systems in a pure quantum state. This equilibration mechanism requires only an assumption of sufficiently complex internal dynamics and natural information-theoretic constraints arising from the infeasibility of collecting an astronomical amount of measurement data. Remarkably, we are able to prove that irreversibility can be understood as typical without assuming decoherence or restricting to coarse-grained observables, and hence occurs under distinct conditions and time-scales than those implied by the usual decoherence point of view. We illustrate the effect numerically in several model systems and prove that the effect is typical under the standard random-matrix conjecture for complex quantum systems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Product Formulas for Exponentials of Commutators

We provide a recursive method for constructing product formula approximations to exponentials of commutators, giving the first approximations that are accurate to arbitrarily high order. Using these formulas, we show how to approximate unitary exponentials of (possibly nested) commutators using exponentials of the elementary operators, and we upper bound the number of elementary exponentials needed to implement the desired operation within a given error tolerance. By presenting an algorithm for quantum search using evolution according to a commutator, we show that the scaling of the number of exponentials in our product formulas with the evolution time is nearly optimal. Finally, we discuss applications of our product formulas to quantum control and to implementing anticommutators, providing new methods for simulating many-body interaction Hamiltonians.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation

We provide a scheme for efficient simulation of a broad class of quantum optics experiments. Our efficient simulation extends the continuous variable Gottesman-Knill theorem to a large class of non-Gaussian mixed states, thereby identifying that these non-Gaussian states are not an enabling resource for exponential quantum speed-up. Our results also provide an operationally motivated interpretation of negativity as non-classicality. We apply our scheme to the case of noisy single-photon-added-thermal-states to show that this class admits states with positive Wigner function but negative P -function that are not useful resource states for quantum computation.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Quantum Data Fitting

We provide a new quantum algorithm that efficiently determines the quality of a least-squares fit over an exponentially large data set by building upon an algorithm for solving systems of linear equations efficiently (Harrow et al., Phys. Rev. Lett. {\bf 103}, 150502 (2009)). In many cases, our algorithm can also efficiently find a concise function that approximates the data to be fitted and bound the approximation error. In cases where the input data is a pure quantum state, the algorithm can be used to provide an efficient parametric estimation of the quantum state and therefore can be applied as an alternative to full quantum state tomography given a fault tolerant quantum computer.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Quantum-circuit design for efficient simulations of many-body quantum dynamics

We construct an efficient autonomous quantum-circuit design algorithm for creating efficient quantum circuits to simulate Hamiltonian many-body quantum dynamics for arbitrary input states. The resultant quantum circuits have optimal space complexity and employ a sequence of gates that is close to optimal with respect to time complexity. We also devise an algorithm that exploits commutativity to optimize the circuits for parallel execution. As examples, we show how our autonomous algorithm constructs circuits for simulating the dynamics of Kitaev's honeycomb model and the Bardeen-Cooper-Schrieffer model of superconductivity. Furthermore we provide numerical evidence that the rigorously proven upper bounds for the simulation error here and in previous work may sometimes overestimate the error by orders of magnitude compared to the best achievable performance for some physics-inspired simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Robust Online Hamiltonian Learning

In this work we combine two distinct machine learning methodologies, sequential Monte Carlo and Bayesian experimental design, and apply them to the problem of inferring the dynamical parameters of a quantum system. We design the algorithm with practicality in mind by including parameters that control trade-offs between the requirements on computational and experimental resources. The algorithm can be implemented online (during experimental data collection), avoiding the need for storage and post-processing. Most importantly, our algorithm is capable of learning Hamiltonian parameters even when the parameters change from experiment-to-experiment, and also when additional noise processes are present and unknown. The algorithm also numerically estimates the Cramer-Rao lower bound, certifying its own performance.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Improved Error Bounds for the Adiabatic Approximation

Since the discovery of adiabatic quantum computing, a need has arisen for rigorously proven bounds for the error in the adiabatic approximation. We present in this paper, a rigorous and elementary derivation of upper and lower bounds on the error incurred from using the adiabatic approximation for quantum systems. Our bounds are often asymptotically tight in the limit of slow evolution for fixed Hamiltonians, and are used to provide sufficient conditions for the application of the adiabatic approximation. We show that our sufficiency criteria exclude the Marzlin--Sanders counterexample from the class of Hamiltonians that obey the adiabatic approximation. Finally, we demonstrate the existence of classes of Hamiltonians that resemble the Marzlin--Sanders counterexample Hamiltonian, but also obey the adiabatic approximation.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Improved Error-Scaling for Adiabatic Quantum State Transfer

We present a technique that dramatically improves the accuracy of adiabatic state transfer for a broad class of realistic Hamiltonians. For some systems, the total error scaling can be quadratically reduced at a fixed maximum transfer rate. These improvements rely only on the judicious choice of the total evolution time. Our technique is error-robust, and hence applicable to existing experiments utilizing adiabatic passage. We give two examples as proofs-of-principle, showing quadratic error reductions for an adiabatic search algorithm and a tunable two-qubit quantum logic gate.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Simulating Quantum Dynamics On A Quantum Computer

We present efficient quantum algorithms for simulating time-dependent Hamiltonian evolution of general input states using an oracular model of a quantum computer. Our algorithms use either constant or adaptively chosen time steps and are significant because they are the first to have time-complexities that are comparable to the best known methods for simulating time-independent Hamiltonian evolution, given appropriate smoothness criteria on the Hamiltonian are satisfied. We provide a thorough cost analysis of these algorithms that considers discretizion errors in both the time and the representation of the Hamiltonian. In addition, we provide the first upper bounds for the error in Lie-Trotter-Suzuki approximations to unitary evolution operators, that use adaptively chosen time steps.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Higher Order Decompositions of Ordered Operator Exponentials

We present a decomposition scheme based on Lie-Trotter-Suzuki product formulae to represent an ordered operator exponential as a product of ordinary operator exponentials. We provide a rigorous proof that does not use a time-displacement superoperator, and can be applied to non-analytic functions. Our proof provides explicit bounds on the error and includes cases where the functions are not infinitely differentiable. We show that Lie-Trotter-Suzuki product formulae can still be used for functions that are not infinitely differentiable, but that arbitrary order scaling may not be achieved.

0 citations0 reviewsNo code linkedOpen access