Events

The Clifford theory of the n-qubit Clifford group

Quantum-Nano Centre, 200 University Ave West, Room QNC 1201 Waterloo, ON CA N2L 3G1

The n-qubit Pauli group and its normalizer the n-qubit Clifford group have applications in quantum error correction and device characterization. Recent applications have made use of the representation theory of the Clifford group. We apply the tools of (the coincidentally named) Clifford theory to examine the representation theory of the Clifford group using the much simpler representation theory of the Pauli group. We find an unexpected correspondence between irreducible characters of the n-qubit Clifford group and those of the (n + 1)-qubit Clifford group. This talk will rely on the explanation of Clifford theory given last week.

CS/Math Seminar - Kunal Marwaha - University of Chicago

200 University Ave. Waterloo ON. QNC 1201 + ZOOM

We study a variant of QMA where quantum proofs have non-negative amplitudes in both completeness and soundness. This class was introduced by Jeronimo and Wu [STOC '23] to understand QMA(2). We show that this variant is very powerful even without considering multiple unentangled quantum provers. In fact, QMA+ with some constant gap is equal to NEXP, even though QMA+ with some other constant gap is equal to QMA.

IQC Special Colloquium - Aziza Suleymanzade, Harvard University

200 University Ave W. Waterloo ON - ZOOM only

The experimental development of quantum networks marks a significant scientific milestone, poised to enable secure quantum communication, distributed quantum computing, and entanglement-enhanced nonlocal sensing. In this talk, I will discuss the recent advancements in the field along with the outstanding challenges through my work on two different platforms: Silicon Vacancy defects in diamond nanophotonic cavities and Rydberg atoms coupled to hybrid cavities. First, I will present our recent results on distributing entanglement across a two-node network with on-chip solid-state defects in cavities which we built at Harvard. We demonstrated high-fidelity entanglement between communication and memory qubits and showed long-distance entanglement over the 35 km of deployed fiber in the Cambridge/Boston area. Second, I will describe our work at the University of Chicago on using Rydberg atoms as transducers of quantum information between optical and microwave photons, with the goal of integrating Rydberg platforms with superconducting circuits and paving the way for advanced quantum network architectures. The talk will conclude with a perspective on the potential of this hybrid platform approach in constructing quantum networks, highlighting the uncharted scientific and technological opportunities it could unlock.

CS/Math Seminar - Nolan Coble - University of Maryland, College Park

200 University Ave. Waterloo ON. QNC 1201 + ZOOM

The recent resolution of the NLTS Conjecture [ABN22] establishes a prerequisite to the Quantum PCP (QPCP) Conjecture through a novel use of newly-constructed QLDPC codes [LZ22]. Even with NLTS now solved, there remain many independent and unresolved prerequisites to the QPCP Conjecture, such as the NLSS Conjecture of [GL22]. In this talk we focus on a specific and natural prerequisite to both NLSS and the QPCP Conjecture, namely, the existence of local Hamiltonians whose low-energy states all require ω(log n) T gates to prepare. In fact, we will show a stronger result which is not necessarily implied by either conjecture: we construct local Hamiltonians whose low-energy states require Ω(n) T gates. We further show that our procedure can be applied to the NLTS Hamiltonians of [ABN22] to yield local Hamiltonians whose low-energy states require both Ω(log n)-depth and Ω(n) T gates to prepare. This result represents a significant improvement over [CCNN23] where we used a different technique to give an energy bound which only distinguishes between stabilizer states and states which require a non-zero number of T gates.

Special Colloquium - Zhi Li, Perimeter Institute

University of Waterloo 200 University Ave. W Waterloo QNC 0101

Quantum error-correcting codes play a pivotal role in enabling fault-tolerant quantum computation. These codes protect quantum information through intricately designed redundancies that encode the information in a global manner. Unlike classical objects, in a quantum error-correcting code, the knowledge of individual subregions, even when combined, reveals nothing about the overall state.

In this talk, we explore the quantification of how far quantum error-correcting code are from classical states. We examine this question from three different perspectives: circuit complexity (the mimimal number of circuit depth needed to prepare a quantum state), expansion number (the minimal number of terms needed to expand the wavefunction), and a quantity we termed product overlap, which characterizes the maximal overlap between a given state and any product state. We will demonstrate why any quantum error-correcting code states must exhibit exponentially small product overlap, and how it implies lower bounds for the circuit complexity and the expansion number.

Math CS Seminar - Jinge Bao, National University of Singapore

200 University Ave W. Waterloo - ZOOM

We initiate a systematic study of the time complexity of quantum divide and conquer algorithms for classical problems. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup and apply these theorems to an array of problems involving strings, integers, and geometric objects. They include LONGEST DISTINCT SUBSTRING, KLEE'S COVERAGE, several optimization problems on stock transactions, and k-INCREASING SUBSEQUENCE. For most of these results, our quantum time upper bound matches the quantum query lower bound for the problem, up to polylogarithmic factors.

https://arxiv.org/abs/2311.16401

Improving the Fidelity of CNOT Circuits on NISQ Hardware

Quantum-Nano Centre, 200 University Ave West, Room QNC 1201 Waterloo, ON CA N2L 3G1

We introduce an improved CNOT synthesis algorithm that considers nearest-neighbour interactions and CNOT gate error rates in noisy intermediate-scale quantum (NISQ) hardware. Our contribution is twofold. First, we define a \Cost function by approximating the average gate fidelity Favg. According to the simulation results, \Cost fits the error probability of a noisy CNOT circuit, Prob = 1 - Favg, much tighter than the commonly used cost functions. On IBM's fake Nairobi backend, it fits Prob with an error at most 10^(-3). On other backends, it fits Prob with an error at most 10^(-1). \Cost accounts for the machine calibration data, and thus accurately quantifies the dynamic error characteristics of a NISQ-executable CNOT circuit. Moreover, it circumvents the computation complexity of calculating Favg and shows remarkable scalability. 

Second, we propose an architecture-aware CNOT synthesis algorithm, NAPermRowCol, by adapting the leading Steiner-tree-based synthesis algorithms. A weighted edge is used to encode a CNOT gate error rate and \Cost-instructed heuristics are applied to each reduction step. Compared to IBM's Qiskit compiler, it reduces \Cost by a factor of 2 on average (and up to a factor of 8.8). It lowers the synthesized CNOT count by a factor of 13 on average (up to a factor of 162). Compared with algorithms that are noise-agnostic, it is effective and scalable to improve the fidelity of CNOT circuits. Depending on the benchmark circuit and the IBM backend selected, it lowers the synthesized CNOT count up to 56.95% compared to ROWCOL and up to 21.62% compared to PermRowCol. It reduces the synthesis \Cost up to 25.71% compared to ROWCOL and up to 9.12% compared to PermRowCol. NAPermRowCol improves the fidelity and execution time of a synthesized CNOT circuit across varied NISQ hardware. It does not use ancillary qubits and is not restricted to certain initial qubit maps. It could be generalized to route a more complicated quantum circuit, and eventually boost the overall efficiency and accuracy of quantum computing on NISQ devices. 

Joint-work with: Dohun Kim, Minyoung Kim, and Michele Mosca

IQC Colloquium - Daniel Carney, Berkeley Labs

200 University Ave. W. Waterloo Ontario, QNC 0101

The search for new fundamental physics -- particles, fields, new objects in the sky, etc -- requires a relentless supply of more and more sensitive detection modalities. Experiments looking for new physics are starting to regularly encounter noise sources generated by the quantum mechanics of measurement itself. This noise now needs to be engineered away. The search for gravitational waves with LIGO, and their recent use of squeezed light, provides perhaps the most famous example. More broadly, searches for various dark matter candidates, precision nuclear physics, and even tests of the quantization of gravity are all now working within this quantum-limited regime of measurement. In this talk, I will give an overview of this set of ideas, focusing on activity going on now and what can plausibly be achieved within the next decade or so.

The (Quantum) Signal and the Noise: towards the intermediate term of quantum computation

University of Waterloo, 200 University Ave West QNC 0101 + ZOOM

Can we compute on small quantum processors? In this talk, I explore the extent to which noise presents a barrier to this goal by quickly drowning out the information in a quantum computation. Noise is a tough adversary: we show that a large class of error mitigation algorithms -- proposals to "undo" the effects of quantum noise through mostly classical post-processing – can never scale up. Switching gears, we next explore the effects of non-unital noise, a physically natural (yet analytically difficult) class of noise that includes amplitude-damping and photon loss. We show that it creates effectively shallow circuits, in the process displaying the strongest known bound on average convergence of quantum states under such noise. Concluding with the computational complexity of learning the outputs of small quantum processors, I will set out a program for wrapping these lower bounds into new directions to look for near-term quantum computational advantage. 

IQC Seminar - Ashutosh Marwah, University of Montreal

Quantum-Nano Centre, 200 University Ave West, Room QNC 1201
Waterloo, ON CA N2L 3G1

For a state $\rho_{A_1^n B}$, we call a sequence of states $(\sigma_{A_1^k B}^{(k)})_{k=1}^n$ an approximation chain if for every $1 \leq k \leq n$, $\rho_{A_1^k B} \approx_\epsilon \sigma_{A_1^k B}^{(k)}$. In general, it is not possible to lower bound the smooth min-entropy of such a $\rho_{A_1^n B}$, in terms of the entropies of $\sigma_{A_1^k B}^{(k)}$ without incurring very large penalty factors. In this paper, we study such approximation chains under additional assumptions. We begin by proving a simple entropic triangle inequality, which allows us to bound the smooth min-entropy of a state in terms of the R\'enyi entropy of an arbitrary auxiliary state while taking into account the smooth max-relative entropy between the two. Using this triangle inequality, we create lower bounds for the smooth min-entropy of a state in terms of the entropies of its approximation chain in various scenarios. In particular, utilising this approach, we prove approximate versions of the asymptotic equipartition property and entropy accumulation. In a companion paper, we show that the techniques developed in this paper can be used to prove the security of quantum key distribution in the presence of source correlations.