Session B52: Quantum Algorithms and Complexity

Quantum simulation of parity-time symmetric systems with diagonal operators

Quantum simulation of quantum systems stands as a pivotal application in the field of quantum computation. However, the accurate representation of real quantum systems poses a challenge, given that most are open systems undergoing non-unitary processes. To capture the dynamics of non-hermitian systems, we must employ innovative simulation methods. In this presentation, I will talk about the implementation of singular value decomposition of the evolution operator for a Parity-Time symmetric system. This method requires dilation of the Hilbert space of the desired quantum system with only one extra qubit. I will demonstrate the scalability of this technique by applying it to two-level and three-level non-Hermitian systems on a real quantum processor.   

Theoretical constraints on simulating non-Markovian topological quantum walks in synthetic dimensions

Topologically protected quantities are robust to symmetry-preserving perturbations that don’t close an energy gap. However, every realistic system is coupled to an environment that may break those symmetries and thus break the topological protection. A significant recent effort has been focussed on the non-Hermitian description of open systems in this context [1]. When considering Hermitian system-bath models, where the bath is included in the model, new behavior can become apparent. This is the case in the non-Markovian topological quantum walks, introduced in Ref. [2]. In this model, a walker can evolve on an SSH-chain with quantum baths attached to every other site. The mean displacement of the walker before leaving the bath is quantized and equal to the topological invariant of the SSH model for sub-ohmic baths. For super-ohmic baths, however, this quantization breaks down. We will discuss theoretical constraints on reproducing this effect experimentally with a finite bath and how to implement the resulting model in synthetic dimensions [3].

[1] N. Okuma and M. Sato, “Non-Hermitian Topological Phenomena: A Review,” Annu. Rev. Condens. Matter Phys., vol. 14, no. 1, pp. 83–107, 2023, doi: 10.1146/annurev-conmatphys-040521-033133.

[2] A. Ricottone, M. S. Rudner, and W. A. Coish, “Topological transition of a non-Markovian dissipative quantum walk,” Phys. Rev. A, vol. 102, no. 1, p. 012215, Jul. 2020, doi: 10.1103/PhysRevA.102.012215.

[3] F. Pellerin, R. Houvenaghel, W. A. Coish, I. Carusotto, and P. St-Jean, “Wavefunction tomography of topological dimer chains with long-range couplings.” arXiv, Jul. 03, 2023. doi: 10.48550/arXiv.2307.01283.   

Simulation of open quantum systems with giant atoms

Open quantum many-body systems are both of fundamental interest and have practical applications. In many cases, numerically solving such systems with classical methods is infeasible; instead, quantum simulation is required. Yet, conventional quantum simulation methods either require a large amount of ancilla qubits or operate within limited parameter spaces. To overcome these challenges, we put forward a novel protocol for simulating open quantum many-body systems with giant atoms. Unlike conventional point-like small atoms, giant atoms couple to the environment at multiple points, yielding interference effects that grant remarkable tunability in the interactions between the atoms and the environment. Utilizing this high tunability, we demonstrate efficient simulation of a variety of open quantum systems with two giant atoms coupled to a waveguide. We further show the capability of this setup to simulate models not intrinsically present in the system by tuning the qubit frequencies at different time steps. Our results can be extended to a larger number of giant atoms, and pave the way towards versatile simulation of open quantum many-body systems.   

Gibbs sampling via cluster expansions

Gibbs states (i.e., thermal states) can be used for several applications such as quantum simulation, quantum machine learning, quantum optimization, and the study of open quantum systems. Moreover, semi-definite programming, combinatorial optimization problems, and training quantum Boltzmann machines can all be addressed by sampling from well-prepared Gibbs states. With that, however, comes the fact that preparing and sampling from Gibbs states on a quantum computer are notoriously difficult tasks. Such tasks can require large overhead in resources and/or calibration even in the simplest of cases, as well as the fact that the implementation might be limited to only a specific set of systems. We propose a method based on sampling from a quasi-distribution consisting of tensor products of mixed states on local clusters, i.e., expanding the full Gibbs state into a sum of products of local "Gibbs-cumulant" type states easier to implement and sample from on quantum hardware. We present results for measuring both the dynamical structure factor and the specific heat of different Gibbs states of spin systems.   

Nearly-optimal simulation of quantum field theory

I will present recent results on state preparation and time evolution in quantum field theories, based on utilizing quantum simulation algorithms with nearly-optimal scaling in problem parameters. I will also discuss ways to overcome the major bottleneck of such methods — the efficient implementation of block encoding — with the aid of the recently developed Quantum Eigenvalue Transformation for Unitary Matrices.   

Linear Combination of Hamiltonian Simulation for Nonunitary Dynamics

