Session F09: General Quantum Algorithms

Novel Trotter formulas for digital quantum simulation

Quantum simulation promises to address many challenges in fields ranging from quantum chemistry to material science and high-energy physics, and could be implemented in noisy intermediate scale quantum devices. A challenge in building good digital quantum simulators is the fidelity of the engineered dynamics given a finite set of elementary operations. The goal of this work is to find a proper ordering of elementary operations so that they approximate as well as possible the desired evolution. However, when the quantum system is large, even calculating one elementary operation is computationally expensive. In this talk, I will introduce a geometric framework for optimizing the order of operations without considering the details of the operations themselves, thus achieving computational efficiency. Based on the geometric framework, I will present two alternative orderings. One has optimal fidelity at a short time scale, and the other one is robust at a long time scale. Thanks to the improved fidelity at different time scales, the two different orderings can form the basis for experimental-constrained digital quantum simulation.   

Quantum Simulation of Quantum Field Theory with Qubit Models

Quantum computers are expected to outperform classical methods in the simulation of strongly-coupled quantum field theories, as they permit the calculation of dynamic quantities in real-time and avoid the notorious sign-problem. We consider a class of qubit models which can be simulated efficiently on a fault-tolerant quantum computer, and present evidence that these models possess a rich phase diagram. One of the quantum critical points in the phase diagram may help define the traditional asymptotically free O(3) non-linear sigma model. We discuss implementation of these qubit models on both NISQ and fault-tolerant quantum computers, and provide numerical results on adiabatic ground state preparation for the O(3) sigma model. This work serves as a stepping stone towards simulating non-Abelian Kogut-Susskind type gauge theories with quantum devices.   

Quantum Simulation of Nonlinear Classical Dynamics

Nonlinear classical dynamics can be simulated by a quantum computer with enough resources to approach the semiclassical limit. There is an exact embedding of a classical system of N ordinary differential equations (ODEs) within an enlarged quantum mechanical system with 2N degrees of freedom. Any set of ODEs can be derived from a classical Hamiltonian that is a sum over a set of N constraints, thereby yielding 2N equations of motion. Quantizing the constrained system leads to a Schrodinger equation that is equal to the classical Liouville equation which ensures conservation of phase space density for the original set of ODEs. Heisenberg’s uncertainty principle is satisfied by each variable and its canonically conjugate momentum, the Lagrange multiplier, on the extended phase space. Hence, there is no uncertainty in a simultaneous measurement of any of the variables of the original ODE. An appropriate choice of Planck’s constant can be used to reduce the uncertainty in the degrees of freedom of interest to a width on the order of the level spacing. Thus, excellent fidelity to the classical system can be achieved.   

Predicting Features of Quantum Systems from Very Few Measurements

Predicting features of complex, large-scale quantum systems is essential to the characterization and engineering of quantum architectures. We present an efficient approach for constructing an approximate classical description, called the classical shadow, of a quantum system from very few quantum measurements that can later be used to predict a large collection of features. This approach is guaranteed to accurately predict M observables with bounded Hilbert-Schmidt norm from only order of log(M) measurements. This is completely independent of the system size and saturates fundamental lower bounds from information theory. A distinct realization of the concept can also be used to predict M few-body observables using classical descriptions constructed from single-qubit measurements on log(M) copies of the system. These protocols have applications in variational quantum algorithms, estimating quantum fidelity, or inferring entanglement properties of the quantum system. We support our theoretical findings with numerical experiments over a wide range of problem sizes (2 to 162 qubits). These highlight advantages compared to existing machine learning approaches.   

Characterizing quantum phase transitions by the entanglement of high symmetric points: A quantum computational investigation

Quantum phase transitions play fundamental roles in our understanding of various properties of quantum materials. Therefore, how to characterize quantum phase transitions efficiently is pursued, especially for topological quantum phase transitions, which have no well-defined order parameters. Here we demonstrate that the entanglement of a small subset of a product state can be used as an indicator for quantum phase transitions. Moreover, this strategy can be easily applied with the near-term quantum computers, in which the number of qubits is highly limited. As examples, we demonstrate with IBM quantum computers for the transverse Ising and Kitaev spin model that the entanglement of product states formed by the states at the high-symmetric points of the Brillouin zone, which are subsets of the real ground state, can be used to determine different ground state phases.   

