Schedule for: 24w4006 - Frontiers of Quantum information and Computation

Hotel address:
The Marina Mall,
13/1A, OMR, Near Navalur Toll,
Egattur, Chennai,
Tamil Nadu - 603103.

https://www.royalorchidhotels.com/regenta-central-rs-chennai/overview

Meet at the hotel lobby

Bell non-locality is a fundamental feature of quantum mechanics whereby measurements performed on "spatially separated" quantum systems can exhibit correlations that cannot be understood as revealing predetermined values. This is a special case of the more general phenomenon of "quantum contextuality", which says that such correlations can occur even when the measurements are not necessarily on separate quantum systems, but are merely "compatible" (i.e. commuting). Crucially, while any non-local game yields an experiment that demonstrates quantum advantage by leveraging the "spatial separation" of two or more devices (and in fact several such demonstrations have been conducted successfully in recent years), the same is not true for quantum contextuality: finding the contextuality analogue of such an experiment is arguably one of the central open questions in the foundations of quantum mechanics.

In this work, we show that an arbitrary contextuality game can be compiled into an operational "test of contextuality" involving a single quantum device, by only making the assumption that the device is computationally bounded. Our work is inspired by the recent work of Kalai et al. (STOC '23) that converts any non-local game into a classical test of quantum advantage with a single device. The central idea in their work is to use cryptography to enforce spatial separation within subsystems of a single quantum device. Our work can be seen as using cryptography to enforce "temporal separation", i.e. to restrict communication between sequential measurements. Beyond contextuality, we employ our ideas to design a "proof of quantumness" that, to the best of our knowledge, is arguably even simpler than the ones proposed in the literature so far.

Uncloneability is one of the most remarkable properties of quantum states that separates them from classical information. Over the years, this property has found numerous uses in cryptography - many tasks that are classically impossible become possible in quantum cryptography due to uncloneability. In this talk, we examine the utility of uncloneable quantum states in complexity theory, specifically in the form of proofs and advice.

We define and study languages that necessarily need uncloneable quantum proofs and advice. We define strictly uncloneable versions of the classes QMA, BQP/qpoly and FEQP/qpoly (which is the class of relational problems solvable exactly with polynomial-sized quantum advice). Strictly uncloneable QMA is defined to be the class of languages in QMA that only have uncloneable proofs, i.e., given any family of candidate proof states, a polynomial-time cloning algorithm cannot act on it to produce states that are jointly usable by $k$ separate polynomial-time verifiers, for arbitrary polynomial $k$. This is a stronger notion of uncloneable proofs and advice than those considered in previous works, which only required the existence of a single family of proof or advice states that are uncloneable. We show that in the quantum oracle model, there exist languages in strictly uncloneable QMA and strictly uncloneable BQP/qpoly. The language in strictly uncloneable QMA also gives a quantum oracle separation between QMA and the class cloneableQMA introduced by Nehoran and Zhandry (2024). We also show without using any oracles that the language used by Aaronson, Buhrman and Kretschmer (2024) to separate FEQP/qpoly and FBQP/poly, is in strictly uncloneable FEQP/qpoly.

Based on joint work with Rohit Chatterjee and Supartha Podder.

Random classical codes have good error correcting properties, and yet they are notoriously hard to decode in practice. Despite many decades of extensive study, the fastest known algorithms still run in exponential time. The Learning Parity with Noise (LPN) problem, which can be seen as the task of decoding a random linear code in the presence of noise, has thus emerged as a prominent hardness assumption with numerous applications in both cryptography and learning theory. Is there a natural quantum analog of the LPN problem? In this work, we introduce the Learning Stabilizers with Noise (LSN) problem, the task of decoding a random stabilizer code in the presence of local depolarizing noise, and give evidence of its hardness as well as applications in both learning theory and cryptography. 

Location will be announced at the start of each workshop.

In this talk, we will discuss the impact of quantum information on cryptography, both in terms of achieving cryptographic tasks beyond the limits of classical computation as well as the interesting anomalies arising in the quantum cryptographic landscape, which is in stark contrast to classical cryptography. In particular, we will discuss the main results and open questions in unclonable cryptography, a subfield of quantum cryptography that does not have a classical cryptographic analog. Next, we will review recent developments concerning the possibility of cryptography without one-way functions and the question of minimal assumption in quantum cryptography.

We investigate the quantum security of key-alternating ciphers (KAC), a generalization of Even-Mansour ciphers extended over multiple rounds. KAC serves as a model for many block cipher constructions, including widely used ciphers like AES. While there is a substantial body of work on the classical security of KAC, little is understood about its resilience against quantum adversaries.

In this talk, we present the first non-trivial quantum key-recovery attack on multi-round KAC in a setting where the adversary has quantum access to just one of the public permutations. This attack, which works for any $t$-round KAC, achieves a quantum query complexity of $O(2^{\frac{t(t+1)n}{(t+1)^2+1}})$, where $n$ is key size. For comparison, the best-known classical attack requires $O(2^{\frac{tn}{(t+1)}})$ queries, as established by Bogdanev et al. (EUROCRYPT 2012). Our approach employs a novel use of MNRS-style quantum walk algorithms by Magniez et al. (STOC 2007), which may have further applications in quantum cryptanalysis.

Moreover, by leveraging a hybrid quantum-classical attack model, we extend the classical Even-Mansour lower bound for $t$-round KACs, from $\Omega(2^{\frac{n}{3}})$ as shown by Alagic et al. (EUROCRYPT 2022), to a tighter bound of $\Omega(2^{\frac{(t-1)n}{t}})$ for $t \geq 2$. This work enhances our understanding of the limitations and vulnerabilities of classical cipher constructions in the presence of quantum adversaries, with potential implications for future block cipher designs in the quantum era.

The talk is based on joint work with Chen Bai and Mehdi Esmaili.

One-way state generators (OWSG) are natural quantum analogs to classical one-way functions. We consider statistically-verifiable OWSGs (sv-OWSG), which are potentially weaker objects than OWSGs. We show that O(n/log(n))-copy sv-OWSGs (n represents the input length) are equivalent to poly(n)-copy sv-OWSGs and to quantum commitments. Since known results show that o(n/log(n))-copy OWSGs cannot imply commitments, this shows that O(n/log(n))-copy sv-OWSGs are the weakest OWSGs from which we can get commitments (and hence much of quantum cryptography).

Our construction follows along the lines of Hastad, Impagliazzo, Levin and Luby [HILL99], who obtained classical pseudorandom generators (PRG) from classical one-way functions (OWF), however with crucial modifications. Our construction, when applied to the classical case, provides an alternative to the classical construction to obtain a classical mildly non-uniform PRG from any classical OWF. Since we do not argue conditioned on the output f(x), our construction and analysis is arguably simpler and may be of independent interest. For converting a mildly non-uniform PRG to a uniform PRG, we can use the same construction as [HILL99].

Almost all known QKD protocols use two way communication, including the earliest and most famous one viz. BB84. Also most known QKD protocols have an information reconciliation step where Alice and Bob go from there respective raw keys, which are slightly different due to Eve's actions, to their reconciled raw keys which are exactly the same. No efficient algorithm for information reconciliation is known. All experimental implementations of QKD suffer significant channel losses, which have to be handled by two way communication.

One way QKD becomes important in some critical / military scenarios. The one way protocol should be practical i.e. designed for today's hardware, resilient i.e. able to handle realistic amount of channel losses and Eve's eavesdropping, and efficient i.e every aspect of the protocol from end to end should be implementable in classical polynomial time.

  We design a strictly one way QKD protocol that achieves all the above requirements. Using the 4 BB84 states, it can tolerate up to 25% losses without eavesdropping bit errors, or 4%  bit errors without losses. A tradeoff exists between losses and bit errors e.g. loss of 10% and bit error of 1% is tolerable which is a realistic figure. In addition, our information reconciliation subroutine can be plugged into existing QKD protocols like BB84, making them fully efficient for the first time. We also obtain extensions to our protocol using the standard set of six states.

This is joint work with Sayantan Chakraborty and Upendra Kapshikar.

In this talk, we survey some recent results in quantum secure non-malleable cryptography. We look at some recent constructions of non-malleable extractors and their applications in privacy amplification (e.g. for QKD), constructing non-malleable randomness-encoders, non-malleable codes, and non-malleable secret sharing schemes (both for classical and quantum secrets). 

Talk based on: ArXiv:2308.06466 (TCC 2024), ArXiv: 2308.07340 (QCrypt 2023), ArXiv:2202.13354 (IEEE-T-IT 2023), ArXiv:2109.03097 (TQC 2023) and ArXiv:2106.02766 (IEEE-T-IT 2023).

Meet at the hotel lobby

Quantum complexity is emerging as a key feature of many-body systems, including early quantum computers, black holes, and topological materials. A state’s quantum complexity quantifies the difficulty of preparing the state from a simple tensor product, or the difficulty of uncomputing the state to a simple tensor product. The greater a state’s distance from maximal complexity, or “uncomplexity,” the more useful the state is as input to a quantum computation. Separately, resource theories—simple models for agents subject to constraints—are burgeoning in quantum information theory. I will unite the two domains, meeting Brown and Susskind’s long-standing challenge to construct a resource theory of uncomplexity. I will present the resource theory’s definition, two operational tasks analyzable in the theory, and monotones (resource-theory measures of a state’s usefulness). This work brings to many-body complexity a powerful mathematical and conceptual toolkit from quantum information theory.

References
1) NYH, Kothakonda, Haferkamp, Munson, Eisert, and Faist, Phys. Rev. A 106, 062417 (2022).
2) Munson, Kothakonda, Haferkamp, NYH, Eisert, and Faist, arXiv:2403.04828 (2024).
3) Haferkamp, Kothakonda, Faist, Eisert, and NYH, Nat. Phys. (2022).

