Bulletin of the American Physical Society
APS March Meeting 2023
Volume 68, Number 3
Las Vegas, Nevada (March 5-10)
Virtual (March 20-22); Time Zone: Pacific Time
Session B47: Quantum Algorithms and Complexity |
Hide Abstracts |
Sponsoring Units: DQI Chair: Nic Ezzell, University of Southern California Room: Room 313 |
Monday, March 6, 2023 11:30AM - 11:42AM |
B47.00001: Locality and error correction in quantum dynamics with measurement Andrew Lucas The speed of light c sets a strict upper bound on the speed of information transfer in both classical and quantum systems. In nonrelativistic systems, the Lieb-Robinson Theorem imposes an emergent speed limit v |
Monday, March 6, 2023 11:42AM - 11:54AM |
B47.00002: Simulating NISQ dynamics using quantum trajectories with few jumps Philip D Blocher, Anupam Mitra, Tameem Albash, Akimasa Miyake, Ivan H Deutsch We present results on the efficiency of classically simulating the dynamics of open quantum many-body systems using a combination of quantum trajectories and 1D tensor network methods. Using Monte Carlo wavefunctions, the unraveling of the master equation gives rise to an ensemble of stochastic quantum trajectories conditioned on potential measurement outcomes (jumps). These trajectories must then be averaged over with appropriate jump statistics to obtain the system's density operator. The averaging is usually done in a stochastic manner until a sufficient sampling error is reached. Here we instead propose a deterministic method of sampling trajectories that avoids the computational overhead of stochastic trajectory sampling, is suitable for simulations of noisy intermediate-scale quantum (NISQ) devices, and has an easily computable sampling error. The usual object of interest in simulations of NISQ many-body dynamics is expectation values of local observables – e.g., one- or two-body correlation functions. These expectation values of local observables are regarded as being more robust to decoherence than other quantities less accessible to NISQ devices, and we conjecture that this robustness to decoherence implies the existence of a model solvable with classical efficiency. We apply our trajectory sampling method to demonstrate the efficiency of classical simulations of open quantum many-body dynamics, in support of this conjecture. |
Monday, March 6, 2023 11:54AM - 12:06PM |
B47.00003: Ground state preparation via unitary time evolution with time-dependent classical fields Zekun He Ground-state preparation is one of the most important problems in quantum computation and in computational many-body physics. Because time-dependent Hamiltonians can change their energy as a function of time, we can optimize the reduction of energy at each time step within a pool of allowed classical fields coupled to quantum operators of the system. In this fashion, we can prepare ground states with unitary circuits. The optimization step also helps the algorithm to be robust and work for a wide range of different initial states. Often, we can find ground-state fidelities of 0.99 or higher with relatively shallow unitary circuits. This approach is an alternative to Kraus-map approaches, which are robust for essentially all initial states, but become difficult to formulate with shallow circuits for interacting models. Our examples study the Hubbard model for a wide range of interactions, and show that this unitary method has a good likelihood of working, even on near-term quantum computers. |
Monday, March 6, 2023 12:06PM - 12:18PM |
B47.00004: Discrete-Time Quantum Walks on Compact Two-Dimensional Surfaces Elena Van der Vorst Random walks are powerful tools that are widely used in algorithmic problems. Similarly, quantum random walks, the quantum mechanical counterpart of the classical random walks, have found applications in several quantum algorithms. The first quantum walk-based algorithm was formulated in 2002 by Childs. In the same year, Shenvi et al. introduced the first algorithm in the discrete-time quantum walk setting. Quantum walks have since been used in various algorithmic problems and have been shown to obtain speed-ups for a number of them compared to their classical analogues. The above establishes the importance of discrete-time quantum walks in the context of algorithms, and motivates their study in general. There are two types of quantum walks: continuous-time quantum walks and discrete-time random walks. Despite various studies into continuous-time walks on compact two-dimensional shapes, few results are available for the discrete-time version. This work therefore focuses on discrete-time quantum walks on finite two-dimensional lattices, and considers the effects of (twisted) periodic and reflective boundary conditions. More specifically, it discusses some of the key properties of quantum walks on the rectangle, torus, Klein bottle, cylinder and Möbius strip. These properties include limiting distributions and marginal distributions. |
Monday, March 6, 2023 12:18PM - 12:30PM |
B47.00005: Quantum computation using PT-symmetric gates Salini Karuvade, Abhijeet Alase, Barry C Sanders The uniqueness of the inner product associated to a quantum system has come under scrutiny following the advent of PT-symmetric quantum mechanics. In this work we aim to ascertain the advantage offered by PT-symmetric gates for computation. To this end, we first show how a changing Hilbert-space inner product can be used to implement unbroken PT-symmetric evolutions. Next, we construct a model of computation in which the allowed gateset includes inner-product changing quantum operations in addition to unitary gates. This construction is based on the operational framework for changing the Hilbert-space inner product of a quantum system developed in S Karuvade, A. Alase and B. C. Sanders, Phys. Rev. Research 4, 013016 (2022). We also show how the new model allows for the implementation of non-unitary gates generated by unbroken PT-symmetric Hamiltonians. Furthermore, we show that the class of computational problems that are efficiently solved by the new model coincides with the complexity class bounded-error quantum polynomial time (BQP). To prove this result, we devised a technique to simulate inner-product changing quantum operations using unitary gates and measurements without changing the Hilbert-space representation of the underlying quantum system. Our work shows that exponential speedup for quantum computation cannot be achieved by changing the Hilbert-space inner product or by implementing PT-symmetric evolutions. |
Monday, March 6, 2023 12:30PM - 12:42PM |
B47.00006: Circuit depth versus energy in topologically ordered systems Arkin Tikku, Isaac H Kim We prove a nontrivial circuit-depth lower bound for preparing a low-energy state of a locally interacting quantum many-body system in two dimensions, assuming the circuit is geometrically local. For preparing any state which has an energy density of at most $epsilon$ with respect to Kitaev's toric code Hamiltonian on a two dimensional lattice $Lambda$, we prove a lower bound of $Omegaleft(minleft(1/epsilon^{frac{1-alpha}{2}}, sqrt{abs{Lambda}} ight) ight)$ for any $alpha >0$. We discuss two implications. First, our bound implies that the lowest energy density obtainable from a large class of existing variational circuits (e.g., Hamiltonian variational ansatz) cannot, in general, decay exponentially with the circuit depth. Second, if long-range entanglement is present in the ground state, this can lead to a nontrivial circuit-depth lower bound even at nonzero energy density. Unlike previous approaches to prove circuit-depth lower bounds for preparing low energy states, our proof technique does not rely on the ground state to be degenerate. |
Monday, March 6, 2023 12:42PM - 12:54PM Author not Attending |
B47.00007: Reducing the qubit requirement of Jordan-Wigner encodings of N-mode, K-fermion systems from N to log(N choose K) Brent A Harrison, James D Whitfield, Daniel M Adamiak, Riley Chien To simulate a fermionic system on a quantum computer, it is necessary to encode the state of the fermions onto qubits. Fermion-to-qubit mappings such as the Jordan-Wigner and Bravyi-Kitaev transformations do this using N qubits to represent systems of N fermionic modes. We demonstrate that for particle number conserving systems of K fermions and N modes, the qubit requirement can be reduced to the information theoretic minimum of log(N choose K). This will improve the feasibility of simulation of molecules and many-body systems on near-term quantum computers with limited qubit number. |
Monday, March 6, 2023 12:54PM - 1:06PM |
B47.00008: Equivalence between fermion-to-qubit mappings in two spatial dimensions Yu-An Chen, Yijia Xu We argue that all locality-preserving mappings between fermionic observables and Pauli matrices on a two-dimensional lattice can be generated from the exact bosonization cite{CKR18}, whose gauge constraints project onto the subspace of the toric code with emergent fermions. Starting from the exact bosonization and applying Clifford finite-depth generalized local unitary (gLU) transformation, we can achieve all possible fermion-to-qubit mappings (up to the re-pairing of Majorana fermions). |
Monday, March 6, 2023 1:06PM - 1:18PM |
B47.00009: Decomposing Quantum Unitaries into Circuits with Program Synthesis Leopoldo Sarra, Florian Marquardt, Kevin Ellis Superposition principle and entanglement are quantum effects that make quantum computing powerful. However, the development of quantum algorithms that exploit these properties is hard and requires considerable expertise. We want to investigate if one can employ machine learning techniques to facilitate the discovery of new algorithms. In particular, by mapping quantum algorithms to graphs of operations ("programs"), one could use program synthesis to find interpretable solutions to given tasks. As a proof-of-concept, we consider quantum unitary matrices of a fixed number of qubits and try to automatically decompose them in sequences of gates. We show how program synthesis algorithms allow to start from an elementary set of gates, gradually build circuits, understand which combinations of gates make useful composed gates and use them to decompose harder and harder matrices. |
Monday, March 6, 2023 1:18PM - 1:30PM |
B47.00010: On Unitary k-Design with SU(d) Symmetry Han Zheng, Zimu Li, Junyu Liu, Liang Jiang We propose, for the first time, an explicit unitary ensemble that can achieve unitary k-design with SU(d) symmetry by Schur-Weyl duality on SU(d) and Sn actions on qudits. From the perspective of investigating commutant subspaces, we establish relationship among well-known approaches like tensor product expander, kth fold channel and frame potential to study unitary design with or without an imposed symmetry. Based on which, we further explore the potential of applying Sn representation theory, especially the celebrated Okounkov-Vershik approach, to quantum physics, during which we define the kth order Convolutional Quantum Alternating group (CQA) with kth order CQA ensemble with at most 2k-local unitary and prove that they form SU(d) symmetric k-design in exact and approximate senses respectively. Our results indicate that, despite a "no-go theorem" between locality and universality in the presence of SU(d) symmetry, ensembles of local SU(d)-symmetric unitary would still form unitary k-designs under SU(d) symmetry. |
Monday, March 6, 2023 1:30PM - 1:42PM |
B47.00011: Entanglement in the vertex state: conformal interface approach Yuhan Liu, Yuya Kusuki, Ramanjit Sohal, Jonah L Kudler-Flam, Shinsei Ryu The multipartite entanglement structure for the ground states of two dimensional topological phases is an interesting albeit not well understood question. Utilizing the bulk-boundary correspondence, the tripartite entanglement calculation of 2d topological phases can be reduced to that on the vertex state, defined by the boundary conditions at the interfaces between spatial regions. We use the conformal interface technique to calculate the entanglement measures of the vertex state, which include the area-law, geometrical and topological pieces, and the possible extra order one contribution. A direct consequence is the Markov gap $h=c/3log{2}$, which applies to the vertex state of general rational conformal field theory. Finally, we support our prediction by numerical evidence in the n-vertex state of real fermion (boundary of chiral superconductor). |
Monday, March 6, 2023 1:42PM - 1:54PM |
B47.00012: Linear Growth of Circuit Complexity from Brownian Dynamics Gregory Bentsen, Shaokai Jian, Brian Swingle How rapidly can a many-body quantum system generate randomness? Using path integral methods, we demonstrate that Brownian quantum systems have circuit complexity that grows linearly with time. In particular, we study Brownian clusters of $N$ spins or fermions with time-dependent all-to-all interactions, and calculate the Frame Potential to characterize complexity growth in these models. In both cases the problem can be mapped to an effective statistical mechanics problem which we study using path integral methods. Within this framework it is straightforward to show that the $k$th Frame Potential comes within $epsilon$ of the Haar value after a time of order $t sim k N + k log k + log epsilon^{-1}$. Using a bound on the diamond norm, this implies that such circuits are capable of coming very close to a unitary $k$-design after a time of order $t sim k N$. We also consider the same question for systems with a time-independent Hamiltonian and argue that a small amount of time-dependent randomness is sufficient to generate a $k$-design in linear time provided the underlying Hamiltonian is quantum chaotic. These models provide explicit examples of linear complexity growth that are analytically tractable and are directly applicable to practical applications calling for unitary $k$-designs. |
Monday, March 6, 2023 1:54PM - 2:06PM |
B47.00013: Taking Quantum States as Objective Possibilities Seriously Armin Nikkhah Shirazi There is a common ``back-of-the-mind idea'', prompted by phenomena such as quantum contextuality and quantum non-locality, that quantum states represent ``mere possibilities'' in some vague sense. Yet, this idea reflects itself neither in the quantum formalism nor in the way we use it. In this talk, I explore what it entails to take this idea seriously. |
Monday, March 6, 2023 2:06PM - 2:18PM |
B47.00014: Quantum algorithms for thermal equilibrium from fluctuation theorems Rolando D Somma, Yigit Subasi, Burak Sahinoglu, Gopikrishnan Muraleedharan, Zoe Holmes Fluctuation theorems provide a correspondence between properties of quantum systems in thermal equilibrium and a work distribution arising in a non-equilibrium process that connects two quantum systems with Hamiltonians H0 and H1=H0+V. Building upon these theorems, we present quantum algorithms to prepare the thermal state of H1 at inverse temperature β≥0 and to estimate the free energy difference between the two systems. The complexity of these algorithms, given by the number of times certain unitaries are used, is at most exponential in β|V|, where |V| is the spectral norm of V. This is a significant improvement of prior quantum algorithms that have complexity exponential in β|H0| or β|H1|. The dependence of the complexity in terms of a precision parameter ε>0 varies according to the structure of the quantum systems. For the problem of thermal state preparation, this complexity can be exponential in 1/ε in general, but we show it to be sublinear in 1/ε if H0 and H1 commute, or polynomial in 1/ε if H0 and H1 are local spin systems. The possibility of applying a unitary that drives the system H0 out of equilibrium allows one to improve the complexity of the quantum algorithms even further. |
Monday, March 6, 2023 2:18PM - 2:30PM |
B47.00015: A Unified Graph-Theoretic Framework for Free-Fermion Solvability Adrian K Chapman, Samuel J Elman, Ryan L Mann We provide a simple criterion to determine whether a spin model admits an exact description by noninteracting fermions. Our criterion is given in terms of the model's frustration graph, which captures the pairwise anticommutation relations between Pauli terms of the Hamiltonian in a given basis. An exact solution exists when this graph is claw-free and contains a structure called a simplicial clique. This unifies characterizations given in previous work, where it was shown that a free-fermion mapping exists when this graph is either a line graph, or (even-hole, claw)-free. The former case includes the Jordan-Wigner transformation and the exact solution to the Kitaev honeycomb model, and the latter case generalizes a non-local solution to the four-fermion model given by Fendley. Our characterization unifies these two approaches, extending the generalized Jordan-Wigner solutions to the non-local case and extending the generalized four-fermion solution to models of arbitrary spatial dimension. These results establish a deep connection between many-body physics and the mathematical theory of claw-free graphs. |
Follow Us |
Engage
Become an APS Member |
My APS
Renew Membership |
Information for |
About APSThe American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics. |
© 2024 American Physical Society
| All rights reserved | Terms of Use
| Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200
Editorial Office
100 Motor Pkwy, Suite 110, Hauppauge, NY 11788
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700