Quantum algorithms claim significant speedup over their classical counterparts for solving many problems. An important aspect of many of these algorithms is the existence of a quantum oracle, which needs to be implemented efficiently in order to realize the claimed advantages in practice. A quantum random access memory (QRAM) is a promising architecture for realizing these oracles. In this paper we develop a new design for QRAM and implement it with Clifford+T circuit. We focus on optimizing the T-count and T-depth since non-Clifford gates are the most expensive to implement fault-tolerantly in most error correction schemes. Integral to our design is a polynomial encoding of bit strings and so we refer to this design as [Formula: see text]. Compared to the previous state-of-the-art bucket brigade architecture for QRAM, we achieve an exponential improvement in T-depth, while reducing T-count and keeping the qubit-count same. Specifically, if N is the number of memory locations to be queried, then [Formula: see text] has T-depth [Formula: see text], T-count [Formula: see text] and uses O(N) logical qubits, while the bucket brigade circuit has T-depth [Formula: see text], T-count O(N) and uses O(N) qubits. Combining two [Formula: see text] we design a quantum look-up-table, [Formula: see text], that has T-depth [Formula: see text], T-count [Formula: see text] and qubit count [Formula: see text]. A quantum look-up table (qLUT) or quantum read-only memory (QROM) has restricted functionality than a QRAM. For example, it cannot write into a memory location and the circuit needs to be compiled each time the contents of the memory change. The previous state-of-the-art CSWAP architecture has T-depth [Formula: see text], T-count [Formula: see text] and qubit count [Formula: see text]. Thus we achieve a double exponential improvement in T-depth while keeping the T-count and qubit-count asymptotically same. Additionally, with our polynomial encoding of bit strings, we develop a method to optimize the Toffoli-count of circuits, specially those consisting of multi-controlled-NOT gates.
We construct local generalizations of 3-state Potts models with exotic critical points. We analytically show that these are described by non-diagonal modular invariant partition functions of products of Z_3 Z 3 parafermion or u(1)_6 u ( 1 ) 6 conformal field theories (CFTs). These correspond either to non-trivial permutation invariants or block diagonal invariants, that one can understand in terms of anyon condensation. In terms of lattice parafermion operators, the constructed models correspond to parafermion chains with many-body terms. Our construction is based on how the partition function of a CFT depends on symmetry sectors and boundary conditions. This enables to write the partition function corresponding to one modular invariant as a linear combination of another over different sectors and boundary conditions, which translates to a general recipe how to write down a microscopic model, tuned to criticality. We show that the scheme can also be extended to construct critical generalizations of k k -state clock type models.