Quantum systems are prone to environmental interactions that lead to faults in a computation process, posing significant engineering roadblocks for building large-scale quantum computers. Quantum error correction (QEC) provides a theoretical framework to ensure that logical operations can performed reliably in the presence of noise. However, many of these theoretical guarantees rely on overly simplistic error models, often assuming decoherence caused by unknown Pauli operations such as a Depolarizing channel. This approach fails to accurately capture realistic noise, where quantum systems undergo a general time evolution while being entangled with their environment. For example, the physical process associated with a qubit's T1 relaxation time does not conform to a Depolarizing channel. Similarly, coherent errors arising from imperfect calibration present another critical deviation. Analyzing the behavior of QEC schemes under such realistic noise conditions is crucial for optimizing their design and performance. In this talk, I will present an overview of some of my works (arXiv:1711.04736, arXiv:2108.10830, arXiv:2303.06846, and another in preparation) that provide insights into benchmarking and improving the performance of QEC schemes under realistic noise models, paving the way for designing optimal and efficient QEC schemes.

Approximate degree is known to be a lower bound on the quantum query complexity. For a measure $M$, composition question asks if $M(f\circ g) = \Theta (M(f) M(g)$. Even though the composition question for most of the measures based on decision tree (how does  for a measure $M$?) has been answered, the complete picture is missing for approximate degree. In this talk we will focus on the composition question of approximate degree.

We will discuss methods (like dual witness) which have been tried to prove composition. This will allow us to prove composition for some interesting classes of functions. Specifically, we will see the composition result when the inner or the outer function is a recursive composition itself.

This is a joint work with Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar and Nitin Saurabh.  

Location will be announced at the start of each workshop.

More information will follow.

Meet at the hotel lobby

Fully quantum conditional entropies are widely used in quantum information theory and cryptography to quantify the uncertainty about the state of a quantum system from the perspective of an observer with access to a potentially correlated quantum system. Using a novel construction, we find a comprehensive family of conditional entropy that contain all previously studied examples of R\'enyi entropies. We show that they satisfy a list of desiderata: data-processing inequalities, additivity under tensor products, duality relations, chain rules, concavity or convexity, and various monotonicity relations in their parameters. We provide unified proofs that in many cases simplify previous more specialised arguments.

Quantum channels derived from various dynamical systems are considered. If there is a classical limit, classical channels, defined via the unitary Koopman operators, enable a detailed study of classical structures in quantum channel modes, including scarring. For many-body systems these channels provide a fresh insight into integrability breaking and the quantum equivalents of Ruelle-Pollicot resonances that govern decay of correlations. Some universal features such as the application of the single-ring theorem from random matrix theory in the spectral properties of quantum channels is also pointed out.

Location will be announced at the start of each workshop.

We study the power of entanglement in classical communication complexity. In particular, we study LOCC communication where Alice and Bob have limited entanglement and can exchange classical messages that depend on measurement outcomes of their shared state. We give explicit partial functions on N bits for which reducing the entanglement even by a small amount exponentially increases the classical communication complexity. Among several results, we show that for every k >= 1, 

(1.) Classical simultaneous protocols with O(k log N) qubits of entanglement can exponentially outperform quantum simultaneous protocols with O(k) qubits of entanglement.  

(2.) Classical one-way protocols with O(k^5 log^3 N) qubits of entanglement can exponentially outperform classical two-way protocols with O(k) qubits of entanglement. 

Collectively, these results show that we cannot efficiently reduce the entanglement in a quantum protocol using only a small amount of classical two-way communication or quantum simultaneous communication. This is based on a joint work with Srinivasan Arunachalam.

The talk is in two parts. —  In the first part, we prove a lower bound on the scrambling speed of a random quantum circuit. We give three applications of this:

a) An optimal lower bound on the depth required for ε-approximate unitary designs; 
b) A polynomial-time quantum algorithm that computes the depth of a bounded-depth circuit, given oracle access to the circuit;
c) A polynomial-time algorithm that learns log-depth circuits up to polynomially small diamond distance, given oracle access to the circuit.

