Min-Hsiu Hsieh

Code switching is a powerful technique in quantum error correction that allows one to leverage the complementary strengths of different codes to achieve fault-tolerant universal quantum computation. However, existing code-switching protocols which encapsulate recent generalized lattice surgery approaches often either require many rounds of measurements to ensure fault-tolerance or suffer from low code rates. We present a single-shot, universal protocol that uses code-switching between high-rate quantum codes to perform fault-tolerant quantum computation. To our best knowledge, our work contains the first universal fault-tolerant quantum computation protocol that achieves what we term single-shot universality that is characterized by (i) single-shot error correction, (ii) single-shot state preparation, as well as (iii) logical gates and logical measurements with constant depth circuits. We achieve this by showing how to perform single-shot code switching between high-rate homological product codes by developing a generalization of Bombin's dimensional jump for color codes and Hillmann et al.'s single-shot lattice surgery for higher-dimensional topological codes. We introduce a vastly simpler recipe to construct 3D homological product codes with transversal CCZ gates that grants immense flexibility in the choice of expander graphs and local codes, allowing us to expand the search space for codes with good parameters and interesting logical gates. Our work opens an alternative path towards universal fault-tolerant quantum computation with low space-time overhead by circumventing the need for magic state distillation.

We study the construction of fully universal private channel coding protocols for classical-quantum channels. While earlier schemes achieved universal decoding, they relied on random encoders, preventing complete universality. We close this gap by showing that spectral expansion of a graph associated with a codebook guarantees universal channel resolvability: if the graph has a large spectral gap, the output state induced by the codewords is asymptotically indistinguishable from the target state, independent of the channel. This yields the first deterministic, channel-independent resolvability coding in the quantum regime. Combining this with universal channel coding, we construct a fully universal private coding protocol that achieves standard private information rates, highlighting the role of expander graphs in secure quantum communication.

In this work, we continue the search for quantum locally testable codes (qLTCs) of new parameters by presenting three constructions that can make new qLTCs from old. The first analyses the soundness of a quantum code under Hastings' weight reduction construction for qLDPC codes to give a weight reduction procedure for qLTCs. Secondly, we describe a novel `soundness amplification' procedure for qLTCs which can increase the soundness of any qLTC to a constant while preserving its distance and dimension, with an impact only felt on its locality. Finally, we apply the AEL distance amplification construction to the case of qLTCs for the first time which can turn a high-distance qLTC into one with linear distance, at the expense of other parameters. These constructions can be used on as-yet undiscovered qLTCs to obtain new parameters, but we also find a number of present applications. Applying these constructions in various combinations to recent advancements yields near-optimal quantum locally testable codes.

This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity tildeO(N^1/3) for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [Florian Adriaens and Simon Apers. Testing cluster properties of signed graphs.]. Second, we prove an tildeØmega(sqrtN) classical query lower bound for testing clusterability, which nearly matches the upper bound from citeadriaens2021testing. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.

Port-based teleportation (PBT) is a form of quantum teleportation in which no corrective unitary is required on the part of the receiver. Two primary regimes exist - deterministic PBT in which teleportation is always successful, but is imperfect, and probabilistic PBT, in which teleportation succeeds with probability less than one, but teleportation is perfect upon a success. Two further regimes exist within each of these in which the resource state used for the teleportation is fixed to a maximally entangled state, or free to be optimised. Recently, works resolved the long-standing problem of efficiently implementing port-based teleportation, tackling the two deterministic cases for qudits. Here, we provide algorithms in all four regimes for qubits. Emphasis is placed on the practicality of these algorithms, where we give polynomial improvements in the known gate complexity for PBT, as well as an exponential improvement in the required number of ancillas (albeit in separate protocols). Our approach to the implementation of the square-root measurement in PBT can be directly generalised to other highly symmetric state ensembles. For certain families of states, such a framework yields efficient algorithms in the case that the Petz recovery algorithm for the square-root measurement runs in exponential time.

Shallow-depth quantum circuits with gates of bounded fan-in have been demonstrated to achieve computational advantages over shallow-depth classical circuits, even allowing for unbounded fan-in (AC0). Despite their versatility, these computational models are known to be less powerful than Polynomial Threshold Function (PTF) circuits, which serve as a natural model for neural networks and exhibit enhanced expressivity and computational capabilities. We prove that PTF circuits with a constant number of layers, when biased (having the activation region of their gates limited), fail to solve certain computational (relational) problems that quantum circuits of constant depth can solve. Furthermore, we prove such a separation for a family of problems, one for each prime qudit dimension. We prove all of these separations via correlation bounds for average-case hardness. We also establish a tight lower bound on the size of biased PTF circuits that can solve a specific relational problem *exactly*. This allows us to significantly reduce the estimated resource requirements for potential demonstrations of quantum advantage. The main challenges in this area of research arise in establishing the classical lower bounds, and in designing non-local games with quantum-classical gaps in the winning strategy in order to go beyond qubits to higher dimensions. To address the former, we have formulated novel switching lemmas specifically designed for multi-output biased PTF circuits, and have developed a way to assess the difficulty of deriving exact solutions. Our contribution towards the latter is grounded in a novel assortment of non-local games, characterized by an exponential difference between their classical and quantum success probabilities. Finally, our technical developments could be of more general and independent interest.

Randomization has been applied to Hamiltonian simulation in a number of ways to improve the accuracy or efficiency of product formulas. Deterministic product formulas are often constructed in a symmetric way to provide accuracy of even order 2k. We show that by applying randomized corrections, it is possible to more than double the order to 4k + 1 (corresponding to a doubling of the order of the error). In practice, applying the corrections in a quantum algorithm requires some structure to the Hamiltonian, for example the Pauli strings as are used in the simulation of quantum chemistry.

In the study of Markovian processes, one of the principal achievements is the equivalence between the Phi-Sobolev inequalities and an exponential decrease of the Phi-entropies. In this work, we develop a framework of Markov semigroups on matrix-valued functions and generalize the above equivalence to the exponential decay of matrix Phi-entropies. This result also specializes to spectral gap inequalities and modified logarithmic Sobolev inequalities in the random matrix setting. To establish the main result, we define a non-commutative generalization of the carre du champ operator, and prove a de Bruijn's identity for matrix-valued functions. The proposed Markov semigroups acting on matrix-valued functions have immediate applications in the characterization of the dynamical evolution of quantum ensembles. We consider two special cases of quantum unital channels, namely, the depolarizing channel and the phase-damping channel. In the former, since there exists a unique equilibrium state, we show that the matrix Phi-entropy of the resulting quantum ensemble decays exponentially as time goes on. Consequently, we obtain a stronger notion of monotonicity of the Holevo quantity - the Holevo quantity of the quantum ensemble decays exponentially in time and the convergence rate is determined by the modified log-Sobolev inequalities. However, in the latter, the matrix Phi-entropy of the quantum ensemble that undergoes the phase-damping Markovian evolution generally will not decay exponentially. This is because there are multiple equilibrium states for such a channel. Finally, we also consider examples of statistical mixing of Markov semigroups on matrix-valued functions. We can explicitly calculate the convergence rate of a Markovian jump process defined on Boolean hypercubes, and provide upper bounds of the mixing time on these types of examples.