CnNOT gates for implementing random quantum walks

Quantum walks have been investigated for traversing graphs with certain oracles. This is important for building quantum routers on future quantum computers. Buliding quantum walk circuits benefit from the exponential increase in speed when compared to classical random walks. Here we invesitgated CnNOT based implementation of quantum walks along different length cycles and 2-D hypercycle. We decomposed the circuits into a set of series and parallel combinations of elementary CNOT and single qubit gates and simulated them theoretically taking into consideration the deterministic functioning of the gates. In addition, we ran a Python code simulating the same circuits on an IBM-Q supercomputer implemented with superconducting qubits. Based on the outputs, we highlight the physical constraints behind the real backend results and give numerical approximations for the errors for higher qubit number systems.   

Isolated Vertices in Continuous-Time Quantum Walks on Dynamic Graphs

It was recently shown that continuous-time quantum walks on dynamic graphs, i.e., sequences of static graphs whose edges change at specific times, can implement a universal set of quantum gates. This result treated all isolated vertices as having self-loops, so they all evolved by a phase under the quantum walk. In this paper, we permit isolated vertices to be loopless or looped, and loopless isolated vertices do not evolve at all under the quantum walk. Using this distinction, we construct simpler dynamic graphs that implement the Pauli gates and a set of universal quantum gates consisting of the Hadamard, $T$, and CNOT gates, and these gates are easily extended to multi-qubit systems. For example, the $T$ gate is simplified from a sequence of six graphs to a single graph, and the number of vertices is reduced by a factor of four. We also construct a generalized phase gate, of which $Z$, $S$, and $T$ are specific instances. Finally, we validate our implementations by numerically simulating a quantum circuit consisting of layers of one- and two-qubit gates, similar to those in recent quantum supremacy experiments, using a quantum walk.   

Enhancing Quantum Linear System Algorithm by Richardson Extrapolation

We present a complete implementation of the HHL algorithm to solve tridiagonal Toeplitz systems of linear equations of size N with Ο(log(N)log³(1/ε)+log(κ)λ_min/ε) gates, where ε is the accuracy, κ the condition number and λ_min the smallest eigenvalue, an exponential improvement in the size of the system over classical methods.
In particular, we present efficient oracles for preparing a quantum state where amplitudes are specified by a given function, Hamiltonian simulation and solution observables, and we show that the Euclidean norm of the solution can be obtained deterministically.
The main result is the use of Richardson extrapolation for general product formulae Hamiltonian simulation, resulting in an implementation of the quantum phase estimation part at polylog(1/ε) complexity instead of poly(1/ε).
For each result we provide detailed mathematical analysis that do not restrict to tridiagonal matrices, and analyze whether it is possible to obtain a quantum advantage taking into account different classes of right hand sides and quantum algorithms.
All the procedures presented are implemented with Qiskit and tested on a quantum simulator.
We demonstrate our algorithm for a small illustrative problem and two different observables on real hardware of the IBM Quantum Computing Center.   

Universality and conformal invariance in hybrid quantum circuits

We establish the emergence of conformal field theories (CFT) in (1+1)-dimensional hybrid quantum circuits right at the measurement-driven entanglement transition, by revealing the remarkable space-time conformal covariance of entanglement entropies and mutual information, computed numerically for various subregions at all time steps within Clifford circuits of up to L = 512 qubits and T = 1024 time steps. Though the evolution takes place in real-time, the time dimension of the circuit becomes “imaginary” or “space-like” – to be consistent with conformal invariance – as a result of measurements that break unitarity. Throughout the paper we investigate Clifford circuits with several different boundary conditions by injecting physical qubits at the spatial and/or temporal boundaries, all giving consistent characterizations of the “Clifford CFT”. We emphasize universal results that are consequences solely of the conformal invariance and do not depend crucially on the precise nature of the CFT. Among these are the infinite “entangling speed” as a manifestation of “many-body entanglement swapping”, and the critical decaying behavior of the thermal entropy of a mixed state at the recently discovered “purification transition”.   

Time Complexity Reduction for Gate-Model Quantum Computers