—  In the second part, we show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. Our random circuit-based constructions provide concrete instantiations of quantum crypto-graphic primitives whose security do not depend on the existence of one-way functions. The use of random circuits in our constructions also opens the door to NISQ-friendly quantum cryptography.

Machine learning models are used for pattern recognition analysis of big data, without direct human intervention. The task of supervised learning is to classify new data after learning patterns from training data, while that of unsupervised learning is to find the probability distribution that would best describe the available data, and then use it to make predictions. The former uses feature maps, while the latter uses Boltzmann distributions, both with a large number of tunable parameters. Quantum extensions of these models replace classical probability distributions with the quantum density matrix. An advantage can be obtained only when features of quantum density matrices that are missing in classical probability distributions are exploited. Such situations depend on the input data as well as the targeted observables. Illustrative examples bring out the constraints limiting quantum advantage. The problem-dependent extent of quantum advantage has implications for both data analysis and sensing applications.

Moderator: Ashwin Nayak Rahul Jain Arul Lakshminarayan Frederic Magniez Anand Natarajan Apoorva Patel

Meet at the hotel lobby

Recent results on constant overhead LDPC code based fault-tolerance against i.i.d. errors naturally lead to the question of fault-tolerance against errors with long-range correlations. Though any correlation can be captured by a joint (system and bath) Hamiltonian, an arbitrary joint Hamiltonian is often intractable. Hence, the joint Hamiltonian model with pairwise terms was introduced and developed in a seminal series of papers, Terhal et al. 2005, Aliferis et al. 2005 and Aharonov et al. 2006. However, the analysis of the new constant overhead codes in that error model appears quite challenging. In this work, for modeling correlated errors in quantum memory we introduce a classical correlation model based on hidden random fields. This proposed model, which includes stationary and ergodic (non-Markov) error distributions, is shown to capture correlations not captured by the joint Hamiltonian model with pairwise terms. On the other hand, we show that for a broad class of non-Markov and (possibly) non-stationary error distributions within our proposed model, quantum Tanner codes can ensure an exponential retention time (in the number of physical qubits), when the error rate is below a threshold.  We also discuss some new insights obtained from the analysis of the proposed model that are complementary to the pairwise Hamiltonian model. 

