10
talks
2
posters
9
committee roles
0
leadership roles
1998–2026
years active
Contributions
QIP QCrypt TQC presenter award · △program ◇steering ○organising □local · filled = chair
Talks
| Title | Conference | Type | Co-authors |
|---|---|---|---|
| Average-Case Hardness and Reducibility of Decoding Quantum Stabilizer Codes | QIP 2026 | regular | Andrey Khesin, Jonathan Z. Lu, Alexander Poremba, Yihui Quek, Akshar Ramkumar, Vinod Vaikuntanathan |
Random classical linear codes are widely believed to be hard to decode, exponentially so at constant coding rate. If the rate vanishes asymptotically sufficiently rapidly, slightly sub-exponential decoding algorithms are known. By contrast, the complexity of decoding a random quantum stabilizer code has remained an open question for quite some time. This work closes the gap in our understanding of the algorithmic hardness of decoding random quantum versus random classical codes. We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant rate—the maximally hard regime. This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem, and shows that any sub-exponential algorithm decoding a typical stabilizer code, at any coding rate, would immediately imply a breakthrough in cryptography.
More generally, we also characterize many other complexity-theoretic properties of stabilizer codes. While classical decoding admits a random self-reduction, we prove significant barriers for the existence of random self-reductions in the quantum case. This result follows from new bounds on Clifford entropies and Pauli mixing times, which may be of independent interest. As a complementary result, we demonstrate various other self-reductions which are in fact achievable, such as between search and decision. Our work also demonstrates several ways in which quantum phenomena, such as quantum degeneracy, force several reasonable definitions of stabilizer decoding—all of which are classically identical—to have distinct or non-trivially equivalent complexity. |
|||
| Bounding the classical capacity of a quantum channel assisted by classical feedback | TQC 2021 | regular | Dawei Ding, Sumeet Khatri, Yihui Quek, Xin Wang, Mark M. Wilde |
|
Power law violation of the area law in quantum spin chains ↗
|
QIP 2015 | regular | Ramis Movassagh |
|
Quantum interactive proofs with short messages ↗
|
QIP 2010 | regular | Salman Beigi, John Watrous |
| Quantum communication by erasure channel assisted by back classical communication | QIP 2006 | regular | Debbie Leung |
| Asymmetric unitary gate capacities | QIP 2006 | regular | Aram Harrow |
| Additivity questions in quantum information theory There are a number of interesting, open additivity questions in quantum information theory. Recently, I have been able to show that some of these are equivalent. I will discuss open additivity questions in general and this proof of equivalence in particular. Kiyoshi Tamaki: Unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel We prove the unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel. We assume that Alice has an ideal single photon source and Bob has detectors that discriminate between single photon states on one hand and vacuum state or multiphoton states on the other hand. We use a reduction to an entanglement distillation protocol initiated by a local filtering process in our proof. The bit errors and the phase errors are correlated after the filtering, and we can bound the amount of phase errors from the observed bit errors by an estimation method involving nonorthogonal measurements. Leslie Valiant: Holographic Algorithms John Watrous: Stronger Error Reduction for QMA The complexity class QMA is a bounded-error quantum computational variant of the class NP, where a quantum state plays the role of a certificate. It is known that the error of a given QMA protocol can be reduced exponentially at the cost of a polynomial increase in the length of the certificate. In this talk, I will prove that such a reduction in error is in fact possible with no increase in the length of the certificate whatsoever. Applications of this fact include a proof that logarithmic-length quantum certificates give no increase in power over BQP and a simple proof that QMA is contained in the class PP. Andreas Winter: From entanglement to secret key and back The last year has seen a series of dramatic progresses in the areas of quantum channel capacities, entanglement distillation and our understanding of how these problems relate to secret communication. In this talk I will first review the analogy between the theories of entanglement and key distillation. Then I go on to explain the elements of the recent progress, first describing Devetak's recent reduction of quantum state transmission to private communication and our subsequent joint work generalising this to entanglement/secret key distillation. These findings put into a new light the earlier observations (by Acin et al.and Bruss et al.) of qualitative equivalence between these two tasks, and also prepared the ground for the recent step forward by Horodecki et al., to formulate key distillation strictly within the LOCC paradigm and then to exhibit bound entangled states which nevertheless contain secret key. Contributed Talks Howard Barnum: Query complexity & semidefinite programming We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we do the following: We show that as far as query complexity is concerned, the workspace of a quantum computer used to evaluate f(x) by querying the bits of an n-bit string x can be limited to n + k, where f takes k bit strings as values. We give an algorithm that on input the truth table of a partial boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm that attempts to evaluate f in t queries. We use semidefinite programming duality to formulate a dual SDP Phat(f, t, e) that is feasible if and only if f cannot be avluated within error e by a t-step quantum query algorithm. Using this SDP we derive a general lower bound for query complexity that encompasses a lower bound method of Ambainis and its generalizations. We give an interpretation of the primal SDP as a generalized form of branching in quantum computation. (This is joint work with Mike Saks and Mario Szegedy.) Matthias Christandl: A new generic proof for the security of quantum key distribution We present a new proof for the security of quantum key distribution. The presented proof is general in nature and applies to prepare-and-measure protocols such as BB84 as well as entanglement-based quantum cryptography such as E91. We use techniques that do not relate to entanglement distillation and thus differ significantly from all known security proofs. In order to derive a general security threshold we apply the recent result on privacy amplification in the presence of a quantum mechanical adversary by König, Maurer and Renner (2003). (This is joint work with Artur Ekert and Renato Renner.) Christoph Durr: Quantum query complexity of some graph problems Quantum algorithms for graph problems are considered, both in the adjacency matrix query model and in an adjacency list-like array model. We give almost tight lower and upper bounds for Connectivity, Strong Connectivity, Minimum Spanning Tree and Single Source Shortest Paths. (This is joint work with Mark Heiligman, Peter Hoyer, Mehdi Mhalla, and Yahui Lei.) Ivette Fuentes-Guridi: Holonomic quantum computation in the presence of decoherence We investigate the effects of decoherence in the geometric evolution of states of a degenerate quantum system. This is done by generalizing the scheme for geometric phases in open systems to non-Abelian holonomies. The formalism is applied to estimate the errors produced by performing an universal set of holonomic quantum gates in the presence of an environment. We pinpoint the single source of error in the scheme that must be corrected to achieve holonomic quantum computation completely robust to decoherence. Aram Harrow: Coherent communication of classical messages I define coherent communication in terms of a simple primitive, show it is equivalent to the ability to send a classical message with a unitary or isometric operation, and use it to relate other resources in quantum information theory. Using coherent communication, I can generalize super-dense coding to prepare arbitrary quantum states instead of only classical messages. I also derive single-letter formulae for the classical and quantum capacities of a bipartite unitary gate assisted by an arbitrary fixed amount of entanglement per use. Louis Kauffman: Braiding operators and quantum computing This talk will prove that there is a universal set of gates for quantum computing consisting in A single unitary solution R to the Yang-Baxter equation. Local unitary single qubit operations. The matrix R is the change of basis matrix taking the standard basis of a 2-qubit vector space to the Bell basis. This matrix is not only a unitary solution to the Yang-Baxter equation, it also gives rise to an interesting invariant of knots and links. This talk will pivot on this Theorem and discuss relationships between braids, knots, topological and quantum entanglement and quantum computing. From the point of view of this Theorem, any quantum computer can be configured as representation of an element in a generalization of the Artin Braid group. (This is joint work with Sam Lomonaco.) Sophie Laplante: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments We prove a very general lower bound technique for quantum and randomized query complexity that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted, unweighted methods of Ambainis, and the spectral method of Barnum, Saks, and Szegedy. As an immediate consequence of our main theorem, adversary methods can only prove lower bounds for Boolean functions f in O(min(sqrt{n C0(f)}, sqrt{n C1(f)})), where C0, C1 is the certificate complexity, and n is the size of the input. We also derive a general form of the ad hoc weighted method used by Hoyer, Neerbek, and Shi to give a quantum lower bound on ordered search and sorting. Reference: quant-ph/0311189 (This is joint work with Frederic Magniez.) David Poulin: Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect We present an efficient quantum algorithm to measure the average fidelity decay of a quantum map under perturbation using a single bit of quantum information. Our algorithm scales only as the complexity of the map under investigation, so for those maps admitting an efficient gate decomposition, it provides an exponential speed-up over known classical procedures. Fidelity decay is important in the study of complex dynamical systems, where it is conjectured to be a signature of quantum chaos. Our result also illustrates the role of chaos in the process of decoherence. Barry Sanders: Sharing secret quantum states: theory and experiment Threshold quantum secret sharing enables a quantum state to be transmitted to multiple players who cannot be trusted, whereas certain groups of players can be trusted. Quantum secrets may need to be shared for distributed quantum computing protocols, for quantum communication where trust is an issue, and for distributing quantum money, for example. I explain threshold quantum secret sharing, discuss continuous variable threshold quantum secret sharing, and present results of a recent successful threshold quantum secret sharing experiment implemented in a continuous variable system. Daniel Terno: Quantum information and special relativity Relativistic effects affect nearly all notions of quantum information theory. The vacuum behaves as a noisy channel, even if the detectors are perfect. The standard definition of a reduced density matrix fails for photon polarization because the transversality condition behaves like a superselection rule. We can, however, define an effective reduced density matrix which corresponds to a restricted class of positive operator-valued measures. There are no pure photon qubits, and no exactly orthogonal qubit states. Reduced density matrices for the spin of massive particles are well-defined, but are not covariant under Lorentz transformations. The spin entropy is not a relativistic scalar and has no invariant meaning. The distinguishability of quantum signals and their entanglement depend on the relative motion of observers. Posters Charlene Ahn Quantum error correction for continuously detected errors Muhammed Sabieh Anwar Preparing pure initial states from para-hydrogen Anne Braodbent Multi-party pseudo-telepathy Hilary Carteret Exact asymptotics for the quantum walk on the line Circuits for the direct detection of entanglement without the addition of noise Kai Chen A matrix realignment method for recognizing entanglement Donny Cheung Improved bounds for approximate quantum Fourier transforms Sora Choi Quantum key distribution network between various groups Igor Devatek Triple trade-offs in quantum Shannon theory Leonid Fedichkin Additivity of decoherence measures for multiqubit quantum systems Stephen Fenner Implementing the fanout gate by a Hamiltonian The power of constant-depth quantum circuits Fanout is hard to implement in constant with generalized Toffoli gates Jose Fernandez Quantum circuits for discrete logarithms on Galois Fields Theoretical methods and experimental implementations of non-adiabatic (heat bath) algorithmic cooling Ivette Fuentes-Guridi Holonomic quantum computation in the presence of decoherence Jim Harrington Local rules for protecting topological quantum memory Lawrence Ioannou Detecting entanglement with partial information Kazuo Iwama Quantum oracle computation with and without noises Phil Kaye Efficient implementation of quantum discrete logarithm algorithms on elliptic curves over extensions of GF(2) Viv Kendon Entanglement in Shor's algorithm Avanti Ketkar & Santosh Kumar Bounds on stabilizer codes over GF(q 2 ) Andreas Klappenecker Mutually unbiased bases Takeshi Koshiba Characterizing the existence of quantum one-way permutations Jozef Kosik Scattering model of quantum random walk Vasilijs Kravcevs Boolean function computation by probabilistic and quantum decision trees Maksim Kravtsev Models of probabilistic reversible automata and quantum counterparts Keiji Matsumoto Additivity of Holevo capacity and strong converse of channel capacity and entanglement dilution Carlos Mochon Computing with anyons Masoud Mohseni Optical realization of optimal unambiguous discrimination for pure and mixed quantum states Mio Murao LOCC extraction of distributed quantum information Falk Niehoerster & Helge Rose The Fraunhofer Quantum Computing Services - A parallel simulator of quantum computing processes Harold Ollivier Quantum convolutional coding Tobias Osborne The propagation of quantum information through a spin system Michel Pioro-Ladriere Electron Spin based qubits in lateral gated quantum dots Sergio de Rinaldis Distinguishability of complete and unextendible product bases David Roberts Non-local correlations as information theoretic resources Jeremie Roland Robustness to noise of Hamiltonian search algorithms David Santos Optimal strategies in quantum message authentication Toshiyuki Shimono Numerical test of superadditivity of entanglement of formation for four-qubit states Marcus Silva Erasure thresholds for efficient linear optics quantum computing Graeme Smith Efficient multiparty quantum data hiding Won Min Son D-outcome measurement for a nonlocality test Rob Spekkens The cryptographic power of private shared reference frames Krysta Svore Compiling quantum computations into elementary operations Christino Tamon A note on graphs resistant to quantum uniform mixing Yuuki Tokunaga Anonymous quantum cash Ben Toner Quantifying and generalizing the Kochen-Specker theorem Nicholas Whitlock A theory for matter-wave detection | QIP 2004 | invited | — |
| The Quantum Reverse Shannon Theorem | QIP 2002 | invited | — |
| EPR assisted capacity of a quantum channel | QIP 2000 | invited | — |
| Tutorial: Quantum error correction | QIP 1999 | invited | — |
I will explain how quantum error correcting codes work, using a few simple examples, and introduce some of the general theory of quantum error correction. |
|||
Posters
| Title | Conference | Co-authors |
|---|---|---|
| Universal graph representation of stabilizer codes | QIP 2025 | Andrey Boris Khesin, Jonathan Z. Lu |
| A Discrete Fourier Transform on Lattices with Quantum Applications | QCRYPT 2017 | Lior Eldar |
Committee service
| Conference | Committee | Position | Title |
|---|---|---|---|
| QIP 2024 | PC | member | — |
| QIP 2021 | PC | member | — |
| QIP 2012 | PC | member | — |
| QIP 2011 | PC | member | — |
| QIP 2009 | SC | member | — |
| QIP 2008 | SC | member | — |
| QIP 2007 | SC | member | — |
| QIP 1999 | PC | member | — |
| QIP 1998 | OC | member | — |
Collaborators
| Co-author | Joint talks |
|---|---|
| Jonathan Z. Lu | 2 |
| Yihui Quek | 2 |
| Akshar Ramkumar | 1 |
| Alexander Poremba | 1 |
| Andrey Boris Khesin | 1 |
| Andrey Khesin | 1 |
| Aram Harrow | 1 |
| Dawei Ding | 1 |
| Debbie Leung | 1 |
| John Watrous | 1 |
| Lior Eldar | 1 |
| Mark M. Wilde | 1 |
| Ramis Movassagh | 1 |
| Salman Beigi | 1 |
| Sumeet Khatri | 1 |
| Vinod Vaikuntanathan | 1 |
| Xin Wang | 1 |