One obstacle in the simulation of quantum circuits is the high dimension of the Hilbert space. Using auxiliary field decompositions known from many-particle simulation, we can transform the mathematical description of the quantum circuit into a combination low-dimensional product states which can be sampled using Monte Carlo techniques. We demonstrate the method using Simon's algorithm for the detection of the period of a function.
One obstacle in the simulation of quantum circuits is the high dimension of the Hilbert space. Using auxiliary field decompositions known from many-particle simulation, we can transform the mathematical description of the quantum circuit into a combination low-dimensional product states which can be sampled using Monte Carlo techniques. We demonstrate the method using Simon's algorithm for the detection of the period of a function.
Quantum computing is arguably one of the most revolutionary and disruptive technologies of this century. Due to the ever-increasing number of potential applications as well as the continuing rise in complexity, the development, simulation, optimization, and physical realization of quantum circuits is of utmost importance for designing novel algorithms. We show how matrix product states (MPSs) and matrix product operators (MPOs) can be used to express certain quantum states, quantum gates, and entire quantum circuits as low-rank tensors. This enables the analysis and simulation of complex quantum circuits on classical computers and to gain insight into the underlying structure of the system. We present different examples to demonstrate the advantages of MPO formulations and show that they are more efficient than conventional techniques if the bond dimensions of the wave function representation can be kept small throughout the simulation.
We propose an approximate classical algorithm for estimating quantum circuits' transition amplitudes, ⟨Ψf∣U^∣Ψ0⟩, based on Monte Carlo sums over bidirectionally sampled Feynman paths. The algorithm generates Feynman paths, i.e., sequences of intermediate computational basis states, by combining information from random walks initiated at both the input and output states, Ψ0 and Ψf, respectively. It further combines this bidirectional approach with Multiple Importance Sampling, a powerful variance reduction technique that avoids variance peaks caused by divisions by the very low sampling probabilities associated with hard to reach paths. Empirical data demonstrate the superior convergence rate exhibited by the bidirectional algorithm over a unidirectional, forward-only sampling approach. This superiority is due to the effectiveness of the proposed algorithm in finding and weighting paths with non-zero amplitude in an extremely sparse path space. Sum of paths algorithms exhibit very favourable space complexity. Monte Carlo replaces exhaustive enumeration of the exponentially large path space by stochastic sampling, the computational cost being determined by the variance of the estimator. This work demonstrates these two features by presenting results on very large quantum circuits, with up to 4096 qubits.
We propose an approximate classical algorithm for estimating quantum circuits' transition amplitudes, ⟨Ψf∣U^∣Ψ0⟩, based on Monte Carlo sums over bidirectionally sampled Feynman paths. The algorithm generates Feynman paths, i.e., sequences of intermediate computational basis states, by combining information from random walks initiated at both the input and output states, Ψ0 and Ψf, respectively. It further combines this bidirectional approach with Multiple Importance Sampling, a powerful variance reduction technique that avoids variance peaks caused by divisions by the very low sampling probabilities associated with hard to reach paths. Empirical data demonstrate the superior convergence rate exhibited by the bidirectional algorithm over a unidirectional, forward-only sampling approach. This superiority is due to the effectiveness of the proposed algorithm in finding and weighting paths with non-zero amplitude in an extremely sparse path space. Sum of paths algorithms exhibit very favourable space complexity. Monte Carlo replaces exhaustive enumeration of the exponentially large path space by stochastic sampling, the computational cost being determined by the variance of the estimator. This work demonstrates these two features by presenting results on very large quantum circuits, with up to 4096 qubits.
Abstract This paper describes a different Q11C method for solving the Schrödinger equation, one unlike variational, diffusion, and Green’s function methods. It can be applied to many-body systems to produce solutions for ground states. For systems of fermions, antisymmetrization can be imposed to overcome the problem of node location, but the instability of the method is a serious shortcoming, so that the method as described is limited to treating relatively simple systems. Nevertheless, this auxiliary field quantum 1,fonte Carlo (AFMC) method was demonstrated to be successful for test cases reported in this paper, and in time has been improved to allow treatment of realistic systemsa. The method makes use of the imaginary-time propagation of an initial wavefunction toward the ground-state function. It requires use of a trial wavefunction which is the product of single-particle orbitals for bosons or an antisymmetrized product for fermions. A Hubbard-Stratonovich transformation of the propagator changes the many-body problem to a problem of a collection of single particles interacting with a fluctuating (auxiliary) field which replaces the many-body interactions. The authors developed an integral expression for the energy which, after discretization, could be evaluated by a Metropolis Monte Carlo integration forward in time. The algorithm was tested for one-dimensional systems of particles: 6 to 20 bosons with varied interactions, 2 to 6 neutron-proton pairs, others with repulsive potentials. Importance sampling was found to be critical and computational requirements to be large. For spin systems on a lattice the AFMC method was considered feasible, but for general multidimensional systems the method appeared to be limited by its computation requirements.
These notes begin in Chapter 1 with a review of linear algebra and the postulates of quantum mechanics, leading to an explanation of single- and multi-qubit gates. Chapter 2 explores the challenge of constructing arbitrary quantum states from given initial states, and introduces circuits for building oracles. Chapter 3 presents foundational algorithms such as entanglement creation, quantum teleportation, Deutsch-Jozsa, Bernstein-Vazirani, and Simon's algorithm. Chapters 4 and 5 cover algorithms based on the quantum Fourier transform, including phase estimation, period finding, factoring, and logarithm computation. These chapters also include complexity analysis and detailed quantum circuits suitable for implementation in code. Chapter 6 introduces Grover's algorithm for quantum search and amplitude amplification, including its realization via Hamiltonian simulation and a method for derandomization. Chapter 7 discusses basic techniques for Hamiltonian simulation, such as Lie-Trotter decomposition, sparse Hamiltonians, and the linear combination of unitaries. It also provides example circuits for simulating Hamiltonians expressed as linear combinations of Pauli operators. Chapter 8 introduces variational quantum algorithms, and Chapter 9 presents an algorithm for simulating fermionic many-particle systems, with an emphasis on molecular Hamiltonians. It also outlines the key transformations needed to map a molecular Hamiltonian to a form suitable for simulation on a quantum computer.