Quantum Information

In this talk, I will present three algorithms that address distinct variants of the problem of testing quantum states. First, I will discuss the problem of statistically testing whether an unknown quantum state is a matrix product state of certain bond dimension or it is far from all such states. Next, I will demonstrate a method for testing whether a bipartite quantum state, shared between two parties, corresponds to the ground state of a given gapped local Hamiltonian. Finally, I will present a scheme for verifying that a machine learning model of an unknown quantum state has high overlap with the actual state.

Zoom Link: https://pitp.zoom.us/j/99250127489?pwd=UCtXUi9zMzJZamppT29DbWtJcWU3Zz09

We investigate the evolution of quantum information under Pauli measurement circuits. We focus on the case of one- and two-dimensional systems, which are relevant to the recently introduced Floquet topological codes. We define local reversibility in context of measurement circuits, which allows us to treat finite depth measurement circuits on a similar footing to finite depth unitary circuits. In contrast to the unitary case, a finite depth locally reversible measurement sequence can implement a translation in one dimension. A locally reversible measurement sequence in two dimensions may also induce a flow of logical information along the boundary. We introduce "measurement quantum cellular automata" which unifies these ideas and define an index in one dimension to characterize the flow of logical operators. We find a Z_2 bulk invariant for Floquet topological codes which indicates an obstruction to having a trivial boundary. We prove that the Hastings-Haah honeycomb code belong to a class with such obstruction, which means that any boundary must have either non-local dynamics, period doubled, or admits boundary flow of quantum information.

Zoom Link: https://pitp.zoom.us/j/96083249406?pwd=MnhYbTEyU05ybVdyUlE3UGZrdEhPdz09

A key subroutine in quantum computing, especially in quantum simulation, is to prepare thermal states or ground states of Hamiltonians. Today, I will talk about a new family of quantum algorithms for this task. Physically, our algorithms distill the essence of system-bath interaction by simulating an effective Lindbladian; computationally, our algorithms are quantum analogs of classical Markov chain Monte Carlo sampling. Given the ubiquity of thermodynamics and the triumph of classical Monte Carlo methods, we anticipate that quantum thermal state preparation will become indispensable in quantum computing. 

Joint work with Michael J. Kastoryano, Fernando G.S.L. Brandão, and András Gilyén. https://arxiv.org/abs/2303.18224 

Zoom Link: https://pitp.zoom.us/j/91641127738?pwd=cExPM3Bvd3BaYnJYS0U0UlBiVTJ0QT09

We study the behavior of errors in the quantum simulation of  spin systems with long-range multibody interactions resulting from the  Trotter-Suzuki decomposition of the time evolution operator. We  identify a regime where the Floquet operator underlying the Trotter  decomposition undergoes sharp changes even for small variations in the  simulation step size. This results in a time evolution operator that  is very different from the dynamics generated by the targeted  Hamiltonian, which leads to a proliferation of errors in the quantum  simulation. These regions of sharp change in the Floquet operator,  referred to as structural instability regions, appear typically at  intermediate Trotter step sizes and in the weakly interacting regime,  and are thus complementary to recently revealed quantum chaotic  regimes of the Trotterized evolution [L. M. Sieberer et al. npj  Quantum Inf. 5, 78 (2019); M. Heyl, P. Hauke, and P. Zoller, Sci. Adv.  5, eaau8342 (2019)]. We characterize these structural instability  regimes in p-spin models, transverse-field Ising models with  all-to-all p-body interactions, and analytically predict their  occurrence based on unitary perturbation theory. We further show that  the effective Hamiltonian associated with the Trotter decomposition of  the unitary time-evolution operator, when the Trotter step size is  chosen to be in the structural instability region, is very different  from the target Hamiltonian, which explains the large errors that can  occur in the simulation in the regions of instability. These results  have implications for the reliability of near-term gate based quantum  simulators, and reveal an important interplay between errors and the  physical properties of the system being simulated.

Zoom link:  https://pitp.zoom.us/j/92045582127?pwd=WDUxcnlIeXdnVWM3WGJoSFVMNDE2dz09

We present a quantum algorithm for simulating the classical dynamics of 2^n coupled oscillators (e.g.,  masses coupled by springs). Our approach leverages a mapping between the Schrodinger equation and Newton's equations for harmonic potentials such that the amplitudes of the evolved quantum state encode the momenta and displacements of the classical oscillators. When individual masses and spring constants can be efficiently queried, and when the initial state can be efficiently prepared, the complexity of our quantum algorithm is polynomial in n, almost linear in the evolution time, and sublinear in the sparsity. As an example application, we apply our quantum algorithm to efficiently estimate the kinetic energy of an oscillator at any time, for a specification of the problem that we prove is BQP-complete. Thus, our approach solves a potentially practical application with an exponential speedup over classical computers. Finally, we show that under similar conditions our approach can efficiently simulate more general classical harmonic systems with 2^n modes.

Zoom link:  https://pitp.zoom.us/j/91882209363?pwd=UndJRVdaZW04RGtpL0M2SE52RDJwZz09

For n≥3, we demonstrate the existence of quantum codes which are local in dimension n with V qubits, distance V^{(n−1)/n}, and dimension V^{(n−2)/n}, up to a polylog(V) factor. The distance is optimal up to the polylog factor. The dimension is also optimal for this distance up to the polylog factor. The proof combines the existence of asymptotically good quantum codes, a procedure to build a manifold from a code by Freedman-Hastings, and a quantitative embedding theorem by Gromov-Guth.

Zoom link:  https://pitp.zoom.us/j/96227350980?pwd=TEFtamRmTXg3dnBMNEhKUkpHbmVoZz09