This is a joint work with Smita Bagewadi (IIT Madras).

I will give an overview of the research work in my group [in collaboration with the groups of A Auffeves (MajuLab, CNRS) and R Whitney (Grenoble)] in the past few years on the topic of resource costs of doing quantum computing with noisy components [PRX Quantum 4, 040319 (2023) and PRX Quantum 2, 040335 (2021)]. I will also touch on an upcoming posting on the cost of quantum metrology using exotic states.

In a model of fault-tolerant quantum computation with quick and noiseless polylog-time classical auxiliary computation, we construct a quantum fault tolerance protocol with constant-space and $\widetilde{O}(\log N)$-time overheads. This significantly improves over the previous state-of-the-art due to Yamasaki and Koashi who achieved constant-space and quasipolylog-time overhead. Our construction is obtained by using constant-rate quantum locally testable codes (qLTC) of appropriately chosen block size and developing new fault-tolerant gadgets on qLTCs and qLDPC codes. In particular, we obtain the following new technical results: (1) Magic state distillation protocol with almost-constant spacetime overhead, (2) Single-shot decoder for quantum codes based on the cubical complex constructions, including a recent breakthrough almost-c3 qLTC construction of Dinur-Lin-Vidick, (3) Fault-tolerant universal logical state preparation with almost-constant spacetime overhead on qLTCs. (4) Resource states to obtain addressable qLDPC logic that can be easily prepared using our state preparation schemes. We obtain the mentioned quantum fault tolerance protocol by combining the above results with carefully chosen parameters. To our knowledge, this gives the lowest overhead to date in the considered model of quantum fault tolerance, which we conjecture is optimal, up to sub-polylog factors.

