Within the last several years quantum machine learning (QML) has begun to mature; however, many open questions remain. Rather than review open questions, in this perspective piece I will discuss my ...view about how we should approach problems in QML. In particular I will list a series of questions that I think we should ask ourselves when developing quantum algorithms for machine learning. These questions focus on what the definition of quantum ML is, what is the proper quantum analogue of QML algorithms is, how one should compare QML to traditional ML and what fundamental limitations emerge when trying to build QML protocols. As an illustration of this process I also provide information theoretic arguments that show that amplitude encoding can require exponentially more queries to a quantum model to determine membership of a vector in a concept class than classical bit-encodings would require; however, if the correct analogue is chosen then both the quantum and classical complexities become polynomially equivalent. This example underscores the importance of asking ourselves the right questions when developing and benchmarking QML algorithms.
Elucidating reaction mechanisms on quantum computers Reiher, Markus; Wiebe, Nathan; Svore, Krysta M. ...
Proceedings of the National Academy of Sciences - PNAS,
07/2017, Letnik:
114, Številka:
29
Journal Article
Recenzirano
Odprti dostop
With rapid recent advances in quantum technology, we are close to the threshold of quantum devices whose computational powers can exceed those of classical supercomputers. Here, we show that a ...quantum computer can be used to elucidate reaction mechanisms in complex chemical systems, using the open problem of biological nitrogen fixation in nitrogenase as an example. We discuss how quantum computers can augment classical computer simulations used to probe these reaction mechanisms, to significantly increase their accuracy and enable hitherto intractable simulations. Our resource estimates show that, even when taking into account the substantial overhead of quantum error correction, and the need to compile into discrete gate sets, the necessary computations can be performed in reasonable time on small quantum computers. Our results demonstrate that quantum computers will be able to tackle important problems in chemistry without requiring exorbitant resources.
An n-qubit quantum circuit performs a unitary operation on an exponentially large, 2n-dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular ...value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to various quantum machine learning applications. We also devise a new singular vector transformation algorithm, describe how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and show how to efficiently implement principal component regression. Finally, we also prove a quantum lower bound on spectral transformations.
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 by-product. 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 it is close to tight for power-law interactions and other orderings of terms. This result suggests that our theory can accurately characterize Trotter error in terms of both asymptotic scaling and constant prefactor.
We argue that an excess in entanglement between the visible and hidden units in a quantum neural network can hinder learning. In particular, we show that quantum neural networks that satisfy a volume ...law in the entanglement entropy will give rise to models that are not suitable for learning with high probability. Using arguments from quantum thermodynamics, we then show that this volume law is typical and that there exists a barren plateau in the optimization landscape due to entanglement. More precisely, we show that for any bounded objective function on the visible layers, the Lipshitz constants of the expectation value of that objective function will scale inversely with the dimension of the hidden subsystem with high probability. We show how this can cause both gradient-descent and gradient-free methods to fail. We note that similar problems can happen with quantum Boltzmann machines, although stronger assumptions on the coupling between the hidden and/or visible subspaces are necessary. We highlight how pretraining such generative models may provide a way to navigate these barren plateaus.
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
2
x
T
using a number of
T
-gates or CNOTs in
O
~
(
N
3
/
2
T
3
/
2
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.
Quantum simulation of the electronic structure problem is one of the most researched applications of quantum computing. The majority of quantum algorithms for this problem encode the wavefunction ...usingNGaussian orbitals, leading to Hamiltonians withO(N4)second-quantized terms. We avoid this overhead and extend methods to condensed phase materials by utilizing a dual form of the plane wave basis which diagonalizes the potential operator, leading to a Hamiltonian representation withO(N2)second-quantized terms. Using this representation, we can implement single Trotter steps of the Hamiltonians with linear gate depth on a planar lattice. Properties of the basis allow us to deploy Trotter- and Taylor-series-based simulations with respective circuit depths ofO(N7/2)andO˜(N8/3)for fixed charge densities. Variational algorithms also require significantly fewer measurements in this basis, ameliorating a primary challenge of that approach. While our approach applies to the simulation of arbitrary electronic structure problems, the basis sets explored in this work will be most practical for treating periodic systems, such as crystalline materials, in the near term. We conclude with a proposal to simulate the uniform electron gas (jellium) using a low-depth variational ansatz realizable on near-term quantum devices. From these results, we identify simulations of low-density jellium as a promising first setting to explore quantum supremacy in electronic structure.
We construct quantum circuits that exactly encode the spectra of correlated electron models up to errors from rotation synthesis. By invoking these circuits as oracles within the recently introduced ...“qubitization” framework, one can use quantum phase estimation to sample states in the Hamiltonian eigenbasis with optimal query complexityO(λ/ε), whereλis an absolute sum of Hamiltonian coefficients andεis the target precision. For both the Hubbard model and electronic structure Hamiltonian in a second quantized basis diagonalizing the Coulomb operator, our circuits have T-gate complexityO(N+log(1/ε)), whereNis the number of orbitals in the basis. This scenario enables sampling in the eigenbasis of electronic structure Hamiltonians with T complexityO(N3/ε+N2log(1/ε)/ε). Compared to prior approaches, our algorithms are asymptotically more efficient in gate complexity and require fewer T gates near the classically intractable regime. Compiling to surface code fault-tolerant gates and assuming per-gate error rates of one part in a thousand reveals that one can error correct phase estimation on interesting instances of these problems beyond the current capabilities of classical methods using only about a million superconducting qubits in a matter of hours.
PDF
