Abstract

In this work we give a (n, n)-threshold protocol for sequential secret sharing of quantum information for the first time. By sequential secret sharing we refer to a situation where the dealer is not having all the secrets at the same time, at the beginning of the protocol; however if the dealer wishes to share secrets at subsequent phases she/he can realize it with the help of our protocol. First of all we present our protocol for three parties and later we generalize it for the situation where we have more (n > 3) parties. Interestingly, we show that our protocol of sequential secret sharing requires less amount of quantum as well as classical resource as compared to the situation wherein existing protocols are repeatedly used. Further in a much more realistic situation, we consider the sharing of qubits through two kinds of noisy channels, namely the phase damping channel (PDC) and the amplitude damping channel (ADC). When we carry out the sequential secret sharing in the presence of noise we observe that the fidelity of secret sharing at the kth iteration is independent of the effect of noise at the (k − 1)th iteration. In case of ADC we have seen that the average fidelity of secret sharing drops down to 1 2 which is equivalent to a random guess of the quantum secret. Interestingly, we find that by applying weak measurements one can enhance the average fidelity. This increase of the average fidelity can be achieved with certain trade off with the success probability of the weak measurements

Abstract

Complementarity have been an intriguing feature of physical systems for a long time. In this work we establish a new kind of complimentary relations in the frame work of quantum information processing tasks. In broadcasting of entanglement we create many pairs of less entangled states from a given entangled state both by local and non local cloning operations. These entangled states can be used in various information processing tasks like teleportation and superdense coding. Since these states are less entangled states it is quite intuitive that these states are not going to be as powerful resource as the initial states. In this work we study the usefulness of these states in tasks like teleportation and super dense coding. More precisely, we found out bounds of their capabilities in terms of several complimentary relations involving fidelity of broadcasting. In principle we have considered general mixed as a resource also separately providing different examples like a) Werner like states, b) Bell diagonal states. Here we have used both local and non local cloning operations as means of broadcasting. In the later part of our work, we extend this result by obtaining bounds in form of complimentary relations in a situation where we have used 1 − N cloning transformations instead of 1 − 2 cloning transformations

Abstract

It has been suggested that there may exist quantum correlations that go beyond entanglement. The existence of such correlations can be revealed by information theoretic quantities such as quantum discord, but not by the conventional measures of entanglement. We argue that a state displays quantumness that can be of local and nonlocal origin. Information theoretic measures not only characterize the nonlocal quantumness but also the local quantumness, such as the “local superposition”. This can be a reason why such measures are nonzero when there is no entanglement. We consider a generalized version of the Werner state to demonstrate the interplay of local quantumness, nonlocal quantumness, and classical mixedness of a state.

Abstract

In a recent work, authors prove a yet another no-go theorem that forbids the existence of a universal probabilistic quantum protocol producing a superposition of two unknown quantum states. In this short note, we show that in the presence of closed time like curves, one can indeed create superposition of unknown quantum states and evade the no-go result.

Abstract

We find a single parameter family of genuinely entangled three qubit pure states, called the maximally Bell inequality violating states (MBV), which exhibit maximum Bell inequality violation by the reduced bipartite system for a fixed amount of genuine tripartite entanglement quantified by the so called tangle measure. This in turn implies that there holds a complementary relation between the Bell inequality violation by the reduced bipartite systems and the tangle present in the three qubit states, not necessarily pure. The MBV states also exhibit maximum Bell inequality violation by the reduced bipartite systems of the three qubit pure states with a fixed amount of genuine tripartite correlation quantified by the generalized geometric measure, a genuine entanglement measure of multiparty pure states, and the discord monogamy score, a multipartite quantum correlation measure from information theoretic paradigm. The aforementioned complementary relation has also been established for three qubit pure states for the generalized geometric measure and the discord monogamy score respectively. The complementarity between the Bell inequality violation by the reduced bipartite systems and the genuine tripartite correlation suggests that the Bell inequality violation in the reduced two qubit system comes at the cost of the total tripartite correlation present in the entire system.

Abstract

In this paper we design and implement an algorithm for finding the biconnected components of a given graph. Our algorithm is based on experimental evidence that finding the bridges of a graph is usually easier and faster in the parallel setting. We use this property to first decompose the graph into independent and maximal 2-edge-connected subgraphs. To identify the articulation points in these 2-edge connected subgraphs, we again convert this into a problem of finding the bridges on an auxiliary graph. It is interesting to note that during the conversion process, the size of the graph may increase. However, we show that this small increase in size and the run time is offset by the consideration that finding bridges is easier in a parallel setting. We implement our algorithm on an Intel i7 980X CPU running 12 threads. We show that our algorithm is on average 2.45 x faster than the best known current algorithms implemented on the same platform. Finally, we extend our approach to dense graphs by applying the sparsification technique suggested by Cong and Bader

Abstract

Computing metrics on nodes of a graph is an essential step in understanding the properties of the graph. Pagerank is one such metric that is popular and is being used to measure the importance of nodes in not only web graphs but also in social networks, biological networks, road networks, and the like. The core of the computation of pagerank can be seen as an iterative approach that updates the pageranks of nodes until the values converge.

Abstract

Parallel graph algorithms continue to attract a lot of research attention given their applications to several fields of sciences and engineering. Efficient design and implementation of graph algorithms on modern manycore accelerators has to however contend with a host of challenges including not being able to reach full memory system throughput and irregularity. Of late, focusing on real-world graphs, researchers are addressing these challenges by using decomposition and preprocessing techniques guided by the structural properties of such graphs. In this direction, we present a new GPU algorithm for obtaining an ear decomposition of a graph. Our implementation of the proposed algorithm on an NVidia Tesla K40c improves the state-of-the-art by a factor of 2.3x on average on a collection of real-world and synthetic graphs. The improved performance of our algorithm is due to our proposed characterization that identifies edges of the graph as redundant for the purposes of an ear decomposition. We then study an application of the ear decomposition of a graph in computing the betweenness-centrality values of nodes in the graph. We use an ear decomposition of the input graph to systematically remove nodes of degree two. The actual computation of betweenness-centrality is done on the remaining nodes and the results are extended to nodes removed in the previous step. We show that this approach improves the state-of-the-art for computing betweenness-centrality on an NVidia K40c GPU by a factor of 1.9x on average over a collection of real-world graphs.

Abstract

This paper extends recent work on vulnerability extrapolation. A surge in vulnerability exploits against old and new softwares, urges the importance of detection of vulnerabilities and possible attacks prior to the attacker. How sophisticated an exploit may be, an underlying prerequisite remains to be the presence of at least one memory corruption bug, serving as entry point for the exploit. Therefore several rigorous software testing techniques are borrowed to detect and eliminate software bugs as early as possible. Code similarity based bug detection is one of such techniques, which, in the parlance of software security, is also termed as vulnerability extrapolation. In this paper, we present a source code similarity based bug identification technique by considering code features that are relevant for security related bugs. Our technique works by enriching (augmenting) abstract syntax trees (ASTs) of functions by considering security relevant properties of the code. We show the effectiveness of the augmented AST based similarity approach over existing methods by evaluating proposed method on real-world applications.

Abstract

Consider a synchronous distributed network which is partly controlled by an adversary. In a Perfectly Secret Message Transmission(PSMT) protocol, the sender S wishes to transmit a message to the receiver R such that the adversary learns nothing about the message. We characterize the set of directed graphs that admit PSMT protocols tolerating a dual failure model where up to tp nodes are passively corrupted and further up to any tf nodes may fail.