Engineering Papers⌕ Search

Engineering topics

Bravyi, Sergey

Publications and source records attributed to Bravyi, Sergey.

Quantum Complexity of the Kronecker Coefficients

Whether or not the Kronecker coefficients of the symmetric group count some set of combinatorial objects is a longstanding open question. In this work we show that a given Kronecker coefficient is proportional to the rank of a projector that can be measured efficiently using a quantum computer. In other words a Kronecker coefficient counts the dimension of the vector space spanned by the accepting witnesses of a QMA verifier, where QMA is the quantum analogue of NP . This implies that approximating the Kronecker coefficients to within a given relative error is not harder than a certain natural class of problems that captures the complexity of estimating thermal properties of quantum many-body systems. A second consequence is that deciding positivity of Kronecker coefficients is contained in QMA , complementing a recent NP -hardness result of Ikenmeyer, Mulmuley, and Walter. We obtain similar results for the related problem of approximating row sums of the character table of the symmetric group. Finally, we discuss an efficient quantum algorithm that approximates normalized Kronecker coefficients to inverse-polynomial additive error. Published by the American Physical Society 2024

Physics↗

Hybrid quantum-classical algorithms for approximate graph coloring

We show how to apply the recursive quantum approximate optimization algorithm (RQAOA) to MAX- k -CUT, the problem of finding an approximate k -vertex coloring of a graph. We compare this proposal to the best known classical and hybrid classical-quantum algorithms. First, we show that the standard (non-recursive) QAOA fails to solve this optimization problem for most regular bipartite graphs at any constant level p : the approximation ratio achieved by QAOA is hardly better than assigning colors to vertices at random. Second, we construct an efficient classical simulation algorithm which simulates level- 1 QAOA and level- 1 RQAOA for arbitrary graphs. In particular, these hybrid algorithms give rise to efficient classical algorithms, and no benefit arising from the use of quantum mechanics is to be expected. Nevertheless, they provide a suitable testbed for assessing the potential benefit of hybrid algorithm: We use the simulation algorithm to perform large-scale simulation of level- 1 QAOA and RQAOA with up to 300 qutrits applied to ensembles of randomly generated 3 -colorable constant-degree graphs. We find that level- 1 RQAOA is surprisingly competitive: for the ensembles considered, its approximation ratios are often higher than those achieved by the best known generic classical algorithm based on rounding an SDP relaxation. This suggests the intriguing possibility that higher-level RQAOA may be a potentially useful algorithm for NISQ devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Clifford Circuit Optimization with Templates and Symbolic Pauli Gates

The Clifford group is a finite subgroup of the unitary group generated by the Hadamard, the CNOT, and the Phase gates. This group plays a prominent role in quantum error correction, randomized benchmarking protocols, and the study of entanglement. Here we consider the problem of finding a short quantum circuit implementing a given Clifford group element. Our methods aim to minimize the entangling gate count assuming all-to-all qubit connectivity. First, we consider circuit optimization based on template matching and design Clifford-specific templates that leverage the ability to factor out Pauli and SWAP gates. Second, we introduce a symbolic peephole optimization method. It works by projecting the full circuit onto a small subset of qubits and optimally recompiling the projected subcircuit via dynamic programming. CNOT gates coupling the chosen subset of qubits with the remaining qubits are expressed using symbolic Pauli gates. Software implementation of these methods finds circuits that are only 0.2% away from optimal for 6 qubits and reduces the two-qubit gate count in circuits with up to 64 qubits by 64.7% on average, compared with the Aaronson-Gottesman canonical form.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Schrieffer-Wolff transformation for quantum many-body systems