Joint work with Christopher A. Pattison

Location will be announced at the start of each workshop.

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/\log(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.

This is joint work with Chris Pattison and John Preskill. The talk will be based on arXiv2303.04798.

Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors through error reduction (exactness). Second, through careful accounting (thriftiness), the total query complexity is smaller if subroutines are mostly run on cheaper inputs -- a property that is much less obvious in quantum algorithms than in their classical counterparts.

While these properties were previously seen through the model of span programs (alternatively, the dual adversary bound), a recent work by two of the authors (Belovs, Yolcu 2023) showed how to achieve these benefits without converting to span programs, by defining quantum Las Vegas query complexity. Independently, recent works, including by one of the authors (Jeffery 2022), have worked towards bringing thriftiness to the more practically significant setting of quantum time complexity.

In this work, we show how to achieve both exactness and thriftiness in the setting of time complexity. We generalize the quantum subroutine composition results of Jeffery 2022 so that, in particular, no error reduction is needed. We give a time complexity version of the well-known result in quantum query complexity, $Q(f\circ g)=O(Q(f)\cdot Q(g))$, without log factors.

We achieve this by employing a novel approach to the design of quantum algorithms based on what we call transducers, and which we think is of large independent interest. While a span program is a completely different computational model, a transducer is a direct generalisation of a quantum algorithm, which allows for much greater transparency and control. Transducers naturally characterize general state conversion, rather than only decision problems;  provide a very simple treatment of other quantum primitives such as quantum walks; and lend themselves well to time complexity analysis.

Meet at the hotel lobby

I will talk about some of the new techniques we developed for implementing any Linear combination of Unitaries (LCU) on intermediate-term quantum computers. While the standard LCU procedure requires several ancilla qubits and sophisticated multi-qubit controlled operations, our methods consume significantly fewer quantum resources. 

The first method, known as Single-ancilla LCU, implements any LCU using only a single ancilla qubit, no multi-qubit controlled logic, and quantum circuits of shorter depth than the standard method. The key idea is to substitute complicated controlled operations (in the standard LCU approach) with importance sampling and make several independent runs of short-depth quantum circuits to estimate the expectation value of observables vis-à-vis any state prepared by LCU. We apply this to develop new algorithms for ground state property estimation, Hamiltonian simulation, and quantum linear systems that are more amenable to intermediate-term implementation. We characterize the end-to-end complexities of our algorithms, which, remarkably in some regimes, have shorter gate depths than even state-of-the-art methods despite requiring significantly fewer resources. Time permitting, I will also talk about two other approaches:  Analog LCU, a simple, physically motivated, continuous-time analogue of LCU tailored to hybrid qubit-qumode systems, and  Ancilla-free LCU, which, as the name suggests, allows for implementing LCU without any ancilla qubits when we are interested in the projection of a quantum state (prepared by the LCU procedure) in some subspace of interest.  Both these methods also find applications in different areas. 

Overall, our results are pretty generic and can be readily applied to other problems, even beyond those considered in our work.

Reference: S. Chakraborty, arXiv:2302.13555v4 [arxiv.org] (To appear in Quantum).

In this talk I will discuss qutrit circuit synthesis over various families of universal gate sets. I will describe a method which relates the question of exact synthesis for both single qubits and single qutrits to the problem of solving a system of polynomial equations mod p. 

This is work done in collaboration with Dinesh Valluri and Michele Mosca. 

Quantum computing and quantum sensing represent two distinct frontiers of quantum technology. In this work, we harness quantum computing to solve a fundamental and practically important sensing problem: the detection of weak oscillating fields with unknown strength and frequency. We present a quantum computing enhanced sensing protocol that outperforms all existing approaches. Furthermore, we prove our approach is optimal by establishing the Grover-Heisenberg limit --- a fundamental lower bound on the minimum sensing time. The key idea is to robustly digitize the continuous, analog signal into a discrete operation, which is then integrated into a quantum algorithm. Our metrological gain fundamentally requires quantum computation, distinguishing our protocol from conventional sensing approaches. Indeed, we prove that any approach based on quantum Fisher information, finite-lifetime quantum memory, or classical signal processing is strictly less powerful. Our protocol is compatible with multiple experimental platforms. We propose and analyze a proof-of-principle experiment using nitrogen-vacancy centers, where meaningful improvements are achievable using current technology. This work establishes quantum computation as a powerful new resource for advancing sensing capabilities.

We study the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum verifier. Our main result is that QCPH is infinite relative to a random oracle (previously, this was not even known relative to any oracle). We further prove that higher levels of PH are not contained in lower levels of QCPH relative to a random oracle; this is a strengthening of the somewhat recent result that PH is infinite relative to a random oracle (Rossman, Servedio, and Tan 2016). To establish this, we give a new switching lemma for quantum algorithms which may be of independent interest. Our lemma says that if we apply a random restriction to a function f with low quantum query complexity, the restricted function becomes exponentially close (in terms of depth)  to a small depth decision tree. Our switching lemma works even in a “worst-case” sense, in that only the indices to be restricted are random; the values they are restricted to are chosen adversarially. Moreover, the switching lemma also works for polynomial degree in place of quantum query complexity. This talk is based on joint work with Shalev Ben-David.

We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex.

In the classical unidirectional model the problem of testing k-star-freeness, and more generally k-source-subgraph-freeness, is almost maximally hard for large k. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we prove that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the k-collision problem that was not studied before.

To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of 3-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.

Location will be announced at the start of each workshop.