1,721,036 research outputs found
Approximation and relative entropy
No full textWe re-visit the notion of Approximate Confinement in terms of information theory. This notion formalises probabilistic non-interference in terms of process indistinguishability. We show that it corresponds to the notion of relative entropy, aka Kullback-Leibler divergence
The dual value of Probabilistic Abstract interpretation
No full textProbabilistic Abstract Interpretation is a framework for program analysis that allows us to accommodate probabilistic properties and properties of probabilistic computations. We illustrate the dual value of this framework for both deducing and inferring probabilities. More specifically we show the use of PAI for both static analysis and statistical reasoning
Computer Quantistici
No full textCome tutte le grandi scoperte, il computer quantistico nasce da un'idea
visionaria. Nel caso specifico, l'idea fu avanzata dal premio Nobel Richard
P. Feynman che in uno dei suoi più famosi articoli lo suggerì come una
possibile soluzione al problema: `Can physics be simulated by a universal
computer?' In questo articolo, racconteremo l'evoluzione della ricerca
teorica e sperimentale in quell'area che oggi è nota come `computazione
quantistica', dall'idea di Feynman ai nostri giorni, descrivendo i risultati
ottenuti sia nell'ambito della realizzazione fisica del computer quantistico,
sia riguardo ad aspetti più prettamente informatici relativi alla teoria della
calcolabilità e degli algoritmi e complessità
On Quantitative Analysis of Probabilistic Protocols
No full textAbstractWe advocate the use of approximate noninterference for the security analysis of probabilistic protocols. Our approach relies on a formalisation of the protocol in the setting of a probabilistic process algebra and a notion of process similarity based on weak probabilistic bisimulation. We illustrate this approach by presenting the analysis of a probabilistic nonrepudiation protocol which allows us to quantitatively estimate its fairness degree
A Probabilistic Semantics for the Pure Lambda Calculus
No full textFrom a programming language viewpoint, the lambda calculus formalises several features of the modern description of computation and its implementation. We present a denotational semantics for the untyped calculus that captures a basic feature of probabilistic programming languages, namely probability distributions as both the objects and the result of a computation
Facial expression recognition on a quantum computer
No full textWe address the problem of facial expression recognition and show a possible solution using a quantum machine learning approach. In order to define an efficient classifier for a given dataset, our approach substantially exploits quantum interference. By representing face expressions via graphs, we define a classifier as a quantum circuit that manipulates the graphs adjacency matrices encoded into the amplitudes of some appropriately defined quantum states. We discuss the accuracy of the quantum classifier evaluated on the quantum simulator available on the IBM Quantum Experience cloud platform, and compare it with the accuracy of one of the best classical classifier
Higher-Order Topological Kernels via Quantum Computation
No full textTopological data analysis (TDA) has emerged as a powerful tool for extracting meaningful insights from complex data. TDA enhances the analysis of objects by embedding them into a simplicial complex and extracting useful global properties such as the Betti numbers, i.e. the number of multidimensional holes. which can be used to define kernel methods that are easily integrated with existing machine-learning algorithms. These kernel methods have found broad applications, as they rely on powerful mathematical frameworks which provide theoretical guarantees on their performance. However, the computation of higher-dimensional Betti numbers can be prohibitively expensive on classical hardware, while quantum algorithms can approximate them in polynomial time in the instance size. In this work, we propose a quantum approach to defining topological kernels, which is based on constructing Betti curves, i.e. topological fingerprint of filtrations with increasing order. We exhibit a working prototype of our approach implemented on a noiseless simulator and show its robustness by means of some empirical results suggesting that topological approaches may offer an advantage in quantum machine learning
Quantitative Static Analysis of Distributed Systems
No full textWe introduce a quantitative approach to the analysis of distributed systems which relies on a linear operator based network semantics. A typical problem in a distributed setting is how information propagates through a network, and a typical qualitative analysis is concerned with establishing whether some information will eventually be transmitted from one node to another node in the network. The quantitative approach we present allows to obtain additional information such as an estimation of the probability that some data is transmitted within a given interval of time. We formalise situations like this using a probabilistic version of a process calculus which is the core of KLAIM, a language for distributed and mobile computing based on interactions through distributed tuple spaces. The analysis we present exploits techniques based on Probabilistic Abstract Interpretation and is characterised by compositional aspects which greatly simplify the inspection of the nodes interaction and the detection of the information propagation through a computer network
Program Analysis Probably Counts
No full textIn this paper we start by reviewing both classical and probabilistic/quantitative approaches to program analysis. We shall provide a comparison of the two approaches. We shall use a simple information flow analysis to exemplify the classical approach. The existence of covert information flows through timing channels are difficult to detect using classical techniques; we show how such problems can be addressed using probabilistic techniques
Approximate Non-Interference
No full textWe address the problem of characterising the security of a program against unauthorised information flows. Classical approaches are based on non-inter\-ference models which depend ultimately on the notion of process equivalence. In these models confidentiality is an absolute property stating the absence of any illegal information flow. We present a model in which the notion of non-interference is approximated in the sense that it allows for some exactly quantified leakage of information. This is characterised via a notion of process similarity which replaces the indistinguishability of processes by a quantitative measure of their behavioural difference. Such a quantity is related to the number of statistical tests needed to distinguish two behaviours. We also present two semantics-based analyses of approximate non-interference and we show that one is a correct abstraction of the other
- …
