More Like this

1. Periodicity in the cumulative hierarchy

   https://doi.org/10.4171/JEMS/1318  

   Goldberg, Gabriel; Schlutzenberg, Farmer (March 2023, Journal of the European Mathematical Society)
2. The Hierarchy of Block Models

   https://doi.org/10.1007/s13171-021-00247-2  

   Noroozi, Majid; Pensky, Marianna (June 2022, Sankhya A)
3. Cosmological perturbations without the Boltzmann hierarchy

   https://doi.org/10.1103/PhysRevD.104.063512  

   Kamionkowski, Marc (September 2021, Physical Review D)

   null (Ed.)
4. The Kikuchi Hierarchy and Tensor PCA

   https://doi.org/10.1109/FOCS.2019.000-2  

   Wein, Alexander S.; El Alaoui, Ahmed; Moore, Cristopher (November 2019, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS))

   For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of increasingly powerful algorithms with increasing runtime. Our hierarchy is analogous to the sumof-squares (SOS) hierarchy but is instead inspired by statistical physics and related algorithms such as belief propagation and AMP (approximate message passing). Our level-ℓ algorithm can be thought of as a linearized message-passing algorithm that keeps track of ℓ-wise dependencies among the hidden variables. Specifically, our algorithms are spectral methods based on the Kikuchi Hessian, which generalizes the well-studied Bethe Hessian to the higher-order Kikuchi free energies. It is known that AMP, the flagship algorithm of statistical physics, has substantially worse performance than SOS for tensor PCA. In this work we ‘redeem’ the statistical physics approach by showing that our hierarchy gives a polynomial-time algorithm matching the performance of SOS. Our hierarchy also yields a continuum of subexponential-time algorithms, and we prove that these achieve the same (conjecturally optimal) tradeoff between runtime and statistical power as SOS. Our proofs are much simpler than prior work, and also apply to the related problem of refuting random k-XOR formulas. The results we present here apply to tensor PCA for tensors of all orders, and to k-XOR when k is even. Our methods suggest a new avenue for systematically obtaining optimal algorithms for Bayesian inference problems, and our results constitute a step toward unifying the statistical physics and sum-of-squares approaches to algorithm design. 

   more » « less
5. Un-Weyl-ing the Clifford hierarchy

   https://doi.org/doi.org/10.22331/q-2020-12-11-370  

   Pllaha, T.; Rengaswamy, N.; Tirkonnen, O.; Calderbank, R. (December 2020, Quantum)

   null (Ed.)

   The teleportation model of quantum computation introduced by Gottesman and Chuang (1999) motivated the development of the Clifford hierarchy. Despite its intrinsic value for quantum computing, the widespread use of magic state distillation, which is closely related to this model, emphasizes the importance of comprehending the hierarchy. There is currently a limited understanding of the structure of this hierarchy, apart from the case of diagonal unitaries (Cui et al., 2017; Rengaswamy et al. 2019). We explore the structure of the second and third levels of the hierarchy, the first level being the ubiquitous Pauli group, via the Weyl (i.e., Pauli) expansion of unitaries at these levels. In particular, we characterize the support of the standard Clifford operations on the Pauli group. Since conjugation of a Pauli by a third level unitary produces traceless Hermitian Cliffords, we characterize their Pauli support as well. Semi-Clifford unitaries are known to have ancilla savings in the teleportation model, and we explore their Pauli support via symplectic transvections. Finally, we show that, up to multiplication by a Clifford, every third level unitary commutes with at least one Pauli matrix. This can be used inductively to show that, up to a multiplication by a Clifford, every third level unitary is supported on a maximal commutative subgroup of the Pauli group. Additionally, it can be easily seen that the latter implies the generalized semi-Clifford conjecture, proven by Beigi and Shor (2010). We discuss potential applications in quantum error correction and the design of flag gadgets. 

   more » « less