Centrum Wiskunde & Informatica (National Research Institute for Mathematics and Computer Science)

Mele A.A., Herasymenko Y.

The experimental realization of increasingly complex quantum states underscores the pressing need for new methods of state learning and verification. In one such framework, quantum state tomography, the aim is to learn the full quantum state from data obtained by measurements. Without prior assumptions on the state, this task is prohibitively hard. Here, we present an efficient algorithm for learning states on n fermion modes prepared by any number of Gaussian and at most t non-Gaussian gates. By Jordan-Wigner mapping, this also includes n-qubit states prepared by nearest-neighbor matchgate circuits with at most t gates. Our algorithm is based exclusively on single-copy measurements and produces a classical representation of a state, guaranteed to be close in trace distance to the target state. The sample and time complexity of our algorithm is poly(n,2t); thus if t=O(log(n)), it is efficient. We also show that, if t scales more than logarithmically, any learning algorithm to solve the same task must be inefficient, under common cryptographic assumptions. We also provide an efficient property-testing algorithm that, given access to copies of a state, determines whether such a state is far or close to the set of states for which our learning algorithm works. In addition to the outputs of quantum circuits, our tomography algorithm is efficient for some physical target states, such as those arising in time dynamics and low-energy physics of impurity models. Beyond tomography, our work sheds light on the structure of states prepared with few non-Gaussian gates and offers an improved upper bound on their circuit complexity, enabling an efficient circuit-compilation method. Published by the American Physical Society 2025

Guo Y., Limburg A., Laarman J., Teunissen J., Nijdam S.

Using electric field induced second harmonic generation (E-FISH), we performed direction-resolved absolute electric field measurements on single-channel streamer discharges in 70 mbar (7 kPa) air with 0.2 mm and 2 ns resolutions. In order to obtain the absolute (local) electric field, we developed a deconvolution method taking into account the phase variations of E-FISH. The acquired field distribution shows good agreement with the simulation results under the same conditions, in direction, magnitude, and shape. This is the first time that E-FISH is applied to streamers of this size (>0.5 cm radius), crossing a large gap. Achieving these high resolution electric field measurements benefits further understanding of streamer discharges and enables future use of E-FISH on cylindrically symmetric (transient) electric field distributions. Published by the American Physical Society 2025

Montana J.R., Souto Arias L.A., Cirillo P., Oosterlee C.W.

We introduce the Quantum Alarm System, a novel framework that combines the informational advantages of quantum majorization applied to tail pseudo-correlation matrices with the learning capabilities of a reinforced urn process, to predict financial turmoil and market crashes. This integration allows for a more nuanced analysis of the dependence structure in financial markets, particularly focusing on extreme events reflected in the tails of the distribution. Our model is tested using the daily log-returns of the 30 constituents of the Dow Jones Industrial Average, spanning from 2 January 1992 to 30 August 2024. The results are encouraging: in the validation set, the 12-month ahead probability of correct alarm is between 73% and 80%, while maintaining a low false alarm rate. Thanks to the application of quantum majorization, the alarm system effectively captures non-traditional and emerging risk sources, such as the financial impact of the COVID-19 pandemic—an area where traditional models often fall short.

Christandl M., Lysikov V., Steffan V., Werner A.H., Witteveen F.

Tensor networks provide succinct representations of quantum many-body states and are an important computational tool for strongly correlated quantum systems. Their expressive and computational power is characterized by an underlying entanglement structure, on a lattice or more generally a (hyper)graph, with virtual entangled pairs or multipartite entangled states associated to (hyper)edges. Changing this underlying entanglement structure into another can lead to both theoretical and computational benefits. We study a natural resource theory which generalizes the notion of bond dimension to entanglement structures using multipartite entanglement. It is a direct extension of resource theories of tensors studied in the context of multipartite entanglement and algebraic complexity theory, allowing for the application of the sophisticated methods developed in these fields to tensor networks. The resource theory of tensor networks concerns both the local entanglement structure of a quantum many-body state and the (algebraic) complexity of tensor network contractions using this entanglement structure. We show that there are transformations between entanglement structures which go beyond edge-by-edge conversions, highlighting efficiency gains of our resource theory that mirror those obtained in the search for better matrix multiplication algorithms. We also provide obstructions to the existence of such transformations by extending a variety of methods originally developed in algebraic complexity theory for obtaining complexity lower bounds. The resource theory of tensor networks allows to compare different entanglement structures and should lead to more efficient tensor network representations and contraction algorithms.

Dieperink M., Skorikov A., Claes N., Bals S., Albrecht W.

Abstract The optical cross sections of plasmonic nanoparticles are intricately linked to their morphologies. Accurately capturing this link could allow determination of particles’ shapes from their optical cross sections alone. Electromagnetic simulations bridge morphology and optical properties, provided they are sufficiently accurate. This study examines key factors affecting simulation precision, comparing common methods and detailing the impacts of meshing accuracy, dielectric function selection, and substrate inclusion within the boundary element method. To support the method’s complex parameterization, we develop a workflow incorporating reconstruction, meshing, and mesh simplification, to enable the use of electron tomography data. We analyze how choices of reconstruction algorithm and image segmentation affect simulated optical cross sections, relating these to shape errors minimized during data processing. Optimal results are obtained using the total variation minimization (TVM) reconstruction method with Otsu thresholding and light smoothing, ensuring reliable, watertight surface meshes through the marching cubes algorithm, even for complex shapes.