A method is defined for the time complexity reduction of near-term gate-model quantum computers. The proposed solution evaluates the reduced time complexity equivalent of a reference quantum circuit and recovers the reference output quantum system of the reference quantum circuit via quantum operations on the output of the reduced time complexity quantum circuit. We prove the complexity of the proposed quantum algorithm and the achievable reduction in time complexity. We define the auxiliary cost of the proposed quantum algorithm and show that it is significantly lower than the gainable reduction in time complexity. The algorithm provides a tractable solution to reduce both time complexity and the economic cost of implementing the physical-layer quantum computer by reducing quantum hardware elements. The results are useful for experimental gate-model quantum computations and the near-term quantum devices of the quantum Internet.   

Green's functions of molecules using a quantum computer

Given the recent rapid development of techniques for quantum computation of electronic structures[1],
we propose an algorithm for the construction of one-particle Green's function (GF) of an interacting electronic system via
statistical sampling on a quantum computer for quantum chemistry.[2]
By avoiding the difficulty coming from the non-unitarity of creation and annihilation operators for the electronic spin orbitals,
we provide quantum circuits equipped with at most two ancillary qubits for obtaining all the components of GF.
We perform simulations of such construction of GFs for LiH and H2O molecules based on the unitary coupled-cluster (UCC) method and compare the quasiparticle and satellite spectra exact within UCC and those from full configuration interaction calculations.

[1] Peruzzo et al., Nat. Comm. 5, 4213 (2014); O'Malley et el., Phys. Rev. X 6, 031007 (2016); Hempel et al., Phys. Rev. X 8, 031022 (2018)
[2] Kosugi and Matsushita, arXiv:1908.03902 (2019)   

Quantum Phase Estimation with Time-Frequency Qudits in a Single Photon

In this work, we report an experimental realization of a qudit-based PEA on a photonic platform, utilizing the high dimensionality in time and frequency degrees of freedom (DoFs) in a single photon. The controlled-unitary gates can be realized in a deterministic fashion, as the control and target registers are now represented by two DoFs in a single photon. We also proposed a systematic scheme to decompose an arbitrary unitary matrix into smaller d-level unitary matrices. Representing and connecting these d-level unitary matrices with photonic qudit gates is our plan for future research.   

Implementing single-qubit POVMs on a circuit-based quantum computer

We present a deterministic protocol to implement general single-qubit POVMs on near-term circuit-based quantum computers. The protocol has a modular structure, such that an n-element POVM is implemented as a sequence of (n-1) circuit modules. Each module performs a 2-element POVM. Two variations of the protocol are suggested, one optimal in terms of number of ancilla qubits, the other optimal in terms of number of qubit gate operations and quantum circuit depth. We use the protocol to implement $2$- and $3$-element POVMs on two publicly available quantum computing devices. The results we obtain are positive, and suggest that implementing non-trivial POVMs could be within the reach of current noisy intermediate scale quantum computing devices.

  

Renyi and Tsallis entropies of the Aharonov-Bohm ring in uniform magnetic fields

One-parameter functionals of the Renyi R_ρ,γ(α) and Tsallis T_ρ,γ(α) types are calculated in the position (subscript ρ) and momentum (γ) spaces for the 2D nanoring placed into the combination of the uniform magnetic field B and the AB flux Φ_AB. Ring potential is modelled by the superposition of the quadratic and inverse quadratic dependencies on the radius r. Position (momentum) Renyi entropy depends on B as a negative (positive) logarithm of ω_eff=(ω₀²+ω_c²/4)^1/2 , where ω₀ determines the quadratic steepness of the confining potential and ω_c is a cyclotron frequency. This makes the sum R_ρnm(α)+R_γnm(α/(2α-1)) a field-independent quantity that increases with the principal n and azimuthal m quantum numbers and satisfies corresponding uncertainty relation. In the limit α->1 both entropies in either space tend to their Shannon counterparts along, however, different paths. Analytic expression for the lower boundary of the semi-infinite range of the dimensionless coefficient α where the momentum entropies exist reveals that it depends on the ring geometry, Φ_AB and m. There is the only orbital for which both uncertainty relations turn into the identity at α=1/2 and which is not necessarily the lowest-energy level. At any coefficient α, the R_ρ-Φ_AB curve mimics the energy variation with Φ_AB.