The Schrieffer-Wolff (SW) method is a version of degenerate perturbation theory in which the low-energy effective Hamiltonian H{sub eff} is obtained from the exact Hamiltonian by a unitary transformation decoupling the low-energy and high-energy subspaces. We give a self-contained summary of the SW method with a focus on rigorous results. We begin with an exact definition of the SW transformation in terms of the so-called direct rotation between linear subspaces. From this we obtain elementary proofs of several important properties of H{sub eff} such as the linked cluster theorem. We then study the perturbative version of the SW transformation obtained from a Taylor series representation of the direct rotation. Our perturbative approach provides a systematic diagram technique for computing high-order corrections to H{sub eff}. We then specialize the SW method to quantum spin lattices with short-range interactions. We establish unitary equivalence between effective low-energy Hamiltonians obtained using two different versions of the SW method studied in the literature. Finally, we derive an upper bound on the precision up to which the ground state energy of the nth-order effective Hamiltonian approximates the exact ground state energy. - Highlights: > The Schrieffer-Wolff transformation is specialized to quantum spin lattices with short-range interactions. > We provide a diagram technique for computing high-order corrections to the effective low-energy Hamiltonian. > We derive a rigorous bound on the error up to which the nth-order effective low-energy dynamics approximates the exact dynamics.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Topological order in an exactly solvable 3D spin model

Research highlights: RHtriangle We study exactly solvable spin model with six-qubit nearest neighbor interactions on a 3D face centered cubic lattice. RHtriangle The ground space of the model exhibits topological quantum order. RHtriangle Elementary excitations can be geometrically described as the corners of rectangular-shaped membranes. RHtriangle The ground space can encode 4g qubits where g is the greatest common divisor of the lattice dimensions. RHtriangle Logical operators acting on the encoded qubits are described in terms of closed strings and closed membranes. - Abstract: We study a 3D generalization of the toric code model introduced recently by Chamon. This is an exactly solvable spin model with six-qubit nearest-neighbor interactions on an FCC lattice whose ground space exhibits topological quantum order. The elementary excitations of this model which we call monopoles can be geometrically described as the corners of rectangular-shaped membranes. We prove that the creation of an isolated monopole separated from other monopoles by a distance R requires an operator acting on {Omega}(R{sup 2}) qubits. Composite particles that consist of two monopoles (dipoles) and four monopoles (quadrupoles) can be described as end-points of strings. The peculiar feature of the model is that dipole-type strings are rigid, that is, such strings must be aligned with face-diagonals of the lattice. For periodic boundary conditions the ground space can encode 4g qubits where g is the greatest common divisor of the lattice dimensions. We describe a complete set of logical operators acting on the encoded qubits in terms of closed strings and closed membranes.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Subsystem codes with spatially local generators

We study subsystem codes whose gauge group has local generators in two-dimensional (2D) geometry. It is shown that there exists a family of such codes defined on lattices of size LxL with the number of logical qubits k and the minimum distance d both proportional to L. The gauge group of these codes involves only two-qubit generators of type XX and ZZ coupling nearest-neighbor qubits (and some auxiliary one-qubit generators). Our proof is not constructive as it relies on a certain version of the Gilbert-Varshamov bound for classical codes. Along the way, we introduce and study properties of generalized Bacon-Shor codes that might be of independent interest. Secondly, we prove that any 2D subsystem [n,k,d] code with spatially local generators obeys upper bounds kd=O(n) and d{sup 2}=O(n). The analogous upper bound proved recently for 2D stabilizer codes is kd{sup 2}=O(n). Our results thus demonstrate that subsystem codes can be more powerful than stabilizer codes under the spatial locality constraint.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Topological quantum order: Stability under local perturbations

We study zero-temperature stability of topological phases of matter under weak time-independent perturbations. Our results apply to quantum spin Hamiltonians that can be written as a sum of geometrically local commuting projectors on a D-dimensional lattice with certain topological order conditions. Given such a Hamiltonian H{sub 0}, we prove that there exists a constant threshold {epsilon}>0 such that for any perturbation V representable as a sum of short-range bounded-norm interactions, the perturbed Hamiltonian H=H{sub 0}+{epsilon}V has well-defined spectral bands originating from low-lying eigenvalues of H{sub 0}. These bands are separated from the rest of the spectra and from each other by a constant gap. The band originating from the smallest eigenvalue of H{sub 0} has exponentially small width (as a function of the lattice size). Our proof exploits a discrete version of Hamiltonian flow equations, the theory of relatively bounded operators, and the Lieb-Robinson bound.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