Search

We introduce a quantum-inspired algorithm for Graph Coloring Problems (GCPs) that utilizes qudits in a product state, with each qudit representing a node in the graph and parameterized by d-dimensional spherical coordinates. We propose and benchmark two optimization strategies: qudit gradient descent (QdGD), initiating qudits in random states and employing gradient descent to minimize a cost function, and qudit local quantum annealing (QdLQA), which adapts the local quantum annealing method to optimize an adiabatic transition from a tractable initial function to a problem-specific cost function. Our approaches are benchmarked against established solutions for standard GCPs, showing that our methods not only rival but frequently surpass the performance of recent state-of-the-art algorithms in terms of solution quality and computational efficiency. The adaptability of our algorithm and its high-quality solutions, achieved with minimal computational resources, point to an advancement in the field of quantum-inspired optimization, with potential applications extending to a broad spectrum of optimization problems., Comment: 10 pages, 5 figures

Alternatively to the full reconstruction of an unknown quantum process, the so-called selective and efficient quantum process tomography (SEQPT) allows estimating, individually and up to the required accuracy, a given element of the matrix that describes such an operation with a polynomial amount of resources. The implementation of this protocol has been carried out with success to characterize the evolution of a quantum system that is well described by a trace preserving quantum map. Here, we deal with a more general type of quantum process that does not preserve the trace of the input quantum state, which naturally arises in the presence of imperfect devices and system-environment interactions, in the context of quantum information science or quantum dynamics control. In that case, we show that with the aid of {\it a priori} information on the losses structure of the quantum channel, the SEQPT reconstruction can be adapted to reconstruct the non-trace-preserving map. We explicitly describe how to implement the reconstruction in an arbitrary Hilbert space of finite dimension $d$. The method is experimentally verified on a superconducting quantum processor of the IBM Quantum services, by estimating several non trace-preserving quantum processes in dimensions up to $d=6$. Our results show that it is possible to efficiently reconstruct non trace-preserving processes, with high precision, and with significantly higher fidelity than when the process is assumed to be trace-preserving.

The temporal evolution of a quantum system can be characterized by quantum process tomography, a complex task that consumes a number of physical resources scaling exponentially with the number of subsystems. An alternative approach to the full reconstruction of a quantum channel allows selecting which coefficient from its matrix description to measure, and how accurately, reducing the amount of resources to be polynomial. The possibility of implementing this method is closely related to the possibility of building a complete set of mutually unbiased bases (MUBs) whose existence is known only when the dimension of the Hilbert space is the power of a prime number. However, an extension of the method that uses tensor products of maximal sets of MUBs, has been introduced recently. Here we explicitly describe how to implement this algorithm to selectively and efficiently estimate any parameter characterizing a quantum process in a non-prime power dimension, and we conducted for the first time an experimental verification of the method in a Hilbert space of dimension $d=6$. That is the small space for which there is no known a complete set of MUBs but it can be decomposed as a tensor product of two other Hilbert spaces of dimensions $D_1=2$ and $D_2=3$, for which a complete set of MUBs is known. The $6$-dimensional states were codified in the discretized transverse momentum of the photon wavefront. The state preparation and detection stages are dynamically programmed with the use of only-phase spatial light modulators, in a versatile experimental setup that allows to implement the algorithm in any finite dimension.

We present a characterization of the set of non-signaling correlations in terms of a two dimensional representation that involves the maximal value of a Bell functional and the mutual information between the parties. In particular, we apply this representation to the bipartite Bell scenario with two measurements and two outcomes. In terms of these physically meaningful quantities and through numerical optimization methods and some analytical results, we investigate the frontier between the different subsets of the non-signaling correlations, focussing on the quantum and post-quantum ones. Finally, we show that the Tsirelson bound appears as a singular point in this context without resorting to quantum mechanics., Comment: 9 pages, 9 figures

We consider a toy model for non-local quantum correlations in which nature resorts to some form of hidden signaling (i.e., signaling between boxes but not available to the users) to generate correlations. We show that if such a model also had memory, the parties would be able to exploit the hidden-signaling and use it to send a message, achieving faster-than-light communication. Given that memory is a resource easily available for any physical system, our results add evidence against hidden signaling as the mechanism behind nature's non-local behavior, Comment: 8 pages, 4 figures

The characterization of quantum processes is a key tool in quantum information processing tasks for several reasons: on one hand, it allows to acknowledge errors in the implementations of quantum algorithms; on the other, it allows to charcaterize unknown processes occurring in Nature. In previous works [Bendersky, Pastawski and Paz. Phys. Rev. Lett. 100, 190403 (2008) and Phys. Rev. A 80, 032116 (2009)] it was introduced a method to selectively and efficiently measure any given coefficient from the matrix description of a quantum channel. However, this method heavily relies on the construction of maximal sets of mutually unbiased bases (MUBs), which are known to exist only when the dimension of the Hilbert space is the power of a prime number. In this article, we lift the requirement on the dimension by presenting two variations of the method that work on arbitrary finite dimensions: one uses tensor products of maximally sets of MUBs, and the other uses a dimensional cutoff of a higher prime power dimension., Comment: 8 pages, 3 figures

