26838 research outputs found
Sort by
A generalisation of Ville’s inequality to monotonic lower bounds and thresholds
Full text linkEssentially all anytime-valid methods hinge on Ville’s inequality to gain validity across time without incurring a union bound. Ville’s inequality is a proper generalisation of Markov’s inequality. It states that a non-negative supermartingale will only ever reach a multiple of its initial value with small probability. In the classic rendering both the lower bound (of zero) and the threshold are constant in time. We generalise both to monotonic curves. That is, we bound the probability that a supermartingale which remains above a given decreasing curve exceeds a given increasing threshold curve. We show our bound is tight by exhibiting a supermartingale for which the bound is an equality. Using our generalisation, we derive a cleaner finite-time version of the law of the iterated logarithm
Entanglement recycling in two-step port-based teleportation
No full textA protocol involving the repetitive (twofold, to be precise) application of PBT protocol to the same resource is studied. The quantities characterizing the resulting protocol, so-called two-step PBT, namely enatnglement fidelity and success probability are provided for two scenarios, relying on application of pretty-good measurement, i.e. deterministic and probabilistic PBT with non-EPR resource. This results show that two-step PBT is an accurate protocol, provided the resource is sufficiently large. In particular, the deterministic two-step PBT obtains fidelity that is remarkably close to the optimal MPBT fidelity for teleportation of two quantum states. Additionally, the recycling fidelity, i.e. the quantity characterizing the degradation of the resource state is calculated for repetitive application of probabilistic protocol, for both EPR and optimized resource, showing that entanglement recycling with two-step PBT is possible in the former case as well
Generative super-resolution of turbulent flows via stochastic interpolants
No full textCapturing the intricate multiscale features of turbulent flows remains a fundamental challenge due to the limited resolution of experimental data and the computational cost of high-fidelity simulations. In many practical scenarios only coarse representations of the flows are feasible, leaving crucial fine-scale dynamics unresolved. This study addresses that limitation by leveraging generative models to perform super-resolution of velocity fields and reconstruct the unresolved scales from low-resolution conditionals. In particular, the recently formalized stochastic interpolants are employed to super-resolve a case study of two-dimensional turbulence. Key to our approach is the iterative application of stochastic interpolants over local patches of the flow field, that enables efficient reconstruction without the need to process the full domain simultaneously. The patch-wise strategy is shown to yield physically consistent super-resolved flow snapshots, and key statistical quantities – such as the kinetic energy spectrum – are accurately recovered. Moreover, the patch-wise approach is observed to produce super-resolutions of a quality comparable to those produced using a full field approach, and, in general, stochastic interpolants are observed to outperform contesting generative models across a range of metrics. Although only demonstrated for a 2D case study, these results highlight the potential of using stochastic interpolants to super-resolve turbulent flows
Proof of Persistent Aliveness
No full textProof of Aliveness (PoA) has emerged as a useful cryptographic concept for periodically ascertaining the operational status (aliveness) of devices, especially for those in cyber-physical systems. However, existing PoA schemes exhibit shortcomings stemming from intermittent aliveness proofs and a lack of resilience against the threats caused by malicious verifiers. Motivated by this, we introduce a new security notion called Proof of Persistent Aliveness (PoPA), which encompasses two new properties: persistent aliveness (PAlive) and audit (Audit). Our PAlive strengthens prior work by addressing the security concerns associated with generating persistent aliveness proofs in a continuous time manner, while Audit covers the threats posed by malicious verifiers. To efficiently realize PoPA, we developed two new building blocks: a deterministic hash-based Proof of Work (HPoW) scheme and private tweakable hash (PTH) functions. Using these primitives, we propose a scalable and lightweight PoPA construction, named SPAC, which is provably secure in our PoPA model without relying on random oracles. SPAC leverages HPoW and a customized authenticated credential structure that employs a variant of the Winternitz one-time signature scheme derived from PTH, enabling unlimited aliveness proofs with very small proof size. Over 93% of aliveness proofs are 84 bytes in size, with the worst-case proof size being only 372 bytes
Finding the cyclic covers of a string
Full text linkWe introduce the concept of cyclic covers, which generalizes the classical notion of covers in strings. Given any string , a factor of is called a cyclic cover if each position of belongs to an occurrence of a cyclic shift of in . Two cyclic covers are distinct if one is not a cyclic shift of the other. The cyclic covers problem asks for all distinct cyclic covers of an input string . We present an algorithm that solves the cyclic covers problem in time, where is the length of . It is based on finding a well-structured set of standard occurrences of a constant number of factors of a cyclic cover candidate , computing the regions of covered by cyclic shifts of , extending those factors, and taking the union of the results
What promises do AI hold for computational imaging?
No full textAn image says more than a 1000 thousand words, it is said. This also holds true in many scientific applications, where 2D, 3D, or even 4D images are analysed. But how do we compute images from raw measurements, and can AI help us improve? At CWI’s Computational Imaging group in Amsterdam, mathematicians and computer scientists are trying to answer these questions
Empowering quantum computation with: measurements, catalysts, and guiding states
Full text linkDespite rapid advances in quantum hardware and the appearance of the first devices with active error correction by 2025, fully fault-tolerant quantum computation remains a distant milestone. This thesis investigates how additional resources can enhance computational power across various stages of quantum device development.
Part I examines computation before error correction, where only constant-depth circuits are feasible. We introduce LAQCC, which augments such circuits with intermediate measurement and classical computation, and show that this model enables far more powerful computations.
In Part II, we study the early fault-tolerance regime, where the main limitation is the number of logical qubits. Inspired by the classical catalytic space model, we introduce a quantum analogue in which a space-bounded quantum machine has access to an auxiliary catalytic register that may be modified during the computation but must be restored at the end. We show that this catalytic resource increases the power of quantum space-bounded machines.
In Part III, we study the full fault-tolerant regime and look at the problem of estimating the ground-state energy of a Local Hamiltonian which is central to quantum chemistry. Here, we study the BQP-hard Guided Local Hamiltonian problem (estimating ground-state energy given a guiding state), showing its hardness persists over a broader parameter range. Furthermore, by introducing the Guidable Local Hamiltonian problem, we provide complexity-theoretic evidence that classical guiding-state heuristics are as powerful as quantum ones, in this setting. Finally, this problem also provides restrictions on possible gap-amplification procedures, relevant for the quantum PCP conjecture
Supermartingales for one-sided tests: Sufficient monotone likelihood ratios are sufficient
Full text linkThe t-statistic is a widely-used scale-invariant statistic for testing the null hypothesis that the mean is zero. Martingale methods enable sequential testing with the t-statistic at every sample size, while controlling the probability of falsely rejecting the null. For one-sided sequential tests, which reject when the t-statistic is too positive, a natural question is whether they also control false rejection when the true mean is negative. We prove that this is the case using monotone likelihood ratios and sufficient statistics. We develop applications to the scale-invariant t-test, the location-invariant χ 2 -test and sequential linear regression with nuisance covariates