Entanglement entropies of two-dimensional gapped ground states are expected to satisfy an area law, with a constant correction term known as the topological entanglement entropy (TEE). In many models, the TEE takes a universal value that characterizes the underlying topological phase. However, the TEE is not truly universal: it can differ even for two states related by constant-depth circuits, which are necessarily in the same phase. The difference between the TEE and the value predicted by the anyon theory is often called the spurious topological entanglement entropy. We show this spurious contribution is always nonnegative, thus the value predicted by the anyon theory provides a universal lower bound. This observation also leads to a definition of TEE which is invariant under constant-depth quantum circuits.

Based on a joint work with Daniel Ranard (MIT), Michael Levin (U Chicago), Ting-Chun Lin (UCSD), and Bowen Shi (UCSD)

Zoom link:  https://pitp.zoom.us/j/93809342984?pwd=QXJkK0ZYR3QzdjlUUWlkMEFXMWRnQT09

I will introduce a family of dual-unitary circuits in 1+1 dimensions which are invariant under the joint action of Lorentz and scale transformations. With the same dual unitaries I will construct tensor-network states for this 1+1 model and interpret them as spatial slices of curved 2+1 discrete geometries. These tensor-network states satisfy the Ryu-Takayanagi conjecture outside event horizons, but the geometry of the network is also well defined inside the horizon. The dynamics of the circuit induces a natural dynamics on these geometries which reproduces GR phenomena like the gravitational redshift, the formation of black holes and the growth of their throat.

Zoom link:  https://pitp.zoom.us/j/92034586204?pwd=eEo0NzVjeFkxWVJnY0hjOUhodXNWdz09

Quantum error mitigation has been proposed as a means to combat unwanted and unavoidable errors in near-term quantum computing using no or few additional quantum resources, in contrast to fault-tolerant schemes that come along with heavy overheads. Error mitigation has been successfully applied to reduce noise in near-term applications. 

In this work, however, we identify strong limitations to the degree to which quantum noise can be effectively `undone' for larger system sizes. We set up a framework that rigorously captures large classes of error mitigation schemes in use today. The core of our argument combines fundamental limits of statistical inference with a construction of families of random circuits that are highly sensitive to noise.

We show that even at poly loglog depth, a super-polynomial number of samples is needed in the worst case to estimate the expectation values of noiseless observables, the principal task of error mitigation. Notably, our construction implies that scrambling due to noise can kick in at exponentially smaller depths than previously thought. They also impact other near-term applications, constraining kernel estimation in quantum machine learning, causing an earlier emergence of noise-induced barren plateaus in variational quantum algorithms and ruling out exponential quantum speed-ups in estimating expectation values in the presence of noise or preparing the ground state of a Hamiltonian.

Zoom link:  https://pitp.zoom.us/j/95736148335?pwd=akZLaHE5aStNQVZOeVFETlltNzVwdz09

Tom Leinster recently introduced a curious notion of entropy modulo p (https://arxiv.org/abs/1903.06961). While entropy has a certain meaning in information theory and physics, mathematically it is simply a function with certain properties. Stating these as axioms, the function is unique. Surprisingly, Leinster shows that a function obeying the same axioms can also be found for "probability distributions" over a finite field, and this function is unique too.

In quantum information, mutually unbiased bases is an important set of measurements and an example of a quantum design. While in odd prime power dimensions their construction is based on a finite field, in dimension 2^n it relies on an unpleasant Galois ring. I will replace this ring by length-2 Witt vectors whose arithmetic involves only finite field operations and Leinster's entropy mod 2. This expresses qubit mutually unbiased bases entirely in terms of a finite field and allows deriving an explicit unitary correspondence between them and the affine plane over this field.

Zoom link:  https://pitp.zoom.us/j/94032116379?pwd=TTI1RnByQnFuVHp1MytFUlJxckM4Zz09

Kronecker coefficients appear in representation of the symmetric group in the decomposition of tensor products of irreducible representations. They are notoriously difficult to compute and it is a long standing problem to find a combinatorial expression for them. 

We study the problem of computing Kronecker coefficients from quantum computational perspective. First, we show that the coefficients can be expressed as a dimension of a subspace given by intersection of two commuting, efficiently implementable projectors and relate their computation to the recently introduced quantum approximate counting class (QAPC). Using similar construction, we show that deciding positivity of Kronecker coefficients is contained in QMA. We give similar results for a related problem of approximating row sums in a character table of the symmetric group and show that its decision variant is in QMA. We then discuss two quantum algorithms - one that samples a distribution over squared characters and another one that approximates normalized Kronecker coefficients to inverse-polynomial additive error. We show that under a conjecture about average-case hardness of computing Kronecker coefficients, the resulting distribution is hard to sample from classically. 

Our work explores new structures for quantum algorithms and improved characterization of the quantum approximate counting.

Joint work with David Gossett, Sergey Bravyi, Anirban Chowdhury and Guanyu Zhu 

Zoom link:  https://pitp.zoom.us/j/95976938016?pwd=eDV3TXZReHo5UHdvZ0hIbkhXOFcxQT09

Classical simulation algorithms provide a rigorous ground for investigating quantum resources responsible for quantum speedup. In my talk, I will consider one such algorithm provided by Lambda polytopes. These polytopes are defined to be the polar dual of the stabilizer polytopes and can be used to provide a hidden variable model for finite-dimensional quantum theory. This hidden variable model can be turned into a  classical algorithm that can simulate any quantum computation. The efficiency of this algorithm depends on the combinatorial structure of the polytope. In general, which subset of the vertices gives rise to efficient simulation is an open problem. I will describe some of the known classes of vertices and available methods for studying this polytope.

Zoom link:  https://pitp.zoom.us/j/95216680309?pwd=aGlIN2NtZVRtczdHcXl5RzgzQTlOdz09