Martinovic et al. proposed a Brain-Computer-Interface (BCI) -based attack in which an adversary is able to infer private information about a user, such as their bank or area-of-living, by analyzing the user's brain activities. However, a key limitation of the above attack is that it is intrusive, requiring user cooperation, and is thus easily detectable and can be reported to other users. In this paper, we identify and analyze a more serious threat for users of BCI devices. We propose a it subliminal attack in which the victim is attacked at the levels below his cognitive perception. Our attack involves exposing the victim to visual stimuli for a duration of 13.3 milliseconds -- a duration usually not sufficient for conscious perception. The attacker analyzes subliminal brain activity in response to these short visual stimuli to infer private information about the user. If carried out carefully, for example by hiding the visual stimuli within screen content that the user expects to see, the attack may remain undetected. As a consequence, the attacker can scale it to many victims and expose them to the attack for a long time. We experimentally demonstrate the feasibility of our subliminal attack via a proof-of-concept study carried out with 27 subjects. We conducted experiments on users wearing Electroencephalography-based BCI devices, and used portrait pictures of people as visual stimuli which were embedded within the background of an innocuous video for a time duration not exceeding 13.3 milliseconds. Our experimental results show that it is feasible for an attacker to learn relevant private information about the user, such as whether the user knows the identity of the person for which the attacker is probing., Comment: under review for a journal publication

Passwords are widely used for user authentication and, despite their weaknesses, will likely remain in use in the foreseeable future. Human-generated passwords typically have a rich structure, which makes them susceptible to guessing attacks. In this paper, we study the effectiveness of guessing attacks based on Markov models. Our contributions are two-fold. First, we propose a novel password cracker based on Markov models, which builds upon and extends ideas used by Narayanan and Shmatikov (CCS 2005). In extensive experiments we show that it can crack up to 69% of passwords at 10 billion guesses, more than all probabilistic password crackers we compared again t. Second, we systematically analyze the idea that additional personal information about a user helps in speeding up password guessing. We find that, on average and by carefully choosing parameters, we can guess up to 5% more passwords, especially when the number of attempts is low. Furthermore, we show that the gain can go up to 30% for passwords that are actually based on personal attributes. These passwords are clearly weaker and should be avoided. Our cracker could be used by an organization to detect and reject them. To the best of our knowledge, we are the first to systematically study the relationship between chosen passwords and users' personal information. We test and validate our results over a wide collection of leaked password databases.

Suppose you find the same username on different online services, what is the probability that these usernames refer to the same physical person? This work addresses what appears to be a fairly simple question, which has many implications for anonymity and privacy on the Internet. One possible way of estimating this probability would be to look at the public information associated to the two accounts and try to match them. However, for most services, these information are chosen by the users themselves and are often very heterogeneous, possibly false and difficult to collect. Furthermore, several websites do not disclose any additional public information about users apart from their usernames (e.g., discus- sion forums or Blog comments), nonetheless, they might contain sensitive information about users. This paper explores the possibility of linking users profiles only by looking at their usernames. The intuition is that the probability that two usernames refer to the same physical person strongly depends on the "entropy" of the username string itself. Our experiments, based on crawls of real web services, show that a significant portion of the users' profiles can be linked using their usernames. To the best of our knowledge, this is the first time that usernames are considered as a source of information when profiling users on the Internet.

As the amount of personal information stored at remote service providers increases, so does the danger of data theft. When connections to remote services are made in the clear and authenticated sessions are kept using HTTP cookies, data theft becomes extremely easy to achieve. In this paper, we study the architecture of the world's largest service provider, i.e., Google. First, with the exception of a few services that can only be accessed over HTTPS (e.g., Gmail), we find that many Google services are still vulnerable to simple session hijacking. Next, we present the Historiographer, a novel attack that reconstructs the web search history of Google users, i.e., Google's Web History, even though such a service is supposedly protected from session hijacking by a stricter access control policy. The Historiographer uses a reconstruction technique inferring search history from the personalized suggestions fed by the Google search engine. We validate our technique through experiments conducted over real network traffic and discuss possible countermeasures. Our attacks are general and not only specific to Google, and highlight privacy concerns of mixed architectures using both secure and insecure connections., Comment: Our report was sent to Google on February 23rd, 2010. Google is investigating the problem and has decided to temporarily suspend search suggestions from Search History. Furthermore, Google Web History page is now offered over HTTPS only. Updated information about this project is available at: http://planete.inrialpes.fr/projects/private-information-disclosure-from-web-searches