Accepted talks TQC 2024

@Talk{T24_298,

title = {Conditional independence of 1D Gibbs states with applications to efficient learning},

author = {Paul Gondolf and Samuel O. Scalet and Alberto Ruiz-de-Alarcón and Álvaro M. Alhambra and Ángela Capel},

url = {https://arxiv.org/abs/2402.18500},

year  = {2024},

date = {2024-01-01},

abstract = {We show that spin chains in thermal equilibrium have a correlation structure in which individual regions are strongly correlated at most with their near vicinity. We quantify this with alternative notions of the conditional mutual information defined through the so-called Belavkin-Staszewski relative entropy. We prove that these measures decay super-exponentially, under the assumption that the spin chain Hamiltonian is translation-invariant. Using a recovery map associated with these measures, we sequentially construct tensor network approximations in terms of marginals of small (sub-logarithmic) size. As a main application, we show that classical representations of the states can be learned efficiently from local measurements with a polynomial sample complexity. We also prove an approximate factorization condition for the purity of the entire Gibbs state, which implies that it can be efficiently estimated to a small multiplicative error from a small number of local measurements. As a technical step of independent interest, we show an upper bound to the decay of the Belavkin-Staszewski relative entropy upon the application of a conditional expectation.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_176,

title = {Dissipation-enabled bosonic Hamiltonian learning via new information-propagation bounds},

author = {Tim Möbus and Andreas Bluhm and Matthias C. Caro and Albert H. Werner and Cambyse Rouzé},

url = {https://arxiv.org/abs/2308.12425},

year  = {2024},

date = {2024-01-01},

abstract = {In this work, we prove uniform continuity bounds for entropic quantities related to the sandwiched Rényi divergences such as the sandwiched Rényi conditional entropy. We follow three different approaches: The first one is the axiomatic approach, which exploits the sub-/ superadditivity and joint concavity/ convexity of the exponential of the divergence. In our second approach, termed the "operator space approach", we express the entropic measures as norms and utilize their properties for establishing the bounds. These norms draw inspiration from interpolation space norms. We not only demonstrate the norm properties solely relying on matrix analysis tools but also extend their applicability to a context that holds relevance in resource theories. By this, we extend the strategies of Marwah and Dupuis as well as Beigi and Goodarzi employed in the sandwiched Rényi conditional entropy context. Finally, we merge the approaches into a mixed approach that has some advantageous properties and then discuss in which regimes each bound performs best. Our results improve over the previous best continuity bounds or sometimes even give the first continuity bounds available. In a separate contribution, we use the ALAAF method, developed in a previous article by some of the authors, to study the stability of approximate quantum Markov chains.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_194,

title = {Eigenpath traversal by Poisson-distributed phase randomisation},

author = {Joseph Cunningham and Jérémie Roland},

year  = {2024},

date = {2024-01-01},

abstract = {We present a framework for quantum computation, similar to Adiabatic Quantum Computation (AQC), that is based on the quantum Zeno effect. By performing randomised dephasing operations at intervals determined by a Poisson process, we are able to track the eigenspace associated to a particular eigenvalue. We derive a simple differential equation for the fidelity leading to general theorems bounding the time complexity of a whole class of algorithms. We also use eigenstate filtering to optimise the scaling of the complexity in the error tolerance ε. In many cases the bounds given by our general theorems are optimal, giving a time complexity of O(1/Δ) with Δ the minimum of the gap. This allows us to prove optimal results using very general features of problems, minimising the amount of problem-specific insight necessary. As two applications of our framework we obtain optimal scaling for the Grover problem (i.e. O(N^1/2) where N is the database size) and the Quantum Linear System Problem (i.e. O(κłog(1/ε)) where κ is the condition number and ε the error tolerance) by direct applications of our theorems.},

keywords = {Proceedings, Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_269,

title = {Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling},

author = {Pedro C. S. Costa and Philipp Schleich and Mauro Morales and Dominic W. Berry},

url = {https://arxiv.org/abs/2312.09518},

year  = {2024},

date = {2024-01-01},

abstract = {The solution of large systems of nonlinear differential equations is needed for many applications in science and engineering. In this study, we present three main improvements to existing quantum algorithms based on the Carleman linearisation technique. First, by using a high-precision technique for the solution of the linearised differential equations, we achieve logarithmic dependence of the complexity on the error and near-linear dependence on time. Second, we demonstrate that a rescaling technique can considerably reduce the cost, which would otherwise be exponential in the Carleman order for a system of ODEs, preventing a quantum speedup for PDEs. Third, we provide improved, tighter bounds on the error of Carleman linearisation. We apply our results to a class of discretised reaction-diffusion equations using higher-order finite differences for spatial resolution. We show that providing a stability criterion independent of the discretisation can conflict with the use of the rescaling due to the difference between the max-norm and 2-norm. An efficient solution may still be provided if the number of discretisation points is limited, as is possible when using higher-order discretisations.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_380,

title = {Generalized Rényi entropy accumulation theorem and generalized quantum probability estimation},

author = {Amir Arqand and Thomas Hahn and Ernest Y. -Z. Tan},

url = {https://arxiv.org/abs/2405.05912},

year  = {2024},

date = {2024-01-01},

abstract = {The entropy accumulation theorem, and its subsequent generalized version, is a powerful tool in the security analysis of many device-dependent and device-independent cryptography protocols. However, it has the drawback that the finite-size bounds it yields are not necessarily optimal, and furthermore it relies on the construction of an affine min-tradeoff function, which can often be challenging to construct optimally in practice. In this work, we address both of these challenges simultaneously by deriving a new entropy accumulation bound. Our bound yields significantly better finite-size performance, and can be computed as an intuitively interpretable convex optimization, without any specification of affine min-tradeoff functions. Furthermore, it can be applied directly at the level of Renyi entropies if desired, yielding fully-Renyi security proofs. Our proof techniques are based on elaborating on a connection between entropy accumulation and the frameworks of quantum probability estimation or f-weighted Rényi entropies, and in the process we obtain some new results with respect to those frameworks as well.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_284,

title = {Guidable Local Hamiltonian Problems with Implications to Heuristic Ansatz State Preparation and the Quantum PCP Conjecture},

author = {Jordi Weggemans and Marten Folkertsma and Chris Cade},

url = {https://arxiv.org/abs/2302.11578},

year  = {2024},

date = {2024-01-01},

abstract = {We study 'Merlinized' versions of the recently defined Guided Local Hamiltonian problem, which we call 'Guidable Local Hamiltonian' problems. Unlike their guided counterparts, these problems do not have a guiding state provided as a part of the input, but merely come with the promise that one exists. We consider in particular two classes of guiding states: those that can be prepared efficiently by a quantum circuit; and those belonging to a class of quantum states we call classically evaluatable, for which it is possible to efficiently compute expectation values of local observables classically. We show that guidable local Hamiltonian problems for both classes of guiding states are 𝖰𝖢𝖬𝖠-complete in the inverse-polynomial precision setting, but lie within 𝖭𝖯 (or 𝖭𝗊𝖯) in the constant precision regime when the guiding state is classically evaluatable. Our completeness results show that, from a complexity-theoretic perspective, classical Ansätze selected by classical heuristics are just as powerful as quantum Ansätze prepared by quantum heuristics, as long as one has access to quantum phase estimation. In relation to the quantum PCP conjecture, we (i) define a complexity class capturing quantum-classical probabilistically checkable proof systems and show that it is contained in BQP^NP[1] for constant proof queries; (ii) give a no-go result on 'dequantizing' the known quantum reduction which maps a 𝖰𝖯𝖢𝖯-verification circuit to a local Hamiltonian with constant promise gap; (iii) give several no-go results for the existence of quantum gap amplification procedures that preserve certain ground state properties; and (iv) propose two conjectures that can be viewed as stronger versions of the NLTS theorem. Finally, we show that many of our results can be directly modified to obtain similar results for the class 𝖬𝖠.},

keywords = {Proceedings, Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_182,

title = {Hamiltonian Property Testing},

author = {Andreas Bluhm and Matthias C. Caro and Aadil Oufkir},

url = {https://arxiv.org/abs/2403.02968},

year  = {2024},

date = {2024-01-01},

abstract = {Locality is a fundamental feature of many physical time evolutions. Assumptions on locality and related structural properties also underlie recently proposed procedures for learning an unknown Hamiltonian from access to the induced time evolution. However, no protocols to rigorously test whether an unknown Hamiltonian is in fact local were known. We investigate Hamiltonian locality testing as a property testing problem, where the task is to determine whether an unknown Hamiltonian H is k-local or epsilon-far from all k-local Hamiltonians, given access to the time evolution along H. First, we emphasize the importance of the chosen distance measure: With respect to the operator norm, a worst-case distance measure, incoherent quantum locality testers require at least order 2^n many time evolution queries and an expected total evolution time of order 2^n/epsilon, and even coherent testers need at least order 2^(n/2) many queries and order 2^(n/2)/epsilon total evolution time. In contrast, when distances are measured according to the normalized Frobenius norm, corresponding to an average-case distance, we give a sample-, time-, and computationally efficient incoherent Hamiltonian locality testing algorithm based on randomized measurements. In fact, our procedure can be used to simultaneously test a wide class of Hamiltonian properties beyond locality. Finally, we prove that learning a general Hamiltonian remains exponentially hard with this average-case distance, thereby establishing an exponential separation between Hamiltonian testing and learning. Our work initiates the study of property testing for quantum Hamiltonians, demonstrating that a broad class of Hamiltonian properties is efficiently testable even with limited quantum capabilities, and positioning Hamiltonian testing as an independent area of research alongside Hamiltonian learning.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_390,

title = {Hierarchical memories: Simulating quantum LDPC codes with local gates},

author = {Christopher Pattison and Anirudh Krishna and John Preskill},

url = {https://arxiv.org/abs/2303.04798},

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 = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_185,

title = {Information-theoretic generalization bounds for learning from quantum data},

author = {Matthias C. Caro and Tom Gur and Cambyse Rouze and Daniel Stilck França and Sathyawageeswar Subramanian},

url = {https://arxiv.org/abs/2311.05529},

year  = {2024},

date = {2024-01-01},

abstract = {Learning tasks play an increasingly prominent role in quantum information and computation. They range from fundamental problems such as state discrimination and metrology over the framework of quantum probably approximately correct (PAC) learning, to the recently proposed shadow variants of state tomography. However, the many directions of quantum learning theory have so far evolved separately. We propose a general mathematical formalism for describing quantum learning by training on classical-quantum data and then testing how well the learned hypothesis generalizes to new data. In this framework, we prove bounds on the expected generalization error of a quantum learner in terms of classical and quantum mutual information quantities measuring how strongly the learner's hypothesis depends on the specific data seen during training. To achieve this, we use tools from quantum optimal transport and quantum concentration inequalities to establish non-commutative versions of decoupling lemmas that underlie recent information-theoretic generalization bounds for classical machine learning. Our framework encompasses and gives intuitively accessible generalization bounds for a variety of quantum learning scenarios such as quantum state discrimination, PAC learning quantum states, quantum parameter estimation, and quantumly PAC learning classical functions. Thereby, our work lays a foundation for a unifying quantum information-theoretic perspective on quantum learning.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_290,

title = {Learning low-degree quantum objects},

author = {Srinivasan Arunachalam and Arkopal Dutt and Francisco Escudero Gutiérrez and Carlos Palazuelos},

year  = {2024},

date = {2024-01-01},

abstract = {We consider the problem of learning low-degree quantum objects up to ε-error in l_2-distance. We show the following results: (I) unknown n-qubit degree-d (in the Pauli basis) quantum channels and unitaries can be learned using O(1/ε^d) queries (which is independent of n), (II) polynomials p:-1,1^n -> [-1,1] arising from d-query quantum algorithms can be learned from O((1/ε)^d log n) many random examples (x,p(x)) (which implies learnability even for d=O(log n)), and (III) degree-d polynomials p:-1,1^n -> [-1,1] can be learned through O(1/ε^d) queries to a quantum unitary Up that block-encodes p. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded polynomials.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_30,

title = {One Clean Qubit Suffices for Quantum Communication Advantage},

author = {Uma Girish and Srinivasan Arunachalam and Noam Lifshitz},

year  = {2024},

date = {2024-01-01},

abstract = {We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost O(log N) in this model, however, every interactive randomized protocol has cost Ømega(sqrtN), settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus classical communication separations required at least Ømega(log N) clean qubits. The function demonstrating our separation also has an efficient protocol in the quantum-simultaneous-with-entanglement model of cost O(log N). We thus recover the state-of-the-art separations between quantum and classical communication complexity. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer, in conjunction with tools from the representation theory of compact Lie groups.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_61,

title = {Online Locality Meets Distributed Quantum Computing},

author = {Amirreza Akbari and Xavier Coiteux-Roy and Francesco D'Amore and Francois Le Gall and Henrik Lievonen and Darya Melnyk and Augusto Modanese and Shreyas Pai and Marc-Olivier Renou and Václav Rozhoň and Jukka Suomela},

url = {https://arxiv.org/abs/2403.01903},

year  = {2024},

date = {2024-01-01},

abstract = {We extend the theory of locally checkable labeling problems (LCLs) from the classical LOCAL model to a number of other models that have been studied recently, including the quantum-LOCAL model, finitely-dependent processes, non-signaling model, dynamic-LOCAL model, and online-LOCAL model [e.g. STOC 2024, ICALP 2023]. 

First, we demonstrate the advantage that finitely-dependent processes have over the classical LOCAL model. We show that all LCL problems solvable with locality O(log⋆n) in the LOCAL model admit a finitely-dependent distribution (with constant locality). In particular, this gives a finitely-dependent coloring for regular trees, answering an open question by Holroyd [2023]. This also introduces a new formal barrier for understanding the distributed quantum advantage: it is not possible to exclude quantum advantage for any LCL in the Θ(log⋆n) complexity class by using non-signaling arguments. 

Second, we put limits on the capabilities of all of these models. To this end, we introduce a model called randomized online-LOCAL, which is strong enough to simulate e.g. SLOCAL and dynamic-LOCAL, and we show that it is also strong enough to simulate any non-signaling distribution and hence any quantum-LOCAL algorithm. We prove the following result for rooted trees: if we can solve an LCL problem with locality o(loglogn) in the randomized online-LOCAL model, we can solve it with locality O(log⋆n) in the classical deterministic LOCAL model. Put together, these results show that in rooted trees the set of LCLs that can be solved with locality O(log⋆n) is the same across all these models: classical deterministic and randomized LOCAL, quantum-LOCAL, non-signaling model, dynamic-LOCAL, and deterministic and randomized online-LOCAL.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_257,

title = {Proper vs Improper Quantum PAC Learning},

author = {Ashwin Nayak and Pulkit Sinha},

url = {https://arxiv.org/abs/2403.03295},

year  = {2024},

date = {2024-01-01},

abstract = {A basic question in the PAC model of learning is whether proper learning is harder than improper learning. In the classical case, there are examples of concept classes with VC dimension d that have sample complexity Ω(d/ϵ log(1/ϵ)) for proper learning with error ϵ, while the complexity for improper learning is O(d/ϵ). One such example arises from the Coupon Collector problem. 

Motivated by the efficiency of proper versus improper learning with quantum samples, Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf (TQC 2020) studied an analogue, the Quantum Coupon Collector problem. Curiously, they discovered that for learning size k subsets of [n] the problem has sample complexity Θ(k log mink,n−k+1), in contrast with the complexity of Θ(k log k) for Coupon Collector. This effectively negates the possibility of a separation between the two modes of learning via the quantum problem, and Arunachalam et al. posed the possibility of such a separation as an open question. In this work, we first present an algorithm for the Quantum Coupon Collector problem with sample complexity that matches the sharper lower bound of (1−o_k(1))k ln mink,n−k+1 shown recently by Bab Hadiashar, Nayak, and Sinha (IEEE TIT 2024), for the entire range of the parameter k. Next, we devise a variant of the problem, the Quantum Padded Coupon Collector. We prove that its sample complexity matches that of the classical Coupon Collector problem for both modes of learning, thereby exhibiting the same asymptotic separation between proper and improper quantum learning as mentioned above. The techniques we develop in the process can be directly applied to any form of padded quantum data. We hope that padding can more generally lift other forms of classical learning behaviour to the quantum setting.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_45,

title = {Provable Advantage in Quantum PAC Learning},

author = {Wilfred Salmon and Sergii Strelchuk and Tom Gur},

url = {https://arxiv.org/abs/2309.10887},

year  = {2024},

date = {2024-01-01},

abstract = {We revisit the problem of characterising the complexity of Quantum PAC learning, as introduced by Bshouty and Jackson [1]. Several quantum advantages have been demonstrated in this setting, however, none are generic: they apply to particular concept classes and typically only work when the distribution that generates the data is known. In the general case, it was recently shown by Arunachalam and de Wolf [2] that quantum PAC learners can only achieve constant factor advantages over classical PAC learners. 

We show that with a natural extension of the definition of quantum PAC learning used by Arunachalam and de Wolf, we can achieve a generic advantage in quantum learning. To be precise, for any concept class C of VC dimension d, we show there is an (ϵ,δ)-quantum PAC learner with sample complexity 

O(1/√ϵ[d+log(1/δ)]log^9(1/ϵ)). 

Up to polylogarithmic factors, this is a square root improvement over the classical learning sample complexity. We show the tightness of our result by proving an Ω(d/√ϵ) lower bound that matches our upper bound up to polylogarithmic factors. 

[1] SIAM J. Comput. 1998, 28, 1136-1153 [2] JMLR, 19 (2018) 1-36},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_425,

title = {Quantum Bohnenblust–Hille inequalities and applications to learning low-degree quantum observables},

author = {Alexander Volberg and Haonan Zhang and Ohad Klein and Joseph Slote},

year  = {2024},

date = {2024-01-01},

abstract = {Analysis on the Boolean hypercube −1,1^n, particularly Fourier analysis, has played a crucial role in many areas of mathematics and computer science, including learning algorithms. In view of the success and importance of quantum algorithms, it is natural to transfer classical learning results to the quantum realm. In this contribution, we extend the recent progress on learning low-degree functions and quantum operators to the setting of general qudit systems, as well as develop novel Fourier-analytic tools for studying (generalized) Pauli decompositions of Hermitian operators. These tools also allow us to deduce new results in quantum Boolean analysis and approximate theory, such as the junta-type theorem and dimension-free discrete Remez-type inequalities.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_124,

title = {Quantum computation of stopping power for inertial fusion target design},

author = {Nicholas Rubin and Dominic Berry and Alina Kononov and Fionn Malone and Tanuj Khattar and Alec White and Joonho Lee and Hartmut Neven and Ryan Babbush and Andrew Baczewski},

year  = {2024},

date = {2024-01-01},

abstract = {Stopping power is the rate at which a material absorbs the kinetic energy of a charged particle passing through it – one of many properties needed over a wide range of thermodynamic conditions in modeling inertial fusion implosions. First-principles stopping calculations are classically challenging because they involve the dynamics of large electronic systems far from equilibrium, with accuracies that are particularly difficult to constrain and assess in the warm-dense conditions preceding ignition. Here, we describe a protocol for using a fault-tolerant quantum computer to calculate stopping power from a first-quantized representation of the electrons and projectile. Our approach builds upon the electronic structure block encodings of Su et al. [PRX Quantum 2, 040332 2021], adapting and optimizing those algorithms to estimate observables of interest from the non-Born-Oppenheimer dynamics of multiple particle species at finite temperature. We also work out the constant factors associated with a novel implementation of a high-order Trotter approach to simulating a grid representation of these systems. Ultimately, we report logical qubit requirements and leading-order Toffoli costs for computing the stopping power of various projectile/target combinations relevant to interpreting and designing inertial fusion experiments. We estimate that scientifically interesting and classically intractable stopping power calculations can be quantum simulated with roughly the same number of logical qubits and about one hundred times more Toffoli gates than is required for state-of-the-art quantum simulations of industrially relevant molecules such as FeMoco or P450.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_121,

title = {Quantum delegation with an off-the-shelf device},

author = {Anne Broadbent and Arthur Mehta and Yuming Zhao},

url = {https://arxiv.org/abs/2304.03448},

year  = {2024},

date = {2024-01-01},

abstract = {Given that reliable cloud quantum computers are becoming closer to reality, the concept of delegation of quantum computations and its verifiability is of central interest. Many models have been proposed, each with specific strengths and weaknesses. Here, we put forth a new model where the client trusts only its classical processing, makes no computational assumptions, and interacts with a quantum server in a single round. In addition, during a set-up phase, the client specifies the size n of the computation and receives an untrusted, off-the-shelf (OTS) quantum device that is used to report the outcome of a single measurement. 

We show how to delegate polynomial-time quantum computations in the OTS model. This also yields an interactive proof system for all of QMA, which, furthermore, we show can be accomplished in statistical zero-knowledge. This provides the first relativistic (one-round), two-prover zero-knowledge proof system for QMA. As a proof approach, we provide a new self-test for n EPR pairs using only constant-sized Pauli measurements, and show how it provides a new avenue for the use of simulatable codes for local Hamiltonian verification. Along the way, we also provide an enhanced version of a well-known stability result due to Gowers and Hatami and show how it completes a common argument used in self-testing.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_68,

title = {Quantum Generic Hardness for Discrete Logarithms and Integer Factorization},

author = {Minki Hhan and Takashi Yamakawa and Aaram Yun},

url = {https://arxiv.org/pdf/2307.03065 https://arxiv.org/pdf/2402.11269},

year  = {2024},

date = {2024-01-01},

abstract = {We study the quantum computational complexity of the discrete logarithm (DL) problems and integer factorization in the context of ``generic algorithms''—that is, algorithms that do not exploit any properties of the group/ring encoding. 

We establish the generic models of quantum algorithms for group/ring problems as quantum analogs of their classical counterparts. In these models, we count the number of group/ring operations as complexity measures. Shor's and Regev's algorithms (or their slight modifications) can be described in these models. 

We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and integer factorization in these models. 

* (The DL problem, fully quantum setting) We prove that any generic quantum DL algorithm must make a logarithmic number of group operations for the group size, showing that Shor's algorithm that makes the logarithmic number of group operations is asymptotically optimal regarding the number of group operations. This holds even considering parallel quantum algorithms. 

* (The DL problem, hybrid/memory-bounded setting) We observe that some (known) variations of Shor's algorithm can take advantage of classical computations to reduce the number and depth of quantum group operations. We establish a model for generic hybrid quantum-classical algorithms and prove the matching lower bounds. We also study the memory-bounded setting and establish asymptotically tight lower bounds. We extend these results to the multiple-instance DL problem with a matching new algorithm. * (Integer factorization) We give a logarithmic lower bound for the order-finding algorithms, an important step for Shor's algorithm. We also prove a logarithmic lower bound for a certain generic factoring algorithm outputting relatively small integers, which includes a modified version of Regev's algorithm.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_237,

title = {Quantum state tomography of continuous variable systems},

author = {Francesco Anna Mele and Salvatore F. E. Oliviero and Lennart Bittel and Jens Eisert and Vittorio Giovannetti and Ludovico Lami and Lorenzo Leone and Antonio Anna Mele},

url = {https://arxiv.org/abs/2405.01431},

year  = {2024},

date = {2024-01-01},

abstract = {Quantum state tomography, aimed at deriving a classical description of an unknown state from measurement data, is a fundamental task in quantum physics. In this work, we analyse the ultimate achievable performance of tomography of continuous-variable systems, such as bosonic and quantum optical systems. We prove that tomography of these systems is extremely inefficient in terms of time resources, much more so than tomography of qudit systems: the minimum number of state copies needed for tomography not only scales exponentially with the number of modes but also exhibits a dramatic scaling with the trace-distance error, even for low-energy states. On a more positive note, we prove that tomography of Gaussian states is efficient. To accomplish this, we answer a fundamental question for the field of continuous-variable quantum information: if we know with a certain error the first and second moments of an unknown Gaussian state, what is the resulting trace-distance error that we make on the state? Lastly, we demonstrate that tomography of non-Gaussian states prepared through Gaussian unitaries and a few local non-Gaussian evolutions is efficient and experimentally feasible.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_192,

title = {Revocable Quantum Digital Signatures},

author = {Tomoyuki Morimae and Alexander Poremba and Takashi Yamakawa},

url = {https://arxiv.org/pdf/2312.13561},

year  = {2024},

date = {2024-01-01},

abstract = {We study digital signatures with revocation capabilities and show two results. First, we define and construct digital signatures with revocable signing keys from the LWE assumption. In this primitive, the signing key is a quantum state which enables a user to sign many messages and yet, the quantum key is also revocable, i.e., it can be collapsed into a classical certificate which can later be verified. Once the key is successfully revoked, we require that the initial recipient of the key loses the ability to sign. We construct digital signatures with revocable signing keys from a newly introduced primitive which we call two-tier one-shot signatures, which may be of independent interest. This is a variant of one-shot signatures, where the verification of a signature for the message ``0'' is done publicly, whereas the verification for the message ``1'' is done in private. We give a construction of two-tier one-shot signatures from the LWE assumption. As a complementary result, we also construct digital signatures with quantum revocation from group actions, where the quantum signing key is simply ``returned'' and then verified as part of revocation. Second, we define and construct digital signatures with revocable signatures from OWFs. In this primitive, the signer can produce quantum signatures which can later be revoked. Here, the security property requires that, once revocation is successful, the initial recipient of the signature loses the ability to find accepting inputs to the signature verification algorithm. We construct this primitive using a newly introduced two-tier variant of tokenized signatures. For the construction, we show a new lemma which we call the adaptive hardcore bit property for OWFs, which may enable further applications.},

keywords = {Proceedings, Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_214,

title = {Secret Sharing with Certified Deletion},

author = {James Bartusek and Justin Raizes},

url = {https://eprint.iacr.org/2024/736},

year  = {2024},

date = {2024-01-01},

abstract = {Secret sharing allows a user to split a secret into many shares so that the secret can be recovered if, and only if, an authorized set of shares is collected. Although secret sharing typically does not require any computational hardness assumptions, its security does require that an adversary cannot collect an authorized set of shares. Over long periods of time where an adversary can benefit from multiple data breaches, this may become an unrealistic assumption. 

 We initiate the systematic study of secret sharing with certified deletion in order to achieve security even against an adversary that eventually collects an authorized set of shares. In secret sharing with certified deletion, a (classical) secret 

s is split into quantum shares that can be destroyed in a manner verifiable by the dealer. 

 We put forth two natural definitions of security. No-signaling security roughly requires that if multiple non-communicating adversaries delete sufficiently many shares, then their combined view contains negligible information about s, even if the total set of corrupted parties forms an authorized set. Adaptive security requires privacy of s against an adversary that can continuously and adaptively corrupt new shares and delete previously-corrupted shares, as long as the total set of corrupted shares minus deleted shares remains unauthorized. Next, we show that these security definitions are achievable: we show how to construct (i) a secret sharing scheme with no-signaling certified deletion for any monotone access structure, and (ii) a threshold secret sharing scheme with adaptive certified deletion. Our first construction uses Bartusek and Khurana's (CRYPTO 2023) 2-out-of-2 secret sharing scheme with certified deletion as a building block, while our second construction is built from scratch and requires several new technical ideas. For example, we significantly generalize the ``XOR extractor'' of Agarwal, Bartusek, Khurana, and Kumar (EUROCRYPT 2023) in order to obtain better seedless extraction from certain quantum sources of entropy, and show how polynomial interpolation can double as a high-rate randomness extractor in our context of threshold sharing with certified deletion.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@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},

url = {https://arxiv.org/abs/2306.12470},

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 article, we prove that quantum Tanner codes also facilitate single-shot quantum error correction (QEC) of adversarial noise, where one measurement round (consisting of constant-weight parity checks) suffices to perform reliable QEC even in the presence of measurement errors. We establish this result for both 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 = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_58,

title = {Stochastic error cancellation in analog quantum simulation},

author = {Yiyi Cai and Yu Tong and John Preskill},

url = {https://arxiv.org/abs/2311.14818},

year  = {2024},

date = {2024-01-01},

abstract = {Analog quantum simulation is a promising path towards solving classically intractable problems in many-body physics on near-term quantum devices. However, the presence of noise limits the size of the system and the length of time that can be simulated. In our work, we consider an error model in which the actual Hamiltonian of the simulator differs from the target Hamiltonian we want to simulate by small local perturbations, which are assumed to be random and unbiased. We analyze the error accumulated in observables in this setting and show that, due to stochastic error cancellation, with high probability the error scales as the square root of the number of qubits instead of linearly. We explore the concentration phenomenon of this error as well as its implications for local observables in the thermodynamic limit. Moreover, we show that stochastic error cancellation also manifests in the fidelity between the target state at the end of time-evolution and the actual state we obtain in the presence of noise. This indicates that, to reach a certain fidelity, more noise can be tolerated than implied by the worst-case bound if the noise comes from many statistically independent sources.},

keywords = {Proceedings, Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_343,

title = {Sufficiency of Rényi divergences},

author = {Niklas Galke and Lauritz Luijk and Henrik Wilming},

year  = {2024},

date = {2024-01-01},

abstract = {A set of classical or quantum states is equivalent to another one if there exists a pair of classical or quantum channels mapping either set to the other one. For dichotomies (pairs of states), this is closely connected to (classical or quantum) Rényi divergences (RD) and the data-processing inequality: If a RD remains unchanged when a channel is applied to the dichotomy, then there is a recovery channel mapping the image back to the initial dichotomy. Here, we prove for classical dichotomies that equality of the RDs alone is already sufficient for the existence of a channel in any of the two directions and discuss some applications. In the quantum case, all families of quantum RDs are seen to be insufficient because they cannot detect anti-unitary transformations. Thus, including anti-unitaries, we pose the problem of finding a sufficient family. It is shown that the Petz and maximal quantum RD are still insufficient in this more general sense and we provide evidence for sufficiency of the minimal quantum RD. As a side result of our techniques, we obtain an infinite list of inequalities fulfilled by the classical, the Petz quantum, and the maximal quantum RDs. These inequalities are not true for the minimal quantum RDs. Our results further imply that any sufficient set of conditions for state transitions in the resource theory of athermality must be able to detect time-reversal.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_317,

title = {Taming Quantum Time Complexity},

author = {Aleksandrs Belovs and Stacey Jeffery and Duyal Yolcu},

year  = {2024},

date = {2024-01-01},

abstract = {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 (emphexactness). Second, through careful accounting (emphthriftiness), 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 emphquantum 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 emphtime 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(fcirc 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 emphtransducers, 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.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@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},

url = {https://arxiv.org/abs/2404.17676},

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 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 bivariate bicycle qLDPC codes and show that they are well suited for a parallel syndrome measurement scheme using fast routing with local operations and classical communication (LOCC). Through circuit-level simulations, we find that in some parameter regimes bivariate bicycle codes implemented with this protocol have logical error rates comparable to the surface code while using fewer physical qubits.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_15,

title = {Tradeoff Constructions for Quantum Locally Testable Codes},

author = {Adam Wills and Ting-Chun Lin and Min-Hsiu Hsieh},

url = {https://arxiv.org/abs/2309.05541},

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. Applying these constructions in various combinations to recent advancements yields near-optimal quantum locally testable codes.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}