The Programme Committee of TQC 2024 selected 92 out of 460 submissions for a contributed talk (20% acceptance rate).
You may find the contributed talks here.
The list of accepted posters will be published on the 2nd of May, after the poster notification date. The conference schedule will be published in July.
Note on the list: The talks are listed in alphabetical order of title. Later they will be listed by day of presentation. The topic tags were self-selected by the authors upon submission, given the options provided by the PC chairs.
1.
Libor Caha, Xavier Coiteux-Roy, Robert Koenig
A colossal advantage: 3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits Talk
2024.
Abstract | Tags: Quantum complexity theory, Quantum error correction and fault-tolerant quantum computing
@Talk{T24_208,
title = {A colossal advantage: 3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits},
author = {Libor Caha and Xavier Coiteux-Roy and Robert Koenig},
year = {2024},
date = {2024-01-01},
abstract = {We present a computational problem with the following properties: (i) Every instance can be solved with near-certainty by a constant-depth quantum circuit using only nearest-neighbor gates in 3D, even when its implementation is corrupted by noise. (ii) Any constant-depth classical circuit composed of unbounded fan-in AND, OR, as well as NOT gates, i.e., an AC0-circuit, of size smaller than a certain subexponential, fails to solve a uniformly random instance with probability greater than a certain constant. Such an advantage against unbounded fan-in classical circuits was previously only known in the noise-free case or when ignoring locality constraints. By overcoming these limitations, we are thus proposing the strongest unconditional, fault-tolerant quantum-advantage demonstration to date. Subexponential circuit-complexity lower bounds have traditionally been referred to as exponential. We use the term colossal since our fault-tolerant 3D architecture resembles a certain Roman monument.},
keywords = {Quantum complexity theory, Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
We present a computational problem with the following properties: (i) Every instance can be solved with near-certainty by a constant-depth quantum circuit using only nearest-neighbor gates in 3D, even when its implementation is corrupted by noise. (ii) Any constant-depth classical circuit composed of unbounded fan-in AND, OR, as well as NOT gates, i.e., an AC0-circuit, of size smaller than a certain subexponential, fails to solve a uniformly random instance with probability greater than a certain constant. Such an advantage against unbounded fan-in classical circuits was previously only known in the noise-free case or when ignoring locality constraints. By overcoming these limitations, we are thus proposing the strongest unconditional, fault-tolerant quantum-advantage demonstration to date. Subexponential circuit-complexity lower bounds have traditionally been referred to as exponential. We use the term colossal since our fault-tolerant 3D architecture resembles a certain Roman monument.
2.
Yijia Xu, Yixu Wang, Victor V. Albert
Clifford operations and homological codes for rotors and oscillators Talk
2024.
Abstract | Tags: Quantum error correction and fault-tolerant quantum computing
@Talk{T24_299,
title = {Clifford operations and homological codes for rotors and oscillators},
author = {Yijia Xu and Yixu Wang and Victor V. Albert},
year = {2024},
date = {2024-01-01},
abstract = {We develop quantum information processing primitives for the planar rotor, the state space of a particle on a circle. By interpreting rotor wavefunctions as periodically identified wavefunctions of a harmonic oscillator, we determine the group of bosonic Gaussian operations inherited by the rotor. This (n)-rotor Clifford group, (textU(1)^n(n+1)/2 rtimes textGL_n(mathbbZ)), is represented by continuous (textU(1)) gates generated by polynomials quadratic in angular momenta, as well as discrete (textGL_n(mathbb Z)) momentum sign-flip and sum gates. We classify homological rotor error-correcting codes arXiv:2303.13723 and various rotor states based on equivalence under Clifford operations. Reversing direction, we map homological rotor codes and rotor Clifford operations back into oscillators by interpreting occupation-number states as rotor states of non-negative angular momentum. This yields new multimode homological bosonic codes protecting against dephasing and changes in occupation number, along with their corresponding encoding and decoding circuits. In particular, we show how to non-destructively measure the oscillator phase using conditional occupation-number addition and post selection. We also outline several rotor and oscillator varieties of the GKP-stabilizer codes arXiv:1903.12615.},
keywords = {Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
We develop quantum information processing primitives for the planar rotor, the state space of a particle on a circle. By interpreting rotor wavefunctions as periodically identified wavefunctions of a harmonic oscillator, we determine the group of bosonic Gaussian operations inherited by the rotor. This (n)-rotor Clifford group, (textU(1)^n(n+1)/2 rtimes textGL_n(mathbbZ)), is represented by continuous (textU(1)) gates generated by polynomials quadratic in angular momenta, as well as discrete (textGL_n(mathbb Z)) momentum sign-flip and sum gates. We classify homological rotor error-correcting codes arXiv:2303.13723 and various rotor states based on equivalence under Clifford operations. Reversing direction, we map homological rotor codes and rotor Clifford operations back into oscillators by interpreting occupation-number states as rotor states of non-negative angular momentum. This yields new multimode homological bosonic codes protecting against dephasing and changes in occupation number, along with their corresponding encoding and decoding circuits. In particular, we show how to non-destructively measure the oscillator phase using conditional occupation-number addition and post selection. We also outline several rotor and oscillator varieties of the GKP-stabilizer codes arXiv:1903.12615.
3.
Satoshi Yoshida, Shiro Tamiya, Hayata Yamasaki
Concatenate codes, save qubits Talk
2024.
Abstract | Tags: Quantum error correction and fault-tolerant quantum computing
@Talk{T24_120,
title = {Concatenate codes, save qubits},
author = {Satoshi Yoshida and Shiro Tamiya and Hayata Yamasaki},
year = {2024},
date = {2024-01-01},
abstract = {The essential requirement for fault-tolerant quantum computation (FTQC) is the total protocol design to achieve a fair balance of all the critical factors relevant to its practical realization, such as the space overhead, the threshold, and the modularity. A major obstacle in realizing FTQC with conventional protocols, such as those based on the surface code and the concatenated Steane code, has been the space overhead, i.e., the required number of physical qubits per logical qubit. Protocols based on high-rate quantum low-density parity-check (LDPC) codes gather considerable attention as a way to reduce the space overhead, but problematically, the existing fault-tolerant protocols for such quantum LDPC codes sacrifice the other factors. Here we construct a new fault-tolerant protocol to meet these requirements simultaneously based on more recent progress on the techniques for concatenated codes rather than quantum LDPC codes, achieving a constant space overhead, a high threshold, and flexibility in modular architecture designs. In particular, under a physical error rate of 0.1%, our protocol reduces the space overhead to achieve the logical CNOT error rates $10^-10$ and $10^-24$ by more than 90% and 97%, respectively, compared to the protocol for the surface code. Furthermore, our protocol achieves the threshold of 2.4% under a conventional circuit-level error model, substantially outperforming that of the surface code. The use of concatenated codes also naturally introduces abstraction layers essential for the modularity of FTQC architectures. These results indicate that the code-concatenation approach opens a way to significantly save qubits in realizing FTQC while fulfilling the other essential requirements for the practical protocol design.},
keywords = {Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
The essential requirement for fault-tolerant quantum computation (FTQC) is the total protocol design to achieve a fair balance of all the critical factors relevant to its practical realization, such as the space overhead, the threshold, and the modularity. A major obstacle in realizing FTQC with conventional protocols, such as those based on the surface code and the concatenated Steane code, has been the space overhead, i.e., the required number of physical qubits per logical qubit. Protocols based on high-rate quantum low-density parity-check (LDPC) codes gather considerable attention as a way to reduce the space overhead, but problematically, the existing fault-tolerant protocols for such quantum LDPC codes sacrifice the other factors. Here we construct a new fault-tolerant protocol to meet these requirements simultaneously based on more recent progress on the techniques for concatenated codes rather than quantum LDPC codes, achieving a constant space overhead, a high threshold, and flexibility in modular architecture designs. In particular, under a physical error rate of 0.1%, our protocol reduces the space overhead to achieve the logical CNOT error rates $10^-10$ and $10^-24$ by more than 90% and 97%, respectively, compared to the protocol for the surface code. Furthermore, our protocol achieves the threshold of 2.4% under a conventional circuit-level error model, substantially outperforming that of the surface code. The use of concatenated codes also naturally introduces abstraction layers essential for the modularity of FTQC architectures. These results indicate that the code-concatenation approach opens a way to significantly save qubits in realizing FTQC while fulfilling the other essential requirements for the practical protocol design.
4.
Nadine Meister, Christopher Pattison, John Preskill
Efficient soft-output decoders for the surface code Talk
2024.
Abstract | Tags: Quantum error correction and fault-tolerant quantum computing
@Talk{T24_393,
title = {Efficient soft-output decoders for the surface code},
author = {Nadine Meister and Christopher Pattison and John Preskill},
year = {2024},
date = {2024-01-01},
abstract = {Decoders that provide an estimate of the probability of a logical failure conditioned on the error syndrome ("soft-output decoders") can reduce the overhead cost of fault-tolerant quantum memory and computation. In this work we construct efficient soft-output decoders for the surface code derived from the Minimum-Weight Perfect Matching and Union-Find decoders. We show that soft-output decoding can improve the performance of a "hierarchical code," a concatenated scheme in which the inner code is the surface code, and the outer code is a high-rate quantum low-density parity-check code. Alternatively, the soft-output decoding can improve the reliability of fault-tolerant circuit sampling by flagging those runs that should be discarded because the probability of a logical error is intolerably large.},
keywords = {Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
Decoders that provide an estimate of the probability of a logical failure conditioned on the error syndrome ("soft-output decoders") can reduce the overhead cost of fault-tolerant quantum memory and computation. In this work we construct efficient soft-output decoders for the surface code derived from the Minimum-Weight Perfect Matching and Union-Find decoders. We show that soft-output decoding can improve the performance of a "hierarchical code," a concatenated scheme in which the inner code is the surface code, and the outer code is a high-rate quantum low-density parity-check code. Alternatively, the soft-output decoding can improve the reliability of fault-tolerant circuit sampling by flagging those runs that should be discarded because the probability of a logical error is intolerably large.
5.
Michael Beverland, Vadym Kliuchnikov, Shilin Huang
Fault tolerance of stabilizer channels Talk
2024.
Abstract | Tags: Quantum error correction and fault-tolerant quantum computing
@Talk{T24_434,
title = {Fault tolerance of stabilizer channels},
author = {Michael Beverland and Vadym Kliuchnikov and Shilin Huang},
year = {2024},
date = {2024-01-01},
abstract = {Stabilizer channels, which are stabilizer circuits that implement logical operations while mapping from an input stabilizer code to an output stabilizer code, are ubiquitous for fault tolerant quantum computing not just with surface codes, but with general LDPC codes and Floquet codes. We introduce a rigorous and general formalism to analyze the fault tolerance properties of any stabilizer channel under a broad class of noise models. We provide rigorous but easy-to-work-with definitions and algorithms for the fault distance and hook faults for stabilizer channels. The generalized notion of hook faults which we introduce, defined with respect to an arbitrary subset of the circuit's faults rather than a fixed phenomenological noise model, can be leveraged for fault-tolerant circuit design. Additionally, we establish necessary conditions such that channel composition preserves the fault distance. We apply our framework to design and analyze fault tolerant stabilizer channels for surface codes, revealing novel aspects of fault tolerant circuits.},
keywords = {Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
Stabilizer channels, which are stabilizer circuits that implement logical operations while mapping from an input stabilizer code to an output stabilizer code, are ubiquitous for fault tolerant quantum computing not just with surface codes, but with general LDPC codes and Floquet codes. We introduce a rigorous and general formalism to analyze the fault tolerance properties of any stabilizer channel under a broad class of noise models. We provide rigorous but easy-to-work-with definitions and algorithms for the fault distance and hook faults for stabilizer channels. The generalized notion of hook faults which we introduce, defined with respect to an arbitrary subset of the circuit's faults rather than a fixed phenomenological noise model, can be leveraged for fault-tolerant circuit design. Additionally, we establish necessary conditions such that channel composition preserves the fault distance. We apply our framework to design and analyze fault tolerant stabilizer channels for surface codes, revealing novel aspects of fault tolerant circuits.
6.
Andreas Bauer
Fault-tolerant circuits from twisted quantum doubles – Quantum error correction beyond stabilizer and Clifford Talk
2024.
Abstract | Tags: Intersection of quantum information and condensed-matter theory, Quantum error correction and fault-tolerant quantum computing
@Talk{T24_407,
title = {Fault-tolerant circuits from twisted quantum doubles – Quantum error correction beyond stabilizer and Clifford},
author = {Andreas Bauer},
year = {2024},
date = {2024-01-01},
abstract = {We propose a family of explicit fault-tolerant geometrically local circuits realizing any abelian non-chiral topological phase. These circuits are constructed by relating them to discrete fixed-point path integrals, specifically the abelian Dijkgraaf-Witten state sum on a 3-dimensional cellulation, which is a spacetime representation of the twisted quantum double model. The resulting circuits are based on the well-known syndrome extraction circuit of the (qudit) toric code with $8$ controlled-$X$ gates per spacetime unit cell, into which we insert non-Pauli phase gates that implement the ``twist''. The overhead compared to the toric code is moderate, in contrast to the few known constructions for twisted abelian phases. The simplest example is a fault-tolerant circuit for the double-semion phase, which consists of $12$ controlled-$S$ gates in addition to the $8$ controlled-$X$ gates per spacetime unit cell. We also show that other architectures for the qudit toric code phase, like measurement-based topological quantum computation, or Floquet codes, can be equipped with phase gates implementing the twist. As a further result, we prove fault tolerance for a very general class of topological circuits that we call 1-form symmetric fixed-point circuits, which includes the circuits in this paper as well as the standard toric code, subsystem toric codes, measurement-based topological quantum computation, or the (CSS) honeycomb Floquet code. The noise model we use includes arbitrary local noise, including weakly correlated noise and non-Pauli noise, for which explicit fault-tolerance proofs might not exist in the literature to date. In the appendix we present a simple combinatorial procedure to define formulas for higher cup products on arbitrary cellulation, which might be interesting in its own right for the study of twisted gauge theory.},
keywords = {Intersection of quantum information and condensed-matter theory, Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
We propose a family of explicit fault-tolerant geometrically local circuits realizing any abelian non-chiral topological phase. These circuits are constructed by relating them to discrete fixed-point path integrals, specifically the abelian Dijkgraaf-Witten state sum on a 3-dimensional cellulation, which is a spacetime representation of the twisted quantum double model. The resulting circuits are based on the well-known syndrome extraction circuit of the (qudit) toric code with $8$ controlled-$X$ gates per spacetime unit cell, into which we insert non-Pauli phase gates that implement the ``twist''. The overhead compared to the toric code is moderate, in contrast to the few known constructions for twisted abelian phases. The simplest example is a fault-tolerant circuit for the double-semion phase, which consists of $12$ controlled-$S$ gates in addition to the $8$ controlled-$X$ gates per spacetime unit cell. We also show that other architectures for the qudit toric code phase, like measurement-based topological quantum computation, or Floquet codes, can be equipped with phase gates implementing the twist. As a further result, we prove fault tolerance for a very general class of topological circuits that we call 1-form symmetric fixed-point circuits, which includes the circuits in this paper as well as the standard toric code, subsystem toric codes, measurement-based topological quantum computation, or the (CSS) honeycomb Floquet code. The noise model we use includes arbitrary local noise, including weakly correlated noise and non-Pauli noise, for which explicit fault-tolerance proofs might not exist in the literature to date. In the appendix we present a simple combinatorial procedure to define formulas for higher cup products on arbitrary cellulation, which might be interesting in its own right for the study of twisted gauge theory.
7.
Christopher Pattison, Anirudh Krishna, John Preskill
Hierarchical memories: Simulating quantum LDPC codes with local gates Talk
2024.
Abstract | Tags: Quantum error correction and fault-tolerant quantum computing
@Talk{T24_390,
title = {Hierarchical memories: Simulating quantum LDPC codes with local gates},
author = {Christopher Pattison and Anirudh Krishna and John Preskill},
year = {2024},
date = {2024-01-01},
abstract = {Constant-rate low-density parity-check (LDPC) codes are promising candidates for constructing efficient fault-tolerant quantum memories. However, if physical gates are subject to geometric-locality constraints, it becomes challenging to realize these codes. In this paper, we construct a new family of [[N,K,D]] codes, referred to as hierarchical codes, that encode a number of logical qubits K = Omega(N/łog(N)^2). The N-th element of this code family is obtained by concatenating a constant-rate quantum LDPC code with a surface code; nearest-neighbor gates in two dimensions are sufficient to implement the corresponding syndrome-extraction circuit and achieve a threshold. Below threshold the logical failure rate vanishes superpolynomially as a function of the distance D(N). We present a bilayer architecture for implementing the syndrome-extraction circuit, and estimate the logical failure rate for this architecture. Under conservative assumptions, we find that the hierarchical code outperforms the basic encoding where all logical qubits are encoded in the surface code.},
keywords = {Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
Constant-rate low-density parity-check (LDPC) codes are promising candidates for constructing efficient fault-tolerant quantum memories. However, if physical gates are subject to geometric-locality constraints, it becomes challenging to realize these codes. In this paper, we construct a new family of [[N,K,D]] codes, referred to as hierarchical codes, that encode a number of logical qubits K = Omega(N/łog(N)^2). The N-th element of this code family is obtained by concatenating a constant-rate quantum LDPC code with a surface code; nearest-neighbor gates in two dimensions are sufficient to implement the corresponding syndrome-extraction circuit and achieve a threshold. Below threshold the logical failure rate vanishes superpolynomially as a function of the distance D(N). We present a bilayer architecture for implementing the syndrome-extraction circuit, and estimate the logical failure rate for this architecture. Under conservative assumptions, we find that the hierarchical code outperforms the basic encoding where all logical qubits are encoded in the surface code.
8.
Shin Ho Choe, Robert König
How to fault-tolerantly realize any quantum circuit with local operations Talk
2024.
Abstract | Tags: Quantum error correction and fault-tolerant quantum computing
@Talk{T24_439,
title = {How to fault-tolerantly realize any quantum circuit with local operations},
author = {Shin Ho Choe and Robert König},
year = {2024},
date = {2024-01-01},
abstract = {We propose a new scheme for transforming a general quantum circuit into a geometrically local quantum circuit with polynomial qubit overhead and constant circuit depth overhead. We show that our scheme preserves fault-tolerance of the input quantum circuit under local stochastic noise. As a corollary, we show that our scheme can be used as a black box to transform any fault-tolerance construction involving non-local operation into one which only involves geometrically local operations. That is, our transformation dispenses with the need for considering the locality of operations when designing schemes for fault-tolerant quantum information processing. Applied to recent fault-tolerance constructions, this gives a fault-tolerance threshold theorem for universal quantum computations with local operations, a polynomial qubit overhead and a quasi-polylogarithmic depth overhead. A key element for our construction is parallel repetition of fault-tolerant long-range entanglement generation.},
keywords = {Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
We propose a new scheme for transforming a general quantum circuit into a geometrically local quantum circuit with polynomial qubit overhead and constant circuit depth overhead. We show that our scheme preserves fault-tolerance of the input quantum circuit under local stochastic noise. As a corollary, we show that our scheme can be used as a black box to transform any fault-tolerance construction involving non-local operation into one which only involves geometrically local operations. That is, our transformation dispenses with the need for considering the locality of operations when designing schemes for fault-tolerant quantum information processing. Applied to recent fault-tolerance constructions, this gives a fault-tolerance threshold theorem for universal quantum computations with local operations, a polynomial qubit overhead and a quasi-polylogarithmic depth overhead. A key element for our construction is parallel repetition of fault-tolerant long-range entanglement generation.
9.
Allyson Silva, Xiangyi Zhang, Zachary Webb, Mia Kramer, Chan Woo Yang, Xiao Liu, Jessica Lemieux, Kawai Chen, Artur Scherer, Pooya Ronagh
Multi-qubit Lattice Surgery Scheduling Talk
2024.
Abstract | Tags: Proceedings, Quantum error correction and fault-tolerant quantum computing
@Talk{T24_426,
title = {Multi-qubit Lattice Surgery Scheduling},
author = {Allyson Silva and Xiangyi Zhang and Zachary Webb and Mia Kramer and Chan Woo Yang and Xiao Liu and Jessica Lemieux and Kawai Chen and Artur Scherer and Pooya Ronagh},
year = {2024},
date = {2024-01-01},
abstract = {Fault-tolerant quantum computation using two-dimensional topological quantum error correcting codes can benefit from multi-qubit long-range operations. By using simple commutation rules, a quantum circuit can be transpiled into a sequence of solely non-Clifford multi-qubit gates. Prior work on fault-tolerant compilation avoids optimal scheduling of such gates since they reduce the parallelizability of the circuit. We first show that, using the tableau representation of Clifford gates, this transpilation can be run in linear time with respect to the circuit length, and observe that the reduced parallelization potential is outweighed by the significant reduction in the number of gates. We therefore devise a method for scheduling multi-qubit lattice surgery using an earliest-available-first policy, solving the associated forest packing problem using a representation of the multi-qubit gates as Steiner trees. Our extensive testing on random and real-world circuits demonstrates the method's scalability and performance. We show that the transpilation reduces the circuit length by 82% on average, and that the resulting circuit of multi-qubit gates has an average reduction of 20.5% in the expected circuit execution time compared to serial execution.},
keywords = {Proceedings, Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
Fault-tolerant quantum computation using two-dimensional topological quantum error correcting codes can benefit from multi-qubit long-range operations. By using simple commutation rules, a quantum circuit can be transpiled into a sequence of solely non-Clifford multi-qubit gates. Prior work on fault-tolerant compilation avoids optimal scheduling of such gates since they reduce the parallelizability of the circuit. We first show that, using the tableau representation of Clifford gates, this transpilation can be run in linear time with respect to the circuit length, and observe that the reduced parallelization potential is outweighed by the significant reduction in the number of gates. We therefore devise a method for scheduling multi-qubit lattice surgery using an earliest-available-first policy, solving the associated forest packing problem using a representation of the multi-qubit gates as Steiner trees. Our extensive testing on random and real-world circuits demonstrates the method's scalability and performance. We show that the transpilation reduces the circuit length by 82% on average, and that the resulting circuit of multi-qubit gates has an average reduction of 20.5% in the expected circuit execution time compared to serial execution.
10.
Srinivasan Arunachalam, Vojtech Havlicek, Louis Schatzki
On the Role of Entanglement and Statistics in Learning Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Models of quantum computation, Quantum algorithms, Quantum complexity theory, Quantum error correction and fault-tolerant quantum computing
@Talk{T24_251,
title = {On the Role of Entanglement and Statistics in Learning},
author = {Srinivasan Arunachalam and Vojtech Havlicek and Louis Schatzki},
year = {2024},
date = {2024-01-01},
abstract = {We make progress in understanding the relationship between learning models with access to entangled, separable and statistical measurements in the quantum statistical query (QSQ) model. We show the following results. Entangled versus separable measurements: The goal is to learn an unknown f from the concept class C containing functions from 0,1^n to [k] given copies of a uniform superposition over |x,f(x)>. We show that, if T copies suffice to learn f using entangled measurements, O(nT^2) copies suffice to learn f using only separable measurements. Entangled versus statistical measurements: The goal is to learn a function f in C given access to separable measurements or statistical measurements. We exhibit a concept class C based of degree-2 functions with exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise). This proves the "quantum analogue" of the seminal result of Blum et al. that separates classical SQ learning from classical PAC learning with classification noise. QSQ lower bounds for learning states: We introduce a quantum statistical query dimension (QSD), and use it to give lower bounds on the QSQ complexity of learning. We prove superpolynomial QSQ lower bounds for testing purity of quantum states, shadow tomography, learning coset states for the Abelian hidden subgroup problem, degree-2 functions, planted biclique states, and learning output states of Clifford circuits of depth polylog(n). We also show that an extension of QSD characterizes the complexity of general search problems. Further applications: We give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model. Prior works by Quek et al., Hinsche et al., and Nietner et al. proved analogous results assuming diagonal measurements and our work removes this assumption.},
keywords = {Intersection of quantum information and machine learning, Models of quantum computation, Quantum algorithms, Quantum complexity theory, Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
We make progress in understanding the relationship between learning models with access to entangled, separable and statistical measurements in the quantum statistical query (QSQ) model. We show the following results. Entangled versus separable measurements: The goal is to learn an unknown f from the concept class C containing functions from 0,1^n to [k] given copies of a uniform superposition over |x,f(x)>. We show that, if T copies suffice to learn f using entangled measurements, O(nT^2) copies suffice to learn f using only separable measurements. Entangled versus statistical measurements: The goal is to learn a function f in C given access to separable measurements or statistical measurements. We exhibit a concept class C based of degree-2 functions with exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise). This proves the "quantum analogue" of the seminal result of Blum et al. that separates classical SQ learning from classical PAC learning with classification noise. QSQ lower bounds for learning states: We introduce a quantum statistical query dimension (QSD), and use it to give lower bounds on the QSQ complexity of learning. We prove superpolynomial QSQ lower bounds for testing purity of quantum states, shadow tomography, learning coset states for the Abelian hidden subgroup problem, degree-2 functions, planted biclique states, and learning output states of Clifford circuits of depth polylog(n). We also show that an extension of QSD characterizes the complexity of general search problems. Further applications: We give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model. Prior works by Quek et al., Hinsche et al., and Nietner et al. proved analogous results assuming diagonal measurements and our work removes this assumption.
11.
Shubham P. Jain, Joseph T. Iosue, Alexander Barg, Victor V. Albert
Quantum Spherical Codes Talk
2024.
Abstract | Tags: Quantum error correction and fault-tolerant quantum computing
@Talk{T24_354,
title = {Quantum Spherical Codes},
author = {Shubham P. Jain and Joseph T. Iosue and Alexander Barg and Victor V. Albert},
year = {2024},
date = {2024-01-01},
abstract = {We introduce a framework for constructing quantum codes defined on spheres by recasting such codes as quantum analogues of the classical spherical codes. We apply this framework to bosonic coding, obtaining multimode extensions of the cat codes that can outperform previous constructions while requiring a similar type of overhead. Our polytope-based cat codes consist of sets of points with large separation that at the same time form averaging sets known as spherical designs. We also recast concatenations of CSS codes with cat codes as quantum spherical codes, revealing a new way to autonomously protect against dephasing noise.},
keywords = {Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
We introduce a framework for constructing quantum codes defined on spheres by recasting such codes as quantum analogues of the classical spherical codes. We apply this framework to bosonic coding, obtaining multimode extensions of the cat codes that can outperform previous constructions while requiring a similar type of overhead. Our polytope-based cat codes consist of sets of points with large separation that at the same time form averaging sets known as spherical designs. We also recast concatenations of CSS codes with cat codes as quantum spherical codes, revealing a new way to autonomously protect against dephasing noise.
12.
Shouzhen Gu, Eugene Tang, Libor Caha, Shin Ho Choe, Zhiyang He, Aleksander Kubica
Single-shot decoding of good quantum LDPC codes Talk
2024.
Abstract | Tags: Quantum error correction and fault-tolerant quantum computing
@Talk{T24_146,
title = {Single-shot decoding of good quantum LDPC codes},
author = {Shouzhen Gu and Eugene Tang and Libor Caha and Shin Ho Choe and Zhiyang He and Aleksander Kubica},
year = {2024},
date = {2024-01-01},
abstract = {Quantum Tanner codes constitute a family of quantum low-density parity-check (LDPC) codes with good parameters, i.e., constant encoding rate and relative distance. In this work, we prove that quantum Tanner codes facilitate single-shot quantum error correction (QEC) where one measurement round (consisting of constant-weight parity checks) suffices to perform reliable QEC even in the presence of measurement errors. Importantly, this result holds for both the adversarial and stochastic noise. In our analysis, we consider the sequential and parallel decoding algorithms introduced by Leverrier and Zemor. Furthermore, we show that in order to suppress errors over multiple repeated rounds of QEC, it suffices to run the parallel decoding algorithm for constant time in each round. Combined with good code parameters, the resulting constant-time overhead of QEC and robustness to (possibly time-correlated) adversarial noise make quantum Tanner codes alluring from the perspective of quantum fault-tolerant protocols.},
keywords = {Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
Quantum Tanner codes constitute a family of quantum low-density parity-check (LDPC) codes with good parameters, i.e., constant encoding rate and relative distance. In this work, we prove that quantum Tanner codes facilitate single-shot quantum error correction (QEC) where one measurement round (consisting of constant-weight parity checks) suffices to perform reliable QEC even in the presence of measurement errors. Importantly, this result holds for both the adversarial and stochastic noise. In our analysis, we consider the sequential and parallel decoding algorithms introduced by Leverrier and Zemor. Furthermore, we show that in order to suppress errors over multiple repeated rounds of QEC, it suffices to run the parallel decoding algorithm for constant time in each round. Combined with good code parameters, the resulting constant-time overhead of QEC and robustness to (possibly time-correlated) adversarial noise make quantum Tanner codes alluring from the perspective of quantum fault-tolerant protocols.
13.
Noah Berthusen, Dhruv Devulapalli, Eddie Schoute, Andrew Childs, Michael Gullans, Alexey Gorshkov, Daniel Gottesman
Toward a 2D Local Implementation of Quantum LDPC Codes Talk
2024.
Abstract | Tags: Quantum error correction and fault-tolerant quantum computing
@Talk{T24_373,
title = {Toward a 2D Local Implementation of Quantum LDPC Codes},
author = {Noah Berthusen and Dhruv Devulapalli and Eddie Schoute and Andrew Childs and Michael Gullans and Alexey Gorshkov and Daniel Gottesman},
year = {2024},
date = {2024-01-01},
abstract = {Geometric locality is an important theoretical and practical factor for quantum low-density parity-check (qLDPC) codes which affects code performance and ease of physical realization. For device architectures restricted to 2D local gates, naively implementing the high-rate codes suitable for low-overhead fault-tolerant quantum computing incurs prohibitive amounts of overhead. In this work, we present an error correction protocol built on a bilayer architecture that aims to reduce operational overheads when restricted to 2D local gates by measuring some generators less frequently than others. We investigate the family of quasi-cyclic qLDPC codes and show that they are well suited for a parallel syndrome measurement scheme using fast local operations and classical communication (LOCC) routing. Through circuit-level simulations, we find that in some parameter regimes quasi-cyclic codes implemented with this protocol have logical error rates comparable to copies of the surface codes while using fewer physical qubits.},
keywords = {Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
Geometric locality is an important theoretical and practical factor for quantum low-density parity-check (qLDPC) codes which affects code performance and ease of physical realization. For device architectures restricted to 2D local gates, naively implementing the high-rate codes suitable for low-overhead fault-tolerant quantum computing incurs prohibitive amounts of overhead. In this work, we present an error correction protocol built on a bilayer architecture that aims to reduce operational overheads when restricted to 2D local gates by measuring some generators less frequently than others. We investigate the family of quasi-cyclic qLDPC codes and show that they are well suited for a parallel syndrome measurement scheme using fast local operations and classical communication (LOCC) routing. Through circuit-level simulations, we find that in some parameter regimes quasi-cyclic codes implemented with this protocol have logical error rates comparable to copies of the surface codes while using fewer physical qubits.
14.
Adam Wills, Ting-Chun Lin, Min-Hsiu Hsieh
Tradeoff Constructions for Quantum Locally Testable Codes Talk
2024.
Abstract | Tags: Quantum complexity theory, Quantum error correction and fault-tolerant quantum computing
@Talk{T24_15,
title = {Tradeoff Constructions for Quantum Locally Testable Codes},
author = {Adam Wills and Ting-Chun Lin and Min-Hsiu Hsieh},
year = {2024},
date = {2024-01-01},
abstract = {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 to prove the existence of codes in previously unknown parameter regimes. In particular, applications of these operations to the hypersphere product code and the hemicubic code yield many previously unknown parameters. Additionally, soundness amplification can be used to produce the first asymptotically good testable quantum code (rather than locally testable) - that being one with linear distance and dimension, as well as constant soundness. Lastly, applications of all three results are described to an upcoming work.},
keywords = {Quantum complexity theory, Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
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 to prove the existence of codes in previously unknown parameter regimes. In particular, applications of these operations to the hypersphere product code and the hemicubic code yield many previously unknown parameters. Additionally, soundness amplification can be used to produce the first asymptotically good testable quantum code (rather than locally testable) - that being one with linear distance and dimension, as well as constant soundness. Lastly, applications of all three results are described to an upcoming work.
15.
Zhenhuan Liu, Xingjian Zhang, Yue-Yang Fei, Zhenyu Cai
Virtual Channel Purification Talk
2024.
Abstract | Tags: Quantum algorithms, Quantum error correction and fault-tolerant quantum computing
@Talk{T24_316,
title = {Virtual Channel Purification},
author = {Zhenhuan Liu and Xingjian Zhang and Yue-Yang Fei and Zhenyu Cai},
year = {2024},
date = {2024-01-01},
abstract = {Quantum error mitigation is a key approach for extracting target state properties on state-of-the-art noisy machines and early fault-tolerant devices. Using the ideas from flag fault tolerance and virtual state purification, we develop the virtual channel purification (VCP) protocol, which consumes similar qubit and gate resources as virtual state purification but offers up to exponentially stronger error suppression with increased system size and more noisy operation copies. Furthermore, VCP removes most of the assumptions required in virtual state purification. Essentially, VCP is the first quantum error mitigation protocol that does not require specific knowledge about the noise models, the target quantum state, and the target problem while still offering rigorous performance guarantees for practical noise regimes. Further connections are made between VCP and quantum error correction to produce one of the first protocols that combine quantum error correction and quantum error mitigation beyond concatenation. We can remove all noise in the channel while paying only the same sampling cost as low-order purification, reaching beyond the standard bias-variance trade-off in quantum error mitigation. Our protocol can also be adapted to key tasks in quantum networks like channel capacity activation and entanglement distribution.},
keywords = {Quantum algorithms, Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
Quantum error mitigation is a key approach for extracting target state properties on state-of-the-art noisy machines and early fault-tolerant devices. Using the ideas from flag fault tolerance and virtual state purification, we develop the virtual channel purification (VCP) protocol, which consumes similar qubit and gate resources as virtual state purification but offers up to exponentially stronger error suppression with increased system size and more noisy operation copies. Furthermore, VCP removes most of the assumptions required in virtual state purification. Essentially, VCP is the first quantum error mitigation protocol that does not require specific knowledge about the noise models, the target quantum state, and the target problem while still offering rigorous performance guarantees for practical noise regimes. Further connections are made between VCP and quantum error correction to produce one of the first protocols that combine quantum error correction and quantum error mitigation beyond concatenation. We can remove all noise in the channel while paying only the same sampling cost as low-order purification, reaching beyond the standard bias-variance trade-off in quantum error mitigation. Our protocol can also be adapted to key tasks in quantum networks like channel capacity activation and entanglement distribution.