Grünwald P., Ramdas A., Wang R., Ziegel J.

This half-size MFO workshop brings together researchers in mathematical statistics, probability theory, machine learning, medical sciences, and economics to discuss recent developments in sequential inference. New sequential inference methods that build on nonnegative martingale techniques allow us to elegantly solve prominent shortcomings of traditional statistical hypothesis tests. Instead of p-values, they are based on e-values which have the added benefit that their meaning is much easier to communicate to applied researchers, due to their intuitive interpretation in terms of the wealth of a gambler playing a hypothetically fair game. Significant new contributions to this fast growing research area will be presented in order to stimulate collaborations, discuss and unify notation and concepts in the fields, and tackle a variety of open problems and address current major challenges.

Smeekes O.S., de Boer T.R., van der Mei R.D., Buurman B.M., Willems H.C.

Acute hospitalization, recurrent admissions, institutionalization, and death are important adverse health outcomes. Older adults receiving home care are especially at risk of these outcomes, yet it remains unclear if this risk differs between older adults receiving different types of home care and older adults not receiving home care.

Schiffer B.F., Vreumingen D.V., Tura J., Polla S.

Transitions out of the ground space limit the performance of quantum adiabatic algorithms, while hardware imperfections impose stringent limitations on the circuit depth. We propose an adiabatic echo verification protocol which mitigates both coherent and incoherent errors, arising from non-adiabatic transitions and hardware noise, respectively. Quasi-adiabatically evolving forward and backward allows for an echo-verified measurement of any observable. In addition to mitigating hardware noise, our method uses positive-time dynamics only. Crucially, the estimator bias of the observable is reduced when compared to standard adiabatic preparation, achieving up to a quadratic improvement.

Coladangelo A., Majenz C., Poremba A.

Copy-protection allows a software distributor to encode a program in such a way that it can be evaluated on any input, yet it cannot be "pirated" – a notion that is impossible to achieve in a classical setting. Aaronson (CCC 2009) initiated the formal study of quantum copy-protection schemes, and speculated that quantum cryptography could offer a solution to the problem thanks to the quantum no-cloning theorem. In this work, we introduce a quantum copy-protection scheme for a large class of evasive functions known as "compute-and-compare programs" – a more expressive generalization of point functions. A compute-and-compare program CC[f,y] is specified by a function f and a string y within its range: on input x, CC[f,y] outputs 1, if f(x)=y, and 0 otherwise. We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM), which makes it the first copy-protection scheme to enjoy any level of provable security in a standard cryptographic model. As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing", introduced very recently by Ananth and La Placa (eprint 2020), with a standard security bound in the QROM, i.e. guaranteeing negligible adversarial advantage. Finally, as a third contribution, we elucidate the relationship between unclonable encryption and copy-protection for multi-bit output point functions.

Cade C., Crichigno P.M.

We consider the complexity of the local Hamiltonian problem in the context of fermionic Hamiltonians with N=2 supersymmetry and show that the problem remains QMA-complete. Our main motivation for studying this is the well-known fact that the ground state energy of a supersymmetric system is exactly zero if and only if a certain cohomology group is nontrivial. This opens the door to bringing the tools of Hamiltonian complexity to study the computational complexity of a large number of algorithmic problems that arise in homological algebra, including problems in algebraic topology, algebraic geometry, and group theory. We take the first steps in this direction by introducing the k-local Cohomology problem and showing that it is QMA1-hard and, for a large class of instances, is contained in QMA. We then consider the complexity of estimating normalized Betti numbers and show that this problem is hard for the quantum complexity class DQC1, and for a large class of instances is contained in BQP. In light of these results, we argue that it is natural to frame many of these homological problems in terms of finding ground states of supersymmetric fermionic systems. As an illustration of this perspective we discuss in some detail the model of Fendley, Schoutens, and de Boer consisting of hard-core fermions on a graph, whose ground state structure encodes l-dimensional holes in the independence complex of the graph. This offers a new perspective on existing quantum algorithms for topological data analysis and suggests new ones.

Libera K., Valadian R., Vararattanavech P., Dasari S.N., Dallman T.J., Weerts E., Lipman L.

