Parallel query complexity is a generalization of query complexity in which one is allowed to make several non-adaptive queries to the input in each round. Here one counts the number of such rounds required to compute a function of the input as the complexity. In this talk I will introduce this setting and related background, and discuss some interesting results and problems. The material will all be based on the paper: Quantum advantage and lower bounds in parallel query complexity. The target audience is students who have taken an introductory quantum computing course.

Classical Bayes' rule lays the foundation for the classical causal relation between cause (input) and effect (output). This causal relation is believed to be universally true for all physical processes. Here we show, on the contrary, that it is inadequate to establish correct correspondence between cause and effect in quantum mechanics. In fact, there are instances within the framework of quantum mechanics where the use of classical Bayes' rule leads to inconsistencies in quantum measurement inferences, such as Frauchiger-Renner's paradox. Similar inconsistency also appears in the context of Hardy's setup even after assuming quantum mechanics as a non-local theory. As a remedy, we introduce an input-output causal relation based on quantum Bayes' rule. It applies to general quantum processes even when a cause (or effect) is in coherent superposition with other causes (or effects), involves nonlocal correlations as allowed by quantum mechanics, and in the cases where causes belonging to one system induce effects in some other system as it happens in quantum measurement processes. This enables us to propose a resolution to the contradictions that appear in the context of Frauchiger-Renner's and Hardy's setups. Our results thereby affirm that quantum mechanics, equipped with quantum Bayes' rule, can indeed consistently explain the use of itself.

Entanglement detection and quantification of entanglement are the two most important problems in quantum information theory because quantum entanglement is a key resource in quantum information processing. I will divide the talk into two parts: In the first part I will talk about realignment criterion, which is considered as powerful tool for detection of entangled states in bipartite and multipartite quantum system. It detects not only negative partial transpose entangled states (NPTES) but also detect positive partial transpose entangled states (PPTES). We have approximated the realignment map to a positive map using the method of structural physical approximation (SPA) and then we have shown that the structural physical approximation of realignment map (SPA-R) is completely positive. Positivity of the constructed map is characterized using moments which can be physically measured. Next, we develop a separability criterion based on our SPA-R map in the form of an inequality and have shown that the developed criterion not only detect NPTES but also PPTES. We have provided some examples to support the results obtained. In the second part, we define a physically realizable measure of entanglement for any arbitrary dimensional bipartite system ρ, which we named as structured negativity (NS(ρ)). We have shown that the introduced measure satisfies the properties of a valid entanglement monotone. For d ⊗ d dimensional state, we conjectured that negativity coincides with the structured negativity when the number of negative eigenvalues of the partially transposed matrix is equal to d(d−1)/2. Moreover, we proved that structured negativity may be implemented in the laboratory.