We propose a simple method for simulating a general class of nonunitary dynamics as a linear combination of Hamiltonian simulation (LCHS) problems. LCHS does not rely on converting the problem into a dilated linear system problem or on the spectral mapping theorem. The latter is the mathematical foundation of many quantum algorithms for solving a wide variety of tasks involving nonunitary processes, such as the quantum singular value transformation. The LCHS method can achieve optimal cost in terms of state preparation, and an improved LCHS method further achieves near-optimal dependence on all parameters in terms of matrix queries. We also demonstrate an application for open quantum dynamics simulation using the complex absorbing potential method.   

Toward a Unified Picture of Fermion-to-Qubit Transforms

Several mappings of fermions to qubits analogous to Jordan-Wigner have been proposed, including the Bravyi-Kitaev transformation, as well as the Ternary Tree and Parity mappings. Using graph- and group-theoretic methods, we present progress toward a unified framework for all such mappings. In particular, we describe the set of such mappings whose qubit representations of creation and annihilation operators are single Pauli strings. We endow this set with a group structure, divide it into equivalence classes based on operator locality properties, and show that these classes can be labeled by certain orbits of the symplectic group over $mathbb{F}_2$. For encodings with non-entangled basis states, we find a labeling in terms of nonsingular directed graphs. We present considerations for optimization over this space of equivalence classes, with applications to near-term quantum simulation.   

Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments

Today’s experimental noisy quantum processors can compete with and surpass all known algorithms on state-of-the-art supercomputers for the computational benchmark task of Random Circuit Sampling. Additionally, a circuit-based quantum simulation of quantum information scrambling, which measures a local observable, has already outperformed standard full wave function simulation algorithms, such as, exact Schrodinger evolution and Matrix Product States (MPS). Nevertheless, this experiment has not yet surpassed tensor network contraction for computing the value of the observable.

In my presentation I will review the concept of circuit volume and how it can be used to explain the tradeoff between the experimentally achievable signal-to-noise ratio for a specific observable, and the corresponding computational cost. I will also describe the application of the circuit volume to recent quantum processor experiments of Random Circuit Sampling, quantum information scrambling, and a Floquet circuit unitary.   

Entanglement spectrum statistics in matchgate circuits with supplemental resources

We study the entanglement spectrum generated by matchgate circuits with various additional resources. We show that, for matchgate circuits acting on product states, Wigner-Dyson entanglement statistics emerges in the thermodynamic limit by virtue of a single SWAP gate. This is analogous to the Clifford case, in which only a single T-gate is needed to achieve universal entanglement spectrum statistics under similar system size scaling [1]. Additionally, we examine the entanglement complexity [2] of matchgate circuits with varied initial states, showing a jump in complexity when input states are composed of entangled products of three or more qubits. Our work clarifies the relationship between simulatability, entanglement entropy, and the complexity of entanglement in several different simulable gate sets.

[1] Zhou et. al., SciPost Phys. 9, 087 (2020)

[2] Shaffer et. al., J. Stat. Mech. (2014) P12007   

Classical limits of quantum algorithms

Fault-tolerant quantum computing promises to solve some computational tasks that turn out to be hard on classical computing machines. There are algorithms like Grover's algorithm that have proven speedup against any classical algorithm. Unfortunately, truly fault-tolerant quantum computers have not been realized yet. The potential to achieve quantum advantage with quantum algorithms that run on today's noisy intermediate scale quantum (NISQ) devices remains an open question to date. Here, we propose a systematic strategy to benchmark given NISQ-algorithms for their potential of quantum advantage by comparing these algorithms to their own classical limits.   

What physical model does a Trotterized time evolution on a noisy quantum computer effectively simulate?

We consider the extent to which a noisy quantum computer is able to simulate the time evolution of a quantum spin system in a faithful manner. Given a reasonable set of assumptions regarding the manner in which noise acts on such a device, we argue for a circuit-level description of noise in terms of individual decoherence events following otherwise noise-free gates. With such a model, we further show how the effects of noise can be reinterpreted as a modification to the dynamics of the original system being simulated. We find that this modification corresponds to the introduction of static Lindblad terms, which act in addition to the original unitary dynamics. The form of these terms depends not only on the underlying noise processes occurring on the device, but also on the original unitary dynamics, as well as the manner in which these dynamics are simulated on the device, i.e., the choice of quantum algorithm. Our results are confirmed through numerical analysis. In addition to understanding the extent to which the result of a digital quantum simulation may differ from the intended calculation, our results may aide in tailoring quantum circuits to achieve the simulation of a given noisy spin system, as well as provide additional insight into Lindblad dynamics more broadly.