In broiler chickens, fractures of wings and legs are recorded at poultry slaughterhouses based on the time of occurrence. Pre-killing (PRE) fractures occur before the death of animal, so the chicken was still able to experience pain and distress associated with the injury (an animal welfare issue). Post-killing (POST) fractures occur when the chickens are deceased and fully bled-out and consequently unable to feel pain (not an animal welfare issue). Current practice dictates that fractures are recognized visually and recorded by the animal welfare officers as mandated by European Union and/or national regulations. However, new potential monitoring solutions are desired since human inspection suffers from some significant limitations including subjectivism and fatigue. One possible solution in detecting injuries is X-ray computed tomography (CT) scanning and in this study we aim to evaluate the potential of CT scanning and visual inspection in detecting limb fractures and their causes. 83 chicken wings and 60 chicken legs (n=143) were collected from a single slaughterhouse and classified by an animal welfare officer as PRE, POST or healthy (HEAL). Samples were photographed and CT scanned at a veterinary hospital. The interpretation of CT scans along with photographs took place in 3 rounds (1. CT scans only, 2. CT scans + photographs, 3. photographs only) and was performed independently by 3 veterinarians. The consistency of the interpretation in 3 rounds was compared with the animal welfare officer`s classification. Furthermore, selected samples were also analyzed by histopathological examination due to questionability of their classification (PRE/POST). In questionable samples presence of hemorrhages were confirmed, thus they fit better as PRE. The highest consistency between raters was obtained in the 2nd round, indicating that interpretation accuracy was the highest when CT scans were combined with photographs. These results indicate that CT scanning in combination with visual inspection can be used in detecting limbs fracture and potentially applied as a tool to monitor animal welfare in poultry slaughterhouses in the future.

Cade C., Folkertsma M., Niesen I., Weggemans J.

Run-times of quantum algorithms are often studied via an asymptotic, worst-case analysis. Whilst useful, such a comparison can often fall short: it is not uncommon for algorithms with a large worst-case run-time to end up performing well on instances of practical interest. To remedy this it is necessary to resort to run-time analyses of a more empirical nature, which for sufficiently small input sizes can be performed on a quantum device or a simulation thereof. For larger input sizes, alternative approaches are required.In this paper we consider an approach that combines classical emulation with detailed complexity bounds that include all constants. We simulate quantum algorithms by running classical versions of the sub-routines, whilst simultaneously collecting information about what the run-time of the quantum routine would have been if it were run instead. To do this accurately and efficiently for very large input sizes, we describe an estimation procedure and prove that it obtains upper bounds on the true expected complexity of the quantum algorithms.We apply our method to some simple quantum speedups of classical heuristic algorithms for solving the well-studied MAX-k-SAT optimization problem. This requires rigorous bounds (including all constants) on the expected- and worst-case complexities of two important quantum sub-routines: Grover search with an unknown number of marked items, and quantum maximum-finding. These improve upon existing results and might be of broader interest.Amongst other results, we found that the classical heuristic algorithms we studied did not offer significant quantum speedups despite the existence of a theoretical per-step speedup. This suggests that an empirical analysis such as the one we implement in this paper already yields insights beyond those that can be seen by an asymptotic analysis alone.

Herasymenko Y., Stroeks M., Helsen J., Terhal B.

We consider the problem of approximating the ground state energy of a fermionic Hamiltonian using a Gaussian state. In sharp contrast to the dense case [1, 2], we prove that strictly q-local sparse fermionic Hamiltonians have a constant Gaussian approximation ratio; the result holds for any connectivity and interaction strengths. Sparsity means that each fermion participates in a bounded number of interactions, and strictly q-local means that each term involves exactly q fermionic (Majorana) operators. We extend our proof to give a constant Gaussian approximation ratio for sparse fermionic Hamiltonians with both quartic and quadratic terms. With additional work, we also prove a constant Gaussian approximation ratio for the so-called sparse SYK model with strictly 4-local interactions (sparse SYK-4 model). In each setting we show that the Gaussian state can be efficiently determined. Finally, we prove that the O(n−1/2) Gaussian approximation ratio for the normal (dense) SYK-4 model extends to SYK-q for even q>4, with an approximation ratio of O(n1/2–q/4). Our results identify non-sparseness as the prime reason that the SYK-4 model can fail to have a constant approximation ratio [1, 2].

Cade C., Labib F., Niesen I.

We present three quantum algorithms for clustering graphs based on higher-order patterns, known as motif clustering. One uses a straightforward application of Grover search, the other two make use of quantum approximate counting, and all of them obtain square-root like speedups over the fastest classical algorithms in various settings. In order to use approximate counting in the context of clustering, we show that for general weighted graphs the performance of spectral clustering is mostly left unchanged by the presence of constant (relative) errors on the edge weights. Finally, we extend the original analysis of motif clustering in order to better understand the role of multiple `anchor nodes' in motifs and the types of relationships that this method of clustering can and cannot capture.

Jansen S., Goodenough K., de Bone S., Gijswijt D., Elkouss D.

Entanglement distillation is an essential building block in quantum communication protocols. Here, we study the class of near-term implementable distillation protocols that use bilocal Clifford operations followed by a single round of communication. We introduce tools to enumerate and optimise over all protocols for up to n=5 (not necessarily equal) Bell-diagonal states using a commodity desktop computer. Furthermore, by exploiting the symmetries of the input states, we find all protocols for up to n=8 copies of a Werner state. For the latter case, we present circuits that achieve the highest fidelity with perfect operations and no decoherence. These circuits have modest depth and number of two-qubit gates. Our results are based on a correspondence between distillation protocols and double cosets of the symplectic group, and improve on previously known protocols.