Acín, A, Duan, R, Roberson, DE, Sainz, AB & Winter, A 2017, 'A new property of the Lovász number and duality relations between graph parameters', Discrete Applied Mathematics, vol. 216, no. 3, pp. 489-501.
View/Download from: Publisher's site
View description>>
© 2016 Elsevier B.V.We show that for any graph G, by considering "activation" through the strong product with another graph H, the relation α(G)≤θ(symbol)(G) between the independence number and the Lovász number of G can be made arbitrarily tight: Precisely, the inequality α(G(squared times)H)≤θ(symbol)(G(squared times)H)=θ(symbol)(G)θ(symbol)(H) becomes asymptotically an equality for a suitable sequence of ancillary graphs H.This motivates us to look for other products of graph parameters of G and H on the right hand side of the above relation. For instance, a result of Rosenfeld and Hales states that α(G(squared times)H)≤α*(G)α(H), with the fractional packing number α*(G), and for every G there exists H that makes the above an equality; conversely, for every graph H there is a G that attains equality.These findings constitute some sort of duality of graph parameters, mediated through the independence number, under which α and α* are dual to each other, and the Lovász number θ(symbol) is self-dual. We also show duality of Schrijver's and Szegedy's variants θ(symbol)- and θ(symbol)+ of the Lovász number, and explore analogous notions for the chromatic number under strong and disjunctive graph products.
Alaei, A, Pal, S, Pal, U & Blumenstein, M 2017, 'An Efficient Signature Verification Method Based on an Interval Symbolic Representation and a Fuzzy Similarity Measure', IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, vol. 12, no. 10, pp. 2360-2372.
View/Download from: Publisher's site
Alexander, RN, Gabay, NC, Rohde, PP & Menicucci, NC 2017, 'Measurement-Based Linear Optics', Physical Review Letters, vol. 118, no. 11, pp. 1-6.
View/Download from: Publisher's site
View description>>
© 2017 American Physical Society. A major challenge in optical quantum processing is implementing large, stable interferometers. We offer a novel approach: virtual, measurement-based interferometers that are programed on the fly solely by the choice of homodyne measurement angles. The effects of finite squeezing are captured as uniform amplitude damping. We compare our proposal to existing (physical) interferometers and consider its performance for BosonSampling, which could demonstrate postclassical computational power in the near future. We prove its efficiency in time and squeezing (energy) in this setting.
Berta, M, Fawzi, O & Tomamichel, M 2017, 'On variational expressions for quantum relative entropies', Letters in Mathematical Physics, vol. 107, no. 12, pp. 2239-2265.
View/Download from: Publisher's site
View description>>
© 2017, Springer Science+Business Media B.V. Distance measures between quantum states like the trace distance and the fidelity can naturally be defined by optimizing a classical distance measure over all measurement statistics that can be obtained from the respective quantum states. In contrast, Petz showed that the measured relative entropy, defined as a maximization of the Kullback–Leibler divergence over projective measurement statistics, is strictly smaller than Umegaki’s quantum relative entropy whenever the states do not commute. We extend this result in two ways. First, we show that Petz’ conclusion remains true if we allow general positive operator-valued measures. Second, we extend the result to Rényi relative entropies and show that for non-commuting states the sandwiched Rényi relative entropy is strictly larger than the measured Rényi relative entropy for α∈(12,∞) and strictly smaller for α∈[0,12). The latter statement provides counterexamples for the data processing inequality of the sandwiched Rényi relative entropy for α<12. Our main tool is a new variational expression for the measured Rényi relative entropy, which we further exploit to show that certain lower bounds on quantum conditional mutual information are superadditive.
Bremner, MJ, Montanaro, A & Shepherd, DJ 2017, 'Achieving quantum supremacy with sparse and noisy commuting quantum computations', Quantum, vol. 1, pp. 8-8.
View/Download from: Publisher's site
View description>>
The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.
Chen, J, Guo, C, Ji, Z, Poon, YT, Yu, N, Zeng, B & Zhou, J 2017, 'Joint product numerical range and geometry of reduced density matrices', SCIENCE CHINA Physics, Mechanics and Astronomy, vol. 60, no. 2.
View/Download from: Publisher's site
View description>>
© 2016, Science China Press and Springer-Verlag Berlin Heidelberg. The reduced density matrices of a many-body quantum system form a convex set, whose three-dimensional projection Θ is convex in R3. The boundary ∂Θ of Θ may exhibit nontrivial geometry, in particular ruled surfaces. Two physical mechanisms are known for the origins of ruled surfaces: symmetry breaking and gapless. In this work, we study the emergence of ruled surfaces for systems with local Hamiltonians in infinite spatial dimension, where the reduced density matrices are known to be separable as a consequence of the quantum de Finetti’s theorem. This allows us to identify the reduced density matrix geometry with joint product numerical range Π of the Hamiltonian interaction terms. We focus on the case where the interaction terms have certain structures, such that a ruled surface emerges naturally when taking a convex hull of Π. We show that, a ruled surface on ∂Θ sitting in Π has a gapless origin, otherwise it has a symmetry breaking origin. As an example, we demonstrate that a famous ruled surface, known as the oloid, is a possible shape of Θ, with two boundary pieces of symmetry breaking origin separated by two gapless lines.
Chen, JY, Ji, Z, Liu, ZX, Qi, X, Yu, N, Zeng, B & Zhou, D 2017, 'Physical origins of ruled surfaces on the reduced density matrices geometry', Science in China Series G: Physics Mechanics and Astronomy, vol. 60, no. 2.
View/Download from: Publisher's site
View description>>
© 2016, Science China Press and Springer-Verlag Berlin Heidelberg. The reduced density matrices (RDMs) of many-body quantum states form a convex set. The boundary of low dimensional projections of this convex set may exhibit nontrivial geometry such as ruled surfaces. In this paper, we study the physical origins of these ruled surfaces for bosonic systems. The emergence of ruled surfaces was recently proposed as signatures of symmetry-breaking phase. We show that, apart from being signatures of symmetry-breaking, ruled surfaces can also be the consequence of gapless quantum systems by demonstrating an explicit example in terms of a two-mode Ising model. Our analysis was largely simplified by the quantum de Finetti’s theorem—in the limit of large system size, these RDMs are the convex set of all the symmetric separable states. To distinguish ruled surfaces originated from gapless systems from those caused by symmetry-breaking, we propose to use the finite size scaling method for the corresponding geometry. This method is then applied to the two-mode XY model, successfully identifying a ruled surface as the consequence of gapless systems.
Cheng, HC, Hsieh, MH & Tomamichel, M 2017, 'Exponential decay of matrix Φ-entropies on Markov semigroups with applications to dynamical evolutions of quantum ensembles', Journal of Mathematical Physics, vol. 58, no. 9.
View/Download from: Publisher's site
View description>>
In this work, we extend the theory of quantum Markov processes on a single quantum state to a broader theory that covers Markovian evolution of an ensemble of quantum states, which generalizes Lindblad's formulation of quantum dynamical semigroups. Our results establish the equivalence between an exponential decrease of the matrix Φ-entropies and the Φ-Sobolev inequalities, which allows us to characterize the dynamical evolution of a quantum ensemble to its equilibrium. In particular, we study the convergence rates of two special semigroups, namely, the depolarizing channel and the phase-damping channel. In the former, since there exists a unique equilibrium state, we show that the matrix Φ-entropy of the resulting quantum ensemble decays exponentially as time goes on. Consequently, we obtain a stronger notion of monotonicity of the Holevo quantity-the Holevo quantity of the quantum ensemble decays exponentially in time and the convergence rate is determined by the modified log-Sobolev inequalities. However, in the latter, the matrix Φ-entropy of the quantum ensemble that undergoes the phase-damping Markovian evolution generally will not decay exponentially. There is no classical analogy for these different equilibrium situations. Finally, we also study a statistical mixing of Markov semigroups on matrix-valued functions. We can explicitly calculate the convergence rate of a Markovian jump process defined on Boolean hypercubes and provide upper bounds to the mixing time. Published by AIP Publishing.
Chitambar, E & Hsieh, MH 2017, 'Round complexity in the local transformations of quantum and classical states', Nature Communications, vol. 8, no. 1.
View/Download from: Publisher's site
View description>>
© 2017 The Author(s). In distributed quantum and classical information processing, spatially separated parties operate locally on their respective subsystems, but coordinate their actions through multiple exchanges of public communication. With interaction, the parties can perform more tasks. But how the exact number and order of exchanges enhances their operational capabilities is not well understood. Here we consider the minimum number of communication rounds needed to perform the locality-constrained tasks of entanglement transformation and its classical analog of secrecy manipulation. We provide an explicit construction of both quantum and classical state transformations which, for any given r, can be achieved using r rounds of classical communication exchanges, but no fewer. To show this, we build on the common structure underlying both resource theories of quantum entanglement and classical secret key. Our results reveal that highly complex communication protocols are indeed necessary to fully harness the information-theoretic resources contained in general quantum and classical states.
Chubb, CT, Tan, VYF & Tomamichel, M 2017, 'Moderate Deviation Analysis for Classical Communication over Quantum Channels', Communications in Mathematical Physics, vol. 355, no. 3, pp. 1283-1315.
View/Download from: Publisher's site
View description>>
© 2017, Springer-Verlag GmbH Germany. We analyse families of codes for classical data transmission over quantum channels that have both a vanishing probability of error and a code rate approaching capacity as the code length increases. To characterise the fundamental tradeoff between decoding error, code rate and code length for such codes we introduce a quantum generalisation of the moderate deviation analysis proposed by Altŭg and Wagner as well as Polyanskiy and Verdú. We derive such a tradeoff for classical-quantum (as well as image-additive) channels in terms of the channel capacity and the channel dispersion, giving further evidence that the latter quantity characterises the necessary backoff from capacity when transmitting finite blocks of classical data. To derive these results we also study asymmetric binary quantum hypothesis testing in the moderate deviations regime. Due to the central importance of the latter task, we expect that our techniques will find further applications in the analysis of other quantum information processing tasks.
Coles, PJ, Berta, M, Tomamichel, M & Wehner, S 2017, 'Entropic uncertainty relations and their applications', Reviews of Modern Physics, vol. 89, no. 1, pp. 1-58.
View/Download from: Publisher's site
View description>>
© 2017 American Physical Society. Heisenberg's uncertainty principle forms a fundamental element of quantum mechanics. Uncertainty relations in terms of entropies were initially proposed to deal with conceptual shortcomings in the original formulation of the uncertainty principle and, hence, play an important role in quantum foundations. More recently, entropic uncertainty relations have emerged as the central ingredient in the security analysis of almost all quantum cryptographic protocols, such as quantum key distribution and two-party quantum cryptography. This review surveys entropic uncertainty relations that capture Heisenberg's idea that the results of incompatible measurements are impossible to predict, covering both finite- and infinite-dimensional measurements. These ideas are then extended to incorporate quantum correlations between the observed object and its environment, allowing for a variety of recent, more general formulations of the uncertainty principle. Finally, various applications are discussed, ranging from entanglement witnessing to wave-particle duality to quantum cryptography.
Deng, Y & Feng, Y 2017, 'Probabilistic bisimilarity as testing equivalence', Information and Computation, vol. 257, pp. 58-64.
View/Download from: Publisher's site
View description>>
© 2017 Elsevier Inc. Larsen and Skou initiated the study of probabilistic bisimilarity and its characterisation in terms of tests. Later on, van Breugel et al. showed that, for labelled Markov processes with continuous state spaces, probabilistic bisimilarity nicely coincides with a simple notion of testing equivalence. Their proof employs advanced machinery from topology. In the discrete case of finite-state reactive probabilistic processes, we prove that coincidence result with an elementary and more accessible proof.
Feng, Y & Zhang, L 2017, 'Precisely deciding CSL formulas through approximate model checking for CTMCs', Journal of Computer and System Sciences, vol. 89, pp. 361-371.
View/Download from: Publisher's site
View description>>
© 2017 Elsevier Inc. The model checking problem of continuous-time Markov chains with respect to continuous-time stochastic logic was introduced and shown to be decidable by Aziz et al. [1,2 in 1996. Unfortunately, their proof is only constructive, but highly unpractical. Later in 2000, an efficient approximate algorithm was proposed by Baier et al. [3,5 for a sublogic with binary until. In this paper, we apply transcendental number theory and classical linear algebra to bridge the gap between the precise but unpractical algorithm, and the imprecise but efficient approximate algorithm. We prove that the approximate algorithm in [3,5 can be used as an off-the-shell tool for a precise model checking algorithm for binary until formulas. Further, we discuss extensions of our results to nested until and continuous-time Markov decision processes.
Freer, S, Simmons, S, Laucht, A, Muhonen, JT, Dehollain, JP, Kalra, R, Mohiyaddin, FA, Hudson, FE, Itoh, KM, McCallum, JC, Jamieson, DN, Dzurak, AS & Morello, A 2017, 'A single-atom quantum memory in silicon', QUANTUM SCIENCE AND TECHNOLOGY, vol. 2, no. 1.
View/Download from: Publisher's site
Granade, C, Ferrie, C & Flammia, ST 2017, 'Practical adaptive quantum tomography', New Journal of Physics, vol. 19, no. 11, pp. 1-16.
View/Download from: Publisher's site
View description>>
© 2017 IOP Publishing Ltd and Deutsche Physikalische Gesellschaft. We introduce a fast and accurate heuristic for adaptive tomography that addresses many of the limitations of prior methods. Previous approaches were either too computationally intensive or tailored to handle special cases such as single qubits or pure states. By contrast, our approach combines the efficiency of online optimization with generally applicable and well-motivated data-processing techniques. We numerically demonstrate these advantages in several scenarios includ ing mixed states, higher-dimensional systems, and restricted measurements.
Granade, C, Ferrie, C, Hincks, I, Casagrande, S, Alexander, T, Gross, J, Kononenko, M & Sanders, Y 2017, 'QInfer: Statistical inference software for quantum applications', QUANTUM, vol. 1.
View/Download from: Publisher's site
Grochow, JA & Qiao, Y 2017, 'ALGORITHMS FOR GROUP ISOMORPHISM VIA GROUP EXTENSIONS AND COHOMOLOGY', SIAM JOURNAL ON COMPUTING, vol. 46, no. 4, pp. 1153-1216.
View/Download from: Publisher's site
Haah, J, Harrow, AW, Ji, Z, Wu, X & Yu, N 2017, 'Sample-Optimal Tomography of Quantum States', IEEE Transactions on Information Theory, vol. 63, no. 9, pp. 5628-5641.
View/Download from: Publisher's site
View description>>
© 1963-2012 IEEE. It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error \epsilon in trace distance required O(dr^{2}/\epsilon ^{2}) copies for a d -dimensional density matrix of rank r. Here, we give a theoretical measurement scheme (POVM) that requires O (dr/ \delta) \ln ~(d/\delta) copies to estimate \rho to error \delta in infidelity, and a matching lower bound up to logarithmic factors. This implies O((dr / \epsilon ^{2}) \ln ~(d/\epsilon)) copies suffice to achieve error \epsilon in trace distance. We also prove that for independent (product) measurements, \Omega (dr^{2}/\delta ^{2}) / \ln (1/\delta) copies are necessary in order to achieve error \delta in infidelity. For fixed d , our measurement can be implemented on a quantum computer in time polynomial in n.
Harper, R, Chapman, RJ, Ferrie, C, Granade, C, Kueng, R, Naoumenko, D, Flammia, ST & Peruzzo, A 2017, 'Explaining quantum correlations through evolution of causal models', Physical Review A, vol. 95, no. 4, pp. 1-16.
View/Download from: Publisher's site
View description>>
© 2017 American Physical Society. We propose a framework for the systematic and quantitative generalization of Bell's theorem using causal networks. We first consider the multiobjective optimization problem of matching observed data while minimizing the causal effect of nonlocal variables and prove an inequality for the optimal region that both strengthens and generalizes Bell's theorem. To solve the optimization problem (rather than simply bound it), we develop a genetic algorithm treating as individuals causal networks. By applying our algorithm to a photonic Bell experiment, we demonstrate the trade-off between the quantitative relaxation of one or more local causality assumptions and the ability of data to match quantum correlations.
Herr, D, Nori, F & Devitt, SJ 2017, 'Lattice surgery translation for quantum computation', New Journal of Physics, vol. 19, no. 1, pp. 1-24.
View/Download from: Publisher's site
View description>>
� 2017 IOP Publishing Ltd and Deutsche Physikalische Gesellschaft. In this paper we outline a method for a compiler to translate any non fault tolerant quantum circuit to the geometric representation of the lattice surgery error-correcting code using inherent merge and split operations. Since the efficiency of state distillation procedures has not yet been investigated in the lattice surgery model, their translation is given as an example using the proposed method. The resource requirements seem comparable or better to the defect-based state distillation process, but modularity and eventual implementability allow the lattice surgery model to be an interesting alternative to braiding.
Herr, D, Nori, F & Devitt, SJ 2017, 'Optimization of lattice surgery is NP-hard', npj Quantum Information, vol. 3, no. 1, pp. 1-5.
View/Download from: Publisher's site
View description>>
The traditional method for computation in either the surface code or in the Raussendorf model is the creation of holes or “defects” within the encoded lattice of qubits that are manipulated via topological braiding to enact logic gates. However, this is not the only way to achieve universal, fault-tolerant computation. In this work, we focus on the lattice surgery representation, which realizes transversal logic operations without destroying the intrinsic 2D nearest-neighbor properties of the braid-based surface code and achieves universality without defects and braid-based logic. For both techniques there are open questions regarding the compilation and resource optimization of quantum circuits. Optimization in braid-based logic is proving to be difficult and the classical complexity associated with this problem has yet to be determined. In the context of lattice-surgery-based logic, we can introduce an optimality condition, which corresponds to a circuit with the lowest resource requirements in terms of physical qubits and computational time, and prove that the complexity of optimizing a quantum circuit in the lattice surgery model is NP-hard.
Hiai, F, König, R & Tomamichel, M 2017, 'Generalized Log-Majorization and Multivariate Trace Inequalities', Annales Henri Poincaré, vol. 18, no. 7, pp. 2499-2521.
View/Download from: Publisher's site
View description>>
© 2017, Springer International Publishing. We show that recent multivariate generalizations of the Araki–Lieb–Thirring inequality and the Golden–Thompson inequality (Sutter et al. in Commun Math Phys, 2016. doi:10.1007/s00220-016-2778-5) for Schatten norms hold more generally for all unitarily invariant norms and certain variations thereof. The main technical contribution is a generalization of the concept of log-majorization which allows us to treat majorization with regard to logarithmic integral averages of vectors of singular values.
Ivanyos, G, Qiao, Y & Subrahmanyam, KV 2017, 'Non-commutative Edmonds’ problem and matrix semi-invariants', Computational Complexity, vol. 26, no. 3, pp. 717-763.
View/Download from: Publisher's site
View description>>
© 2016, Springer International Publishing. In 1967, J. Edmonds introduced the problem of computing the rank over the rational function field of an n× n matrix T with integral homogeneous linear polynomials. In this paper, we consider the non-commutative version of Edmonds’ problem: compute the rank of T over the free skew field. This problem has been proposed, sometimes in disguise, from several different perspectives in the study of, for example, the free skew field itself (Cohn in J Symbol Log 38(2):309–314, 1973), matrix spaces of low rank (Fortin-Reutenauer in Sémin Lothar Comb 52:B52f 2004), Edmonds’ original problem (Gurvits in J Comput Syst Sci 69(3):448–484, 2004), and more recently, non-commutative arithmetic circuits with divisions (Hrubeš and Wigderson in Theory Comput 11:357-393, 2015. doi:10.4086/toc.2015.v011a014). It is known that this problem relates to the following invariant ring, which we call the F-algebra of matrix semi-invariants, denoted as R(n, m). For a field F, it is the ring of invariant polynomials for the action of SL (n, F) × SL (n, F) on tuples of matrices—(A, C) ∈ SL (n, F) × SL (n, F) sends (B 1 , … , B m ) ∈ M(n, F) ⊕ m to (AB 1 C T , … , AB m C T ). Then those T with non-commutative rank < n correspond to those points in the nullcone of R(n, m). In particular, if the nullcone of R(n, m) is defined by elements of degree ≤ σ, then there follows a poly (n, σ) -time randomized algorithm to decide whether the non-commutative rank of T is full. To our knowledge, previously the best bound for σ was O(n2·4n2) over algebraically closed fields of characteristic 0 (Derksen in Proc Am Math Soc 129(4):955–964, 2001). We now state the main contributions of this paper:We observe that by using an algorithm of Gurvits, and assuming the above bound σ for R(n, m) over Q, deciding whether or not T has non-commutative rank < n over Q can be done deterministically in time polynomial in the input size and σ.When F is large enough, we devise an a...
Khare, V, Shivakumara, P, Paramesran, R & Blumenstein, M 2017, 'Arbitrarily-oriented multi-lingual text detection in video', Multimedia Tools and Applications, vol. 76, no. 15, pp. 16625-16655.
View/Download from: Publisher's site
View description>>
© 2016 Springer Science+Business Media New YorkText detection in arbitrarily-oriented multi-lingual video is an emerging area of research because it plays a vital role for developing real-time indexing and retrieval systems. In this paper, we propose to explore moments for identifying text candidates. We introduce a novel idea for determining automatic windows to extract moments for tackling multi-font and multi-sized text in video based on stroke width information. The temporal information is explored to find deviations between moving and non-moving pixels in successive frames iteratively, which results in static clusters containing caption text and dynamic clusters containing scene text, as well as background pixels. The gradient directions of pixels in static and dynamic clusters are analyzed to identify the potential text candidates. Furthermore, boundary growing is proposed that expands the boundary of potential text candidates until it finds neighbor components based on the nearest neighbor criterion. This process outputs text lines appearing in the video. Experimental results on standard video data, namely, ICDAR 2013, ICDAR 2015, YVT videos and on our own English and Multi-lingual videos demonstrate that the proposed method outperforms the state-of-the-art methods.
Kieferova, M & Wiebe, N 2017, 'Tomography and generative training with quantum Boltzmann machines', PHYSICAL REVIEW A, vol. 96, no. 6.
View/Download from: Publisher's site
Kong, S, Li, S, Li, Y & Long, Z 2017, 'On tree-preserving constraints', Annals of Mathematics and Artificial Intelligence, vol. 81, no. 3-4, pp. 241-271.
View/Download from: Publisher's site
View description>>
© 2017, Springer International Publishing Switzerland. The study of tractable subclasses of constraint satisfaction problems is a central topic in constraint solving. Tree convex constraints are extensions of the well-known row convex constraints. Just like the latter, every path-consistent tree convex constraint network is globally consistent. However, it is NP-complete to decide whether a tree convex constraint network has solutions. This paper studies and compares three subclasses of tree convex constraints, which are called chain-, path-, and tree-preserving constraints respectively. The class of tree-preserving constraints strictly contains the subclasses of path-preserving and arc-consistent chain-preserving constraints. We prove that, when enforcing strong path-consistency on a tree-preserving constraint network, in each step, the network remains tree-preserving. This ensures the global consistency of consistent tree-preserving networks after enforcing strong path-consistency, and also guarantees the applicability of the partial path-consistency algorithms to tree-preserving constraint networks, which is usually much more efficient than the path-consistency algorithms for large sparse constraint networks. As an application, we show that the class of tree-preserving constraints is useful in solving the scene labelling problem.
Lai, CY & Duan, R 2017, 'On the one-shot zero-error classical capacity of classical-quantum channels assisted by quantum non-signalling correlations', Quantum Information and Computation, vol. 17, no. 5-6, pp. 380-398.
View/Download from: Publisher's site
View description>>
© Rinton Press. Duan and Winter studied the one-shot zero-error classical capacity of a quantum channel assisted by quantum non-signalling correlations, and formulated this problem as a semidefinite program depending only on the Kraus operator space of the channel. For the class of classical-quantum channels, they showed that the asymptotic zero-error classical capacity assisted by quantum non-signalling correlations, minimized over all classicalquantum channels with a confusability graph G, is exactly log v(G), where v(G) is the celebrated Lovász theta function. In this paper, we show that the one-shot capacity for a classical-quantum channel, induced from a circulant graph G defined by equal-sized cyclotomic cosets, is log⌊v(G)⌋, which further implies that its asymptotic capacity is log v(G). This type of graphs include the cycle graphs of odd length, the Paley graphs of prime vertices, and the cubit residue graphs of prime vertices. Examples of other graphs are also discussed. This gives Lovász v function another operational meaning in zero-error classical-quantum communication.
Langford, NK, Sagastizabal, R, Kounalakis, M, Dickel, C, Bruno, A, Luthi, F, Thoen, DJ, Endo, A & DiCarlo, L 2017, 'Experimentally simulating the dynamics of quantum light and matter at deep-strong coupling.', Nature Communications, vol. 8, no. 1, pp. 1715-1715.
View/Download from: Publisher's site
View description>>
The quantum Rabi model describing the fundamental interaction between light and matter is a cornerstone of quantum physics. It predicts exotic phenomena like quantum phase transitions and ground-state entanglement in ultrastrong and deep-strong coupling regimes, where coupling strengths are comparable to or larger than subsystem energies. Demonstrating dynamics remains an outstanding challenge, the few experiments reaching these regimes being limited to spectroscopy. Here, we employ a circuit quantum electrodynamics chip with moderate coupling between a resonator and transmon qubit to realise accurate digital quantum simulation of deep-strong coupling dynamics. We advance the state of the art in solid-state digital quantum simulation by using up to 90 second-order Trotter steps and probing both subsystems in a combined Hilbert space dimension of ∼80, demonstrating characteristic Schrödinger-cat-like entanglement and large photon build-up. Our approach will enable exploration of extreme coupling regimes and quantum phase transitions, and demonstrates a clear first step towards larger complexities such as in the Dicke model.
Laucht, A, Kalra, R, Simmons, S, Dehollain, JP, Muhonen, JT, Mohiyaddin, FA, Freer, S, Hudson, FE, Itoh, KM, Jamieson, DN, McCallum, JC, Dzurak, AS & Morello, A 2017, 'A dressed spin qubit in silicon', NATURE NANOTECHNOLOGY, vol. 12, no. 1, pp. 61-66.
View/Download from: Publisher's site
Lekitsch, B, Weidt, S, Fowler, AG, Mølmer, K, Devitt, SJ, Wunderlich, C & Hensinger, WK 2017, 'Blueprint for a microwave trapped ion quantum computer', Science Advances, vol. 3, no. 2, pp. 1-11.
View/Download from: Publisher's site
View description>>
2017 © The Authors, some rights reserved. The availability of a universal quantum computer may have a fundamental impact on a vast number of research fields and on society as a whole. An increasingly large scientific and industrial community is working toward the realization of such a device. An arbitrarily large quantum computer may best be constructed using a modular approach. We present a blueprint for a trapped ion–based scalable quantum computer module, making it possible to create a scalable quantum computer architecture based on long-wavelength radiation quantum gates. The modules control all operations as stand-alone units, are constructed using silicon microfabrication techniques, and are within reach of current technology. To perform the required quantum computations, the modules make use of long-wavelength radiation–based quantum gate technology. To scale this microwave quantum computer architecture to a large size, we present a fully scalable design that makes use of ion transport between different modules, thereby allowing arbitrarily many modules to be connected to construct a large-scale device. A high error–threshold surface error correction code can be implemented in the proposed architecture to execute fault-tolerant operations. With appropriate adjustments, the proposed modules are also suitable for alternative trapped ion quantum computer architectures, such as schemes using photonic interconnects.
Li, Y & Qiao, Y 2017, 'On rank-critical matrix spaces', Differential Geometry and its Application, vol. 55, pp. 68-77.
View/Download from: Publisher's site
View description>>
© 2017 Elsevier B.V. A matrix space of size m×n is a linear subspace of the linear space of m×n matrices over a field F. The rank of a matrix space is defined as the maximal rank over matrices in this space. A matrix space A is called rank-critical, if any matrix space which properly contains it has rank strictly greater than that of A. In this note, we first exhibit a necessary and sufficient condition for a matrix space A to be rank-critical, when F is large enough. This immediately implies the sufficient condition for a matrix space to be rank-critical by Draisma (2006) [5], albeit requiring the field to be slightly larger. We then study rank-critical spaces in the context of compression and primitive matrix spaces. We first show that every rank-critical matrix space can be decomposed into a rank-critical compression matrix space and a rank-critical primitive matrix space. We then prove, using our necessary and sufficient condition, that the block-diagonal direct sum of two rank-critical matrix spaces is rank-critical if and only if both matrix spaces are primitive, when the field is large enough.
Li, Y, Wang, X & Duan, R 2017, 'Indistinguishability of bipartite states by positive-partial-transpose operations in the many-copy scenario', Physical Review A, vol. 95, no. 5, pp. 052346-1-052346-6.
View/Download from: Publisher's site
Lund, AP, Bremner, MJ & Ralph, TC 2017, 'Quantum sampling problems, BosonSampling and quantum supremacy', npj Quantum Information, vol. 3, no. 1, pp. 1-8.
View/Download from: Publisher's site
View description>>
© 2017 by the Authors. There is a large body of evidence for the potential of greater computational power using information carriers that are quantum mechanical over those governed by the laws of classical mechanics. But the question of the exact nature of the power contributed by quantum mechanics remains only partially answered. Furthermore, there exists doubt over the practicality of achieving a large enough quantum computation that definitively demonstrates quantum supremacy. Recently the study of computational problems that produce samples from probability distributions has added to both our understanding of the power of quantum algorithms and lowered the requirements for demonstration of fast quantum algorithms. The proposed quantum sampling problems do not require a quantum computer capable of universal operations and also permit physically realistic errors in their operation. This is an encouraging step towards an experimental demonstration of quantum algorithmic supremacy. In this paper, we will review sampling problems and the arguments that have been used to deduce when sampling problems are hard for classical computers to simulate. Two classes of quantum sampling problems that demonstrate the supremacy of quantum algorithms are BosonSampling and Instantaneous Quantum Polynomial-time Sampling. We will present the details of these classes and recent experimental progress towards demonstrating quantum supremacy in BosonSampling.
Motes, KR, Olson, JP, Rabeaux, EJ, Dowling, JP, Olson, SJ & Rohde, PP 2017, 'Linear Optical Quantum Metrology with Single Photons: Exploiting Spontaneously Generated Entanglement to Beat the Shot-Noise Limit (vol 114, 170802, 2015)', Physical Review Letters, vol. 118, no. 7.
View/Download from: Publisher's site
Mukhopadhyay, P & Qiao, Y 2017, 'Sparse multivariate polynomial interpolation on the basis of Schubert polynomials', Computational Complexity, pp. 1-29.
View/Download from: Publisher's site
View description>>
© 2016 Springer International PublishingSchubert polynomials were discovered by A. Lascoux and M. Schützenberger in the study of cohomology rings of flag manifolds in 1980s. These polynomials generalize Schur polynomials and form a linear basis of multivariate polynomials. In 2003, Lenart and Sottile introduced skew Schubert polynomials, which generalize skew Schur polynomials and expand in the Schubert basis with the generalized Littlewood–Richardson coefficients. In this paper, we initiate the study of these two families of polynomials from the perspective of computational complexity theory. We first observe that skew Schubert polynomials, and therefore Schubert polynomials, are in #P (when evaluating on nonnegative integral inputs) and VNP. Our main result is a deterministic algorithm that computes the expansion of a polynomial f of degree d in (Formula presented.) on the basis of Schubert polynomials, assuming an oracle computing Schubert polynomials. This algorithm runs in time polynomial in n, d, and the bit size of the expansion. This generalizes, and derandomizes, the sparse interpolation algorithm of symmetric polynomials in the Schur basis by Barvinok and Fomin (Adv Appl Math 18(3):271–285, 1997). In fact, our interpolation algorithm is general enough to accommodate any linear basis satisfying certain natural properties. Applications of the above results include a new algorithm that computes the generalized Littlewood–Richardson coefficients.
Nagayama, S, Fowler, AG, Horsman, D, Devitt, SJ & Meter, RV 2017, 'Surface code error correction on a defective lattice', New Journal of Physics, vol. 19, no. 2, pp. 1-29.
View/Download from: Publisher's site
View description>>
© 2017 IOP Publishing Ltd and Deutsche Physikalische Gesellschaft. The yield of physical qubits fabricated in the laboratory is much lower than that of classical transistors in production semiconductor fabrication. Actual implementations of quantum computers will be susceptible to loss in the form of physically faulty qubits. Though these physical faults must negatively affect the computation, we can deal with them by adapting error-correction schemes. In this paper we have simulated statically placed single-fault lattices and lattices with randomly placed faults at functional qubit yields of 80%, 90%, and 95%, showing practical performance of a defective surface code by employing actual circuit constructions and realistic errors on every gate, including identity gates. We extend Stace et al's superplaquettes solution against dynamic losses for the surface code to handle static losses such as physically faulty qubits [1]. The single-fault analysis shows that a static loss at the periphery of the lattice has less negative effect than a static loss at the center. The randomly faulty analysis shows that 95% yield is good enough to build a large-scale quantum computer. The local gate error rate threshold is , and a code distance of seven suppresses the residual error rate below the original error rate at . 90% yield is also good enough when we discard badly fabricated quantum computation chips, while 80% yield does not show enough error suppression even when discarding 90% of the chips. We evaluated several metrics for predicting chip performance, and found that the average of the product of the number of data qubits and the cycle time of a stabilizer measurement of stabilizers gave the strongest correlation with logical error rates. Our analysis will help with selecting usable quantum computation chips from among the pool of all fabricated chips.
Nemoto, K, Devitt, S & Munro, WJ 2017, 'Noise management to achieve superiority in quantum information systems', Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 375, no. 2099.
View/Download from: Publisher's site
View description>>
© 2017 The Author(s) Published by the Royal Society. All rights reserved. Quantum information systems are expected to exhibit superiority compared with their classical counterparts. This superiority arises from the quantum coherences present in these quantum systems, which are obviously absent in classical ones. To exploit such quantum coherences, it is essential to control the phase information in the quantum state. The phase is analogue in nature, rather than binary. This makes quantum information technology fundamentally different from our classical digital information technology. In this paper, we analyse error sources and illustrate how these errors must be managed for the system to achieve the required fidelity and a quantum superiority.
Olson, JP, Motes, KR, Birchall, PM, Studer, NM, Laborde, M, Moulder, T, Rohde, PP & Dowling, JP 2017, 'Linear optical quantum metrology with single photons: Experimental errors, resource counting, and quantum Cramér-Rao bounds', Physical Review A, vol. 96, no. 1, pp. 1-10.
View/Download from: Publisher's site
View description>>
© 2017 American Physical Society. Quantum number-path entanglement is a resource for supersensitive quantum metrology and in particular provides for sub-shot-noise or even Heisenberg-limited sensitivity. However, such number-path entanglement is thought to have been resource intensive to create in the first place, typically requiring either very strong nonlinearities or nondeterministic preparation schemes with feedforward, which are difficult to implement. Recently [K. R. Motes, Phys. Rev. Lett. 114, 170802 (2015)PRLTAO0031-900710.1103/PhysRevLett.114.170802], it was shown that number-path entanglement from a BosonSampling inspired interferometer can be used to beat the shot-noise limit. In this paper we compare and contrast different interferometric schemes, discuss resource counting, calculate exact quantum Cramér-Rao bounds, and study details of experimental errors.
Paler, A, Polian, I, Nemoto, K & Devitt, SJ 2017, 'Fault-tolerant, high-level quantum circuits: Form, compilation and description', Quantum Science and Technology, vol. 2, no. 2.
View/Download from: Publisher's site
View description>>
© 2017 IOP Publishing Ltd. Fault-tolerant quantum error correction is a necessity for any quantum architecture destined to tackle interesting, large-scale problems. Its theoretical formalism has been well founded for nearly two decades. However, we still do not have an appropriate compiler to produce a fault-tolerant, error-corrected description from a higher-level quantum circuit for state-of the-art hardware models. There are many technical hurdles, including dynamic circuit constructions that occur when constructing fault-tolerant circuits with commonly used error correcting codes. We introduce a package that converts high-level quantum circuits consisting of commonly used gates into a form employing all decompositions and ancillary protocols needed for fault-tolerant error correction. We call this form the (I)initialisation, (C)NOT, (M)measurement form (ICM) and consists of an initialisation layer of qubits into one of four distinct states, a massive, deterministic array of CNOT operations and a series of time-ordered X- or Z-basis measurements. The form allows a more flexible approach towards circuit optimisation. At the same time, the package outputs a standard circuit or a canonical geometric description which is a necessity for operating current state-of-the-art hardware architectures using topological quantum codes.
Peng, H, Lan, C, Liu, Y, Liu, T, Blumenstein, M & Li, J 2017, 'Chromosome preference of disease genes and vectorization for the prediction of non-coding disease genes.', Oncotarget, vol. 8, no. 45, pp. 78901-78916.
View/Download from: Publisher's site
View description>>
Disease-related protein-coding genes have been widely studied, but disease-related non-coding genes remain largely unknown. This work introduces a new vector to represent diseases, and applies the newly vectorized data for a positive-unlabeled learning algorithm to predict and rank disease-related long non-coding RNA (lncRNA) genes. This novel vector representation for diseases consists of two sub-vectors, one is composed of 45 elements, characterizing the information entropies of the disease genes distribution over 45 chromosome substructures. This idea is supported by our observation that some substructures (e.g., the chromosome 6 p-arm) are highly preferred by disease-related protein coding genes, while some (e.g., the 21 p-arm) are not favored at all. The second sub-vector is 30-dimensional, characterizing the distribution of disease gene enriched KEGG pathways in comparison with our manually created pathway groups. The second sub-vector complements with the first one to differentiate between various diseases. Our prediction method outperforms the state-of-the-art methods on benchmark datasets for prioritizing disease related lncRNA genes. The method also works well when only the sequence information of an lncRNA gene is known, or even when a given disease has no currently recognized long non-coding genes.
Shivakumara, P, Wu, L, Lu, T, Tan, CL, Blumenstein, M & Anami, BS 2017, 'Fractals based multi-oriented text detection system for recognition in mobile video images', Pattern Recognition, vol. 68, pp. 158-174.
View/Download from: Publisher's site
View description>>
© 2017 Elsevier Ltd Text detection in mobile video is challenging due to poor quality, complex background, arbitrary orientation and text movement. In this work, we introduce fractals for text detection in video captured by mobile cameras. We first use fractal properties such as self-similarity in a novel way in the gradient domain for enhancing low resolution mobile video. We then propose to use k-means clustering for separating text components from non-text ones. To make the method font size independent, fractal expansion is further explored in the wavelet domain in a pyramid structure for text components in text cluster to identify text candidates. Next, potential text candidates are obtained by studying the optical flow property of text candidates. Direction guided boundary growing is finally proposed to extract multi-oriented texts. The method is tested on different datasets, which include low resolution video captured by mobile, benchmark ICDAR 2013 video, YouTube Video Text (YVT) data, ICDAR 2013, Microsoft, and MSRA arbitrary orientation natural scene datasets, to evaluate the performance of the proposed method in terms of recall, precision, F-measure and misdetection rate. To show the effectiveness of the proposed method, the results are compared with the state of the art methods.
Su, Z-E, Li, Y, Rohde, PP, Huang, H-L, Wang, X-L, Li, L, Liu, N-L, Dowling, JP, Lu, C-Y & Pan, J-W 2017, 'Multiphoton Interference in Quantum Fourier Transform Circuits and Applications to Quantum Metrology.', Physical Review Letters, vol. 119, no. 8, pp. 1-5.
View/Download from: Publisher's site
View description>>
Quantum Fourier transforms (QFTs) have gained increased attention with the rise of quantum walks, boson sampling, and quantum metrology. Here, we present and demonstrate a general technique that simplifies the construction of QFT interferometers using both path and polarization modes. On that basis, we first observe the generalized Hong-Ou-Mandel effect with up to four photons. Furthermore, we directly exploit number-path entanglement generated in these QFT interferometers and demonstrate optical phase supersensitivities deterministically.
Sutter, D, Berta, M & Tomamichel, M 2017, 'Multivariate Trace Inequalities', Communications in Mathematical Physics, vol. 352, no. 1, pp. 37-58.
View/Download from: Publisher's site
Tomamichel, M & Leverrier, A 2017, 'A largely self-contained and complete security proof for quantum key distribution', Quantum, vol. 1, pp. 14-52.
View/Download from: Publisher's site
View description>>
In this work we present a security analysis for quantum key distribution, establishing a rigorous tradeoff between various protocol and security parameters for a class of entanglement-based and prepare-and-measure protocols. The goal of this paper is twofold: 1) to review and clarify the stateof-the-art security analysis based on entropic uncertainty relations, and 2) to provide an accessible resource for researchers interested in a security analysis of quantum cryptographic protocols that takes into account finite resource effects. For this purpose we collect and clarify several arguments spread in the literature on the subject with the goal of making this treatment largely self-contained.
More precisely, we focus on a class of prepare-and-measure protocols based on the Bennett-Brassard (BB84) protocol as well as a class of entanglement-based protocols similar to the Bennett-Brassard-Mermin (BBM92) protocol. We carefully formalize the different steps in these protocols, including randomization, measurement, parameter estimation, error correction and privacy amplification, allowing us to be mathematically precise throughout the security analysis. We start from an operational definition of what it means for a quantum key distribution protocol to be secure and derive simple conditions that serve as sufficient condition for secrecy and correctness. We then derive and eventually discuss tradeoff relations between the block length of the classical computation, the noise tolerance, the secret key length and the security parameters for our protocols. Our results significantly improve upon previously reported tradeoffs.
Tomamichel, M, Martinez-Mateo, J, Pacher, C & Elkouss, D 2017, 'Fundamental finite key limits for one-way information reconciliation in quantum key distribution', Quantum Information Processing, vol. 16, no. 11.
View/Download from: Publisher's site
View description>>
© 2017, Springer Science+Business Media, LLC. The security of quantum key distribution protocols is guaranteed by the laws of quantum mechanics. However, a precise analysis of the security properties requires tools from both classical cryptography and information theory. Here, we employ recent results in non-asymptotic classical information theory to show that one-way information reconciliation imposes fundamental limitations on the amount of secret key that can be extracted in the finite key regime. In particular, we find that an often used approximation for the information leakage during information reconciliation is not generally valid. We propose an improved approximation that takes into account finite key effects and numerically test it against codes for two probability distributions, that we call binary–binary and binary–Gaussian, that typically appear in quantum key distribution protocols.
Tomamichel, M, Wilde, MM & Winter, A 2017, 'Strong Converse Rates for Quantum Communication', IEEE Transactions on Information Theory, vol. 63, no. 1, pp. 715-727.
View/Download from: Publisher's site
View description>>
© 2016 IEEE. We revisit a fundamental open problem in quantum information theory, namely whether it is possible to transmit quantum information at a rate exceeding the channel capacity if we allow for a non-vanishing probability of decoding error. Here we establish that the Rains information of any quantum channel is a strong converse rate for quantum communication: For any sequence of codes with rate exceeding the Rains information of the channel, we show that the fidelity vanishes exponentially fast as the number of channel uses increases. This remains true even if we consider codes that perform classical post-processing on the transmitted quantum data. As an application of this result, for generalized dephasing channels we show that the Rains information is also achievable, and thereby establish the strong converse property for quantum communication over such channels. Thus we conclusively settle the strong converse question for a class of quantum channels that have a non-trivial quantum capacity.
Wang, X & Duan, R 2017, 'Irreversibility of Asymptotic Entanglement Manipulation Under Quantum Operations Completely Preserving Positivity of Partial Transpose.', Physical Review Letters, vol. 119, no. 18, pp. 1-5.
View/Download from: Publisher's site
View description>>
We demonstrate the irreversibility of asymptotic entanglement manipulation under quantum operations that completely preserve the positivity of partial transpose (PPT), resolving a major open problem in quantum information theory. Our key tool is a new efficiently computable additive lower bound for the asymptotic relative entropy of entanglement with respect to PPT states, which can be used to evaluate the entanglement cost under local operations and classical communication (LOCC). We find that for any rank-two mixed state supporting on the 3⊗3 antisymmetric subspace, the amount of distillable entanglement by PPT operations is strictly smaller than one entanglement bit (ebit) while its entanglement cost under PPT operations is exactly one ebit. As a by-product, we find that for this class of states, both the Rains's bound and its regularization are strictly less than the asymptotic relative entropy of entanglement. So, in general, there is no unique entanglement measure for the manipulation of entanglement by PPT operations. We further show a computable sufficient condition for the irreversibility of entanglement distillation by LOCC (or PPT) operations.
Wang, X & Duan, R 2017, 'Nonadditivity of Rains' bound for distillable entanglement', Physical Review A, vol. 95, no. 6, pp. 062322-1-062322-5.
View/Download from: Publisher's site
View description>>
Rains' bound is arguably the best known upper bound of the distillable entanglement by operations completely preserving positivity of partial transpose (PPT) and was conjectured to be additive and coincide with the asymptotic relative entropy of entanglement. We disprove both conjectures by explicitly constructing a special class of mixed two-qubit states. We then introduce an additive semidefinite programming lower bound (EM) for the asymptotic Rains' bound, and it immediately becomes a computable lower bound for entanglement cost of bipartite states. Furthermore, EM is also proved to be the best known upper bound of the PPT-assisted deterministic distillable entanglement and gives the asymptotic rates for all pure states and some class of genuinely mixed states.
Wilde, MM, Tomamichel, M & Berta, M 2017, 'Converse Bounds for Private Communication Over Quantum Channels', IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 63, no. 3, pp. 1792-1817.
View/Download from: Publisher's site
Wilde, MM, Tomamichel, M, Lloyd, S & Berta, M 2017, 'Gaussian Hypothesis Testing and Quantum Illumination', Physical Review Letters, vol. 119, no. 12.
View/Download from: Publisher's site
View description>>
© 2017 American Physical Society. Quantum hypothesis testing is one of the most basic tasks in quantum information theory and has fundamental links with quantum communication and estimation theory. In this paper, we establish a formula that characterizes the decay rate of the minimal type-II error probability in a quantum hypothesis test of two Gaussian states given a fixed constraint on the type-I error probability. This formula is a direct function of the mean vectors and covariance matrices of the quantum Gaussian states in question. We give an application to quantum illumination, which is the task of determining whether there is a low-reflectivity object embedded in a target region with a bright thermal-noise bath. For the asymmetric-error setting, we find that a quantum illumination transmitter can achieve an error probability exponent stronger than a coherent-state transmitter of the same mean photon number, and furthermore, that it requires far fewer trials to do so. This occurs when the background thermal noise is either low or bright, which means that a quantum advantage is even easier to witness than in the symmetric-error setting because it occurs for a larger range of parameters. Going forward from here, we expect our formula to have applications in settings well beyond those considered in this paper, especially to quantum communication tasks involving quantum Gaussian channels.
Xie, W, Fang, K, Wang, X & Duan, R 2017, 'Approximate broadcasting of quantum correlations', PHYSICAL REVIEW A, vol. 96, no. 2.
View/Download from: Publisher's site
Xin, T, Lu, D, Klassen, J, Yu, N, Ji, Z, Chen, J, Ma, X, Long, G, Zeng, B & Laflamme, R 2017, 'Quantum State Tomography via Reduced Density Matrices.', Physical Review Letters, vol. 118, no. 2, pp. 020401-020401.
View/Download from: Publisher's site
View description>>
Quantum state tomography via local measurements is an efficient tool for characterizing quantum states. However, it requires that the original global state be uniquely determined (UD) by its local reduced density matrices (RDMs). In this work, we demonstrate for the first time a class of states that are UD by their RDMs under the assumption that the global state is pure, but fail to be UD in the absence of that assumption. This discovery allows us to classify quantum states according to their UD properties, with the requirement that each class be treated distinctly in the practice of simplifying quantum state tomography. Additionally, we experimentally test the feasibility and stability of performing quantum state tomography via the measurement of local RDMs for each class. These theoretical and experimental results demonstrate the advantages and possible pitfalls of quantum state tomography with local measurements.
Ying, M, Ying, S & Wu, X 2017, 'Invariants of quantum programs: characterisations and generation', ACM SIGPLAN Notices, vol. 52, no. 1, pp. 818-832.
View/Download from: Publisher's site
Ying, S, Ying, M & Feng, Y 2017, 'Quantum Privacy-Preserving Data Analytics.', CoRR, vol. abs/1702.04420.
Ying, S, Ying, M & Feng, Y 2017, 'Quantum Privacy-Preserving Perceptron.', CoRR, vol. abs/1707.09893.
Yu, N, Duan, R & Xu, Q 2017, 'Bounds on the Distance Between a Unital Quantum Channel and the Convex Hull of Unitary Channels', IEEE Transactions on Information Theory, vol. 63, no. 2, pp. 1299-1310.
View/Download from: Publisher's site
View description>>
© 2016 IEEE. Motivated by the recent resolution of asymptotic quantum birkhoff conjecture (AQBC), we attempt to estimate the distance between a given unital quantum channel and the convex hull of unitary channels. We provide two lower bounds on this distance by employing techniques from quantum information and operator algebras, respectively. We then show how to apply these results to construct some explicit counterexamples to AQBC. We also point out an interesting connection between the Grothendieck's inequality and AQBC.
Adak, C, Chaudhuri, BB & Blumenstein, M 2017, 'Impact of struck-out text on writer identification', Proceedings of the International Joint Conference on Neural Networks, International Joint Conference on Neural Networks, IEEE, Anchorage, AK, USA, pp. 1465-1471.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. The presence of struck-out text in handwritten manuscripts may affect the accuracy of automated writer identification. This paper presents a study on such effects of struck-out text. Here we consider offline English and Bengali handwritten document images. At first, the struck-out texts are detected using a hybrid classifier of a CNN (Convolutional Neural Network) and an SVM (Support Vector Machine). Then the writer identification process is activated on normal and struck-out text separately, to ascertain the impact of struck-out texts. For writer identification, we use two methods: (a) a hand-crafted feature-based SVM classifier, and (b) CNN-extracted auto-derived features with a recurrent neural model. For the experimental analysis, we have generated a database from 100 English and 100 Bengali writers. The performance of our system is very encouraging.
Adak, C, Chaudhuri, BB & Blumenstein, M 2017, 'Legibility and Aesthetic Analysis of Handwriting', Proceedings of the International Conference on Document Analysis and Recognition, ICDAR, IAPR International Conference on Document Analysis and Recognition, IEEE, Kyoto, Japan, pp. 175-182.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. This paper deals with computer-based cognitive analysis towards legibility and aesthetics of a handwritten document. The legible text creates a human perception that the writing can be read effortlessly because of its orthographic clarity. The aesthetic property relates to the beautiful appearance of a handwritten document. In this study, we deal with these properties on offline Bengali handwriting. We formulate both legibility and aesthetic analysis tasks as machine learning problems supervised by the human cognitive system. We employ automatically derived feature-based recurrent neural networks to investigate writing legibility. For aesthetics evaluation, we employ hand-crafted feature-based support vector machines (SVMs). We have collected contemporary Bengali handwritings, on which the subjective legibility and aesthetic scores are provided by human readers. On this corpus containing legibility and aesthetic ground-Truth information, we executed our experiments. The experimental results obtained on various handwritings are encouraging.
Alaei, F, Alaei, A, Blumenstein, M & Pal, U 2016, 'Document image retrieval based on texture features and similarity fusion', Proceedings of the International Conference Image and Vision Computing New Zealand, International Conference on Image and Vision Computing New Zealand, IEEE, Palmerston North, New Zealand, pp. 1-6.
View/Download from: Publisher's site
View description>>
© 2016 IEEE. In this paper we investigate the usefulness of two different texture features along with classification fusion for document image retrieval. A local binary texture method, as a statistical approach, and a wavelet analysis technique, as a transform-based approach, are used for feature extraction and two feature vectors are obtained for every document image. The similarity distances between each of the two feature vectors extracted for a given query and the feature vectors extracted from the document images in the training step are computed separately. In order to use the properties of both features, a classifier fusion technique is then employed using a weighted average fusion of distance measures obtained in relation to each feature vector. The document images are finally ranked based on the greatest visual similarity to the query obtained from the fusion similarity measures. The Media Team Document Database, which provides a great variety of page layouts and contents, is considered for evaluating the proposed method. The results obtained from the experiments demonstrate a correct document retrieval of 65.4% and 91.8% in the Top-1 and Top-10 ranked document list, respectively.
Alaei, F, Alaei, A, Pal, U & Blumenstein, M 2017, 'Fast local binary pattern: Application to document image retrieval', International Conference Image and Vision Computing New Zealand, International Conference Image and Vision Computing New Zealand, IEEE, Christchurch, New Zealand, pp. 1-6.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. The volume of digitised documents is increasing every day. Thus, designing a fast document image retrieval method for the large volume of document images, especially when the document images are also large in size, is of high demand. As feature extraction is one of the important steps in every document image retrieval system, a feature extraction technique with a low computing time and small feature number has a direct effect on the speed of the retrieval system. In this paper, we propose a non-parametric texture feature extraction method based on summarising the local grey-level structure of the image. To extract the proposed features, the input image is, at first, divided into a set of overlapping patches of equal size. The peripheral pixels of the centre pixel in a patch are used to extract two sets of patterns. The patterns are derived from the vertical & horizontal, and diagonal & off-diagonal pixels of the patch, separately. From each set of pixels, 15 different local binary patterns are extracted in our proposed feature extraction method. Two histograms of the local binary patterns are then created and concatenated to obtain 30 features called fast local binary pattern (F-LBP). To evaluate the efficiency of the proposed feature extraction method, MTDB and ITESOFT databases were considered for experimentation. The proposed F-LBP provided promising results with lower computing time as well as smaller memory space consumption compared to other variation of LBP methods.
Anshu, A, Touchette, D, Yao, P & Yu, N 2017, 'Exponential separation of quantum communication and classical information', Proceedings of the Annual ACM Symposium on Theory of Computing, Annual ACM SIGACT Symposium on Theory of Computing, ACM, Montreal, Canada, pp. 277-288.
View/Download from: Publisher's site
View description>>
© 2017 ACM. We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the other direction was already known from the work of Kerenidis et. al. [SICOMP 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable. As classical information complexity is an upper bound on quantum information complexity, which in turn is equal to amortized quantum communication complexity, our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold. Motivated by the celebrated results of Ganor, Kol and Raz [FOCS 14, pp. 557-566, STOC 15, pp. 977-986], and by Rao and Sinha [ECCC TR15-057], we use the Symmetric k-ary Pointer Jumping function, whose classical communication complexity is exponentially larger than its classical information complexity. In this paper, we show that the quantum communication complexity of this function is polynomially equivalent to its classical communication complexity. The high-level idea behind our proof is arguably the simplest so far for such an exponential separation between information and communication, driven by a sequence of round-elimination arguments, allowing us to simplify further the approach of Rao and Sinha. As another application of the techniques that we develop, we give a simple proof for an optimal trade-off between Alice's and Bob's communication while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/2O(b)bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.
Bei, X, Qiao, Y & Zhang, S 2017, 'Networked fairness in cake cutting', IJCAI International Joint Conference on Artificial Intelligence, pp. 3632-3638.
View description>>
We introduce a graphical framework for fair division in cake cutting, where comparisons between agents are limited by an underlying network structure. We generalize the classical fairness notions of envy-freeness and proportionality to this graphical setting. Given a simple undirected graph G, an allocation is envy-free on G if no agent envies any of her neighbor's share, and is proportional on G if every agent values her own share no less than the average among her neighbors, with respect to her own measure. These generalizations open new research directions in developing simple and efficient algorithms that can produce fair allocations under specific graph structures. On the algorithmic frontier, we first propose a moving-knife algorithm that outputs an envy-free allocation on trees. The algorithm is significantly simpler than the discrete and bounded envy-free algorithm recently designed in [Aziz and Mackenzie, 2016a] for complete graphs. Next, we give a discrete and bounded algorithm for computing a proportional allocation on descendant graphs, a class of graphs by taking a rooted tree and connecting all its ancestor-descendant pairs.
Belovs, A, Ivanyos, G, Qiao, Y, Santha, M & Yang, S 2017, 'On the polynomial parity argument complexity of the combinatorial nullstellensatz', Leibniz International Proceedings in Informatics, LIPIcs.
View/Download from: Publisher's site
View description>>
© Aleksandrs Belovs, Gabor Ivanyos, Youming Qiao, Miklos Santha, and Siyi Yang. The complexity class PPA consists of NP-search problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from graph theory, combinatorics, algebra and number theory, but only a few of these are known to be complete in the class. Before this work, the known complete problems were all discretizations or combinatorial analogues of topological fixed point theorems. Here we prove the PPA-completeness of two problems of radically different style. They are PPA-Circuit CNSS and PPA-Circuit Chevalley, related respectively to the Combinatorial Nullstellensatz and to the Chevalley-Warning Theorem over the two elements field F2. The input of these problems contain PPA-circuits which are arithmetic circuits with special symmetric properties that assure that the polynomials computed by them have always an even number of zeros. In the proof of the result we relate the multilinear degree of the polynomials to the parity of the maximal parse subcircuits that compute monomials with maximal multilinear degree, and we show that the maximal parse subcircuits of a PPA-circuit can be paired in polynomial time.
Blumenstein, M, Rokne, J & Srivastava, J 2017, 'IEEE/ACM ASONAM 2017 message from the general chairs', Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2017, pp. xvi-xvii.
Cheng, EJ, Prasad, M, Puthal, D, Sharma, N, Prasad, OK, Chin, PH, Lin, CT & Blumenstein, M 2017, 'Deep Learning Based Face Recognition with Sparse Representation Classification', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 665-674.
View/Download from: Publisher's site
View description>>
© 2017, Springer International Publishing AG. Feature extraction is an essential step in solving real-world pattern recognition and classification problems. The accuracy of face recognition highly depends on the extracted features to represent a face. The traditional algorithms uses geometric techniques, comprising feature values including distance and angle between geometric points (eyes corners, mouth extremities, and nostrils). These features are sensitive to the elements such as illumination, variation of poses, various expressions, to mention a few. Recently, deep learning techniques have been very effective for feature extraction, and deep features have considerable tolerance for various conditions and unconstrained environment. This paper proposes a two layer deep convolutional neural network (CNN) for face feature extraction and applied sparse representation for face identification. The sparsity and selectivity of deep features can strengthen sparseness for the solution of sparse representation, which generally improves the recognition rate. The proposed method outperforms other feature extraction and classification methods in terms of recognition accuracy.
Cheng, HC & Hsieh, MH 2017, 'Moderate deviations for classical-quantum channels', IEEE International Symposium on Information Theory - Proceedings, IEEE International Symposium on Information Theory, IEEE, Aachen, Germany, pp. 296-300.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. "To be considered for the 2017 IEEE Jack Keil Wolf ISIT Student Paper Award." We show that the reliable communication through a classical-quantum channel is possible when the transmission rate approaches the channel capacity sufficiently slowly. This scenario exists between the non-vanishing error probability regime, where the rate tends to capacity with a fixed error, and the small error probability regime, where the error vanishes given a rate below capacity. The proof employs a sharp concentration bound in strong large deviation theory, and the asymptotic expansions of the error-exponent functions.
Cheng, HC & Hsieh, MH 2017, 'Moderate deviations for quantum hypothesis testing and a martingale inequality', 2017 IEEE International Symposium on Information Theory (ISIT), International Symposium on Information Theory, IEEE, Aachen, Germany, pp. 1978-1982.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. 'To be considered for the 2017 IEEE Jack Keil Wolf ISIT Student Paper Award.' We study the asymptotic behavior of the type-I error in quantum hypothesis testing when the exponent of the type-II error approaches the quantum relative entropy sufficiently slowly. Our result shows that the moderate deviation principle holds for the testing problem if the quantum relative variance is positive. Our proof strategy employs strong large deviation theory and a martingale inequality.
Cheng, HC, Hsieh, MH & Tomamichel, M 2017, 'Sphere-packing bound for classical-quantum channels', IEEE International Symposium on Information Theory - Proceedings, IEEE Information Theory Workshop, IEEE, Kaohsiung, Taiwan, pp. 479-483.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. We study lower bounds on the optimal error probability in channel coding at rates below capacity, commonly termed sphere-packing bounds. In this work, we establish a sphere-packing bound for classical-quantum channels, which significantly improves previous prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(log n/n), indicating our sphere-packing bound is almost exact in the high rate regime. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.
Cheng, HC, Hsieh, MH & Tomamichel, M 2017, 'Sphere-packing bound for symmetric classical-quantum channels', IEEE International Symposium on Information Theory - Proceedings, IEEE International Symposium on Information Theory, IEEE, Aachen, Germany, pp. 286-290.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. "To be considered for the 2017 IEEE Jack Keil Wolf ISIT Student Paper Award." We provide a sphere-packing lower bound for the optimal error probability in finite blocklengths when coding over a symmetric classical-quantum channel. Our result shows that the pre-factor can be significantly improved from the order of the subexponential to the polynomial, This established pre-factor is arguably optimal because it matches the best known random coding upper bound in the classical case. Our approaches rely on a sharp concentration inequality in strong large deviation theory and crucial properties of the error-exponent function.
Coluccia, A, Ghenescu, M, Piatrik, T, De Cubber, G, Schumann, A, Sommer, L, Klatte, J, Schuchert, T, Beyerer, J, Farhadi, M, Amandi, R, Aker, C, Kalkan, S, Saqib, M, Sharma, N, Makkah, SDK & Blumenstein, M 2017, 'Drone-vs-Bird detection challenge at IEEE AVSS2017', Proceedings of the 2017 14th IEEE International Conference on Advanced Video and Signal Based Surveillance, AVSS 2017, IEEE International Conference on Advanced Video and Signal Based Surveillance, IEEE, Lecce, Italy, pp. 1-6.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. Small drones are a rising threat due to their possible misuse for illegal activities, in particular smuggling and terrorism. The project SafeShore, funded by the European Commission under the Horizon 2020 program, has launched the 'drone-vs-bird detection challenge' to address one of the many technical issues arising in this context. The goal is to detect a drone appearing at some point in a video where birds may be also present: the algorithm should raise an alarm and provide a position estimate only when a drone is present, while not issuing alarms on birds. This paper reports on the challenge proposal, evaluation, and results1.
Das, A, Mondal, P, Pal, U, Blumenstein, M & Ferrer, MA 2017, 'Sclera vessel pattern synthesis based on a non-parametric texture synthesis technique', Advances in Intelligent Systems and Computing, International Conference on Computer Vision and Image Processing, Springer Link, pp. 241-250.
View/Download from: Publisher's site
View description>>
© Springer Science+Business Media Singapore 2017. This work proposes a sclera vessel texture pattern synthesis technique. Sclera texture was synthesized by a non-parametric based texture regeneration technique. A small number of classes from the UBIRIS version: 1 dataset was employed as primitive images. An appreciable result was achieved which solicits the successful synthesis of sclera texture patterns. It is difficult to get a huge collection real sclera data and hence such synthetic data will be useful to the researchers.
Das, A, Pal, U, Ferrer, MA & Blumenstein, M 2017, 'A decision-level fusion strategy for multimodal ocular biometric in visible spectrum based on posterior probability', IEEE International Joint Conference on Biometrics, IJCB 2017, IEEE International Joint Conference on Biometrics, IEEE, Denver, CO, USA, pp. 794-798.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. In this work, we propose a posterior probability-based decision-level fusion strategy for multimodal ocular biometric in the visible spectrum employing iris, sclera and peri-ocular trait. To best of our knowledge this is the first attempt to design a multimodal ocular biometrics using all three ocular traits. Employing all these traits in combination can help to increase the reliability and universality of the system. For instance in some scenarios, the sclera and iris can be highly occluded or for completely closed eyes scenario, the peri-ocular trait can be relied on for the decision. The proposed system is constituted of three independent traits and their combinations. The classification output of the trait which produces highest posterior probability is to consider as the final decision. An appreciable reliability and universal applicability of ocular trait are achieved in experiments conducted employing the proposed scheme.
Das, A, Pal, U, Ferrer, MA, Blumenstein, M, Štepec, D, Rot, P, Emeršič, Ž, Peer, P, Štruc, V, Kumar, SVA & Harish, BS 2017, 'SSERBC 2017: Sclera segmentation and eye recognition benchmarking competition', IEEE International Joint Conference on Biometrics, IJCB 2017, IEEE International Joint Conference on Biometrics, Denver, CO, USA, pp. 742-747.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. This paper summarises the results of the Sclera Segmentation and Eye Recognition Benchmarking Competition (SSERBC 2017). It was organised in the context of the International Joint Conference on Biometrics (IJCB 2017). The aim of this competition was to record the recent developments in sclera segmentation and eye recognition in the visible spectrum (using iris, sclera and peri-ocular, and their fusion), and also to gain the attention of researchers on this subject. In this regard, we have used the Multi-Angle Sclera Dataset (MASD version 1). It is comprised of2624 images taken from both the eyes of 82 identities. Therefore, it consists of images of 164 (82×2) eyes. A manual segmentation mask of these images was created to baseline both tasks. Precision and recall based statistical measures were employed to evaluate the effectiveness of the segmentation and the ranks of the segmentation task. Recognition accuracy measure has been employed to measure the recognition task. Manually segmented sclera, iris and peri-ocular regions were used in the recognition task. Sixteen teams registered for the competition, and among them, six teams submitted their algorithms or systems for the segmentation task and two of them submitted their recognition algorithm or systems. The results produced by these algorithms or systems reflect current developments in the literature of sclera segmentation and eye recognition, employing cutting edge techniques. The MASD version 1 dataset with some of the ground truth will be freely available for research purposes. The success of the competition also demonstrates the recent interests of researchers from academia as well as industry on this subject.
Das, A, Sengupta, A, Ferrer, MA, Pal, U & Blumenstein, M 2017, 'Linking face images captured from the optical phenomenon in the wild for forensic science', IEEE International Joint Conference on Biometrics, IJCB 2017, IEEE International Joint Conference on Biometrics, IEEE, Denver, CO, USA, pp. 781-786.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. This paper discusses the possibility of use of some challenging face images scenario captured from optical phenomenon in the wild for forensic purpose towards individual identification. Occluded and under cover face images in surveillance scenario can be collected from its reflection on a surrounding glass or on a smooth wall that is under the coverage of the surveillance camera and such scenario of face images can be linked for forensic purposes. Another similar scenario that can also be used for forensic is the face images of an individual standing behind a transparent glass wall. To investigate the capability of these images for personal identification this study is conducted. This work investigated different types of features employed in the literature to establish individual identification by such degraded face images. Among them, local region based featured worked best. To achieve higher accuracy and better facial features face image were cropped manually along its close bounding box and noise removal was performed (reflection, etc.). In order to experiment we have developed a database considering the above mentioned scenario, which will be publicly available for academic research. Initial investigation substantiates the possibility of using such face images for forensic purpose.
Farhood, H, He, XS, Jia, W, Blumenstein, M & Li, H 2017, 'Counting People based on Linear, Weighted and Local Random Forest', Prcoeedings of the 2017 International Conference on Digital Image Computing: Techniques and Applications (DICTA), The International Conference on Digital Image Computing: Techniques and Applications, IEEE, Sydney, pp. 1-7.
View/Download from: Publisher's site
View description>>
Recently, many works have been published for counting people. However, when being applied to real-world train station videos, they have exposed many limitations due to problems such as low resolution, heavy occlusion, various density levels and perspective distortions. In this paper, following the recent trend of regression-based density estimation, we present a linear regression approach based on local Random Forests for counting either standing or moving people on station platforms. By dividing each frame into sub-windows and extracting features with ground truth densities as well as learned weights, we perform a linear transformation for counting people to overcome the perspective problems of the existing patch-based approaches. We present improvements against several recent baselines on the UCSD dataset and a dataset of CCTV videos taken from a train station. We also show improvements in speed compared with the state-of-the-art models based on detection and Deep Learning.
Feng, Y & Deng, Y 2017, 'Bisimulations for probabilistic linear lambda calculi', 2017 International Symposium on Theoretical Aspects of Software Engineering (TASE), International Symposium on Theoretical Aspects of Software Engineering, IEEE, Sophia Antipolis, France.
View/Download from: Publisher's site
View description>>
We investigate a notion of probabilistic program equivalence under linear contexts. We show that both a statebased and a distribution-based bisimilarity are sound coinductive proof techniques for reasoning about higher-order probabilistic programs, but only the distribution-based one is complete for linear contextual equivalence. The completeness proof is novel and directly constructs linear contexts from transitions, rather than the traditional approach of characterizing bisimilarities as testing equivalences.
Feng, Y, Hahn, EM, Turrini, A & Ying, S 2017, 'Model checking ω-regular properties for quantum Markov chains', 28th International Conference on Concurrency Theory (CONCUR 2017), International Conference on Concurrency Theory, Leibniz International Proceedings in Informatics, Berlin, Germany.
View/Download from: Publisher's site
View description>>
© Yuan Feng, Ernst Moritz Hahn, Andrea Turrini, and Shenggang Ying. Quantum Markov chains are an extension of classical Markov chains which are labelled with super-operators rather than probabilities. They allow to faithfully represent quantum programs and quantum protocols. In this paper, we investigate model checking !-regular properties, a very general class of properties (including, e.g., LTL properties) of interest, against this model. For classical Markov chains, such properties are usually checked by building the product of the model with a language automaton. Subsequent analysis is then performed on this product. When doing so, one takes into account its graph structure, and for instance performs different analyses per bottom strongly connected component (BSCC). Unfortunately, for quantum Markov chains such an approach does not work directly, because super-operators behave differently from probabilities. To overcome this problem, we transform the product quantum Markov chain into a single super-operator, which induces a decomposition of the state space (the tensor product of classical state space and the quantum one) into a family of BSCC subspaces. Interestingly, we show that this BSCC decomposition provides a solution to the issue of model checking ω-regular properties for quantum Markov chains.
Ivanyos, G, Qiao, Y & Venkata Subrahmanyam, K 2017, 'Constructive non-commutative rank computation is in deterministic polynomial time', Leibniz International Proceedings in Informatics, LIPIcs, Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl, Berkeley, CA, USA, pp. 1-18.
View/Download from: Publisher's site
View description>>
Let B be a linear space of matrices over a field F spanned by n × n matrices B1, . . . ,Bm. The non-commutative rank of B is the minimum r € N such that there exists U < Fnsatisfying dim(U) - dim(B(U)) n - r, where B(U) := span(Ui2€[m]Bi(U)). Computing the non-commutative rank generalizes some well-known problems including the bipartite graph maximum matching problem and the linear matroid intersection problem. In this paper we give a deterministic polynomial-Time algorithm to compute the non-commutative rank over any field F. Prior to our work, such an algorithm was only known over the rational number field Q, a result due to Garg et al, [20]. Our algorithm is constructive and produces a witness certifying the non-commutative rank, a feature that is missing in the algorithm from [20]. Our result is built on techniques which we developed in a previous paper [24], with a new reduction procedure that helps to keep the blow-up parameter small. There are two ways to realize this reduction. The first involves constructivizing a key result of Derksen and Makam [12] which they developed in order to prove that the null cone of matrix semi-invariants is cut out by generators whose degree is polynomial in the size of the matrices involved. We also give a second, simpler method to achieve this. This gives another proof of the polynomial upper bound on the degree of the generators cutting out the null cone of matrix semi-invariants. Both the invariant-Theoretic result and the algorithmic result rely crucially on the regularity lemma proved in [24]. In this paper we improve on the constructive version of the regularity lemma from [24] by removing a technical coprime condition that was assumed there.
Ji, Z 2017, 'Compression of quantum multi-prover interactive proofs', Proceedings of the Annual ACM Symposium on Theory of Computing, 49th Annual ACM SIGACT Symposium on Theory of Computing, AM, Montreal, Canada, pp. 289-302.
View/Download from: Publisher's site
View description>>
© 2017 ACM. We present a protocol that transforms any quantum multi-prover interactive proof into a nonlocal game in which questions consist of logarithmic number of bits and answers of constant number of bits. As a corollary, it follows that the promise problem corresponding to the approximation of the nonlocal value to inverse polynomial accuracy is complete for QMIP∗, and therefore NEXP-hard. This establishes that nonlocal games are provably harder than classical games without any complexity theory assumptions. Our result also indicates that gap amplification for nonlocal games may be impossible in general and provides a negative evidence for the feasibility of the gap amplification approach to the multi-prover variant of the quantum PCP conjecture.
Kong, S, Lee, JH & Li, S 2017, 'A deterministic distributed algorithm for reasoning with connected row-convex constraints', Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, International Conference on Autonomous Agents and Multiagent System, International Foundation for Autonomous Agents and Multiagent Systems, São Paulo, Brazil, pp. 203-211.
View description>>
© Copyright 2017, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All Rights Reserved. The class of CRC constraints generalizes several tractable classes of constraints and is expressive enough to model problems in domains such as temporal reasoning, geometric reasoning, and scene labelling. This paper presents the first distributed deterministic algorithm for connected row-convex (CRC) constraints. Our distributed (partial) path consistency algorithm efficiently transforms a CRC constraint network into an equivalent constraint network, where all constraints are minimal (i.e., they are the tightest constraints) and generating all solutions can be done in a backtrack- free manner. When compared with the state-of-ihe-Art distributed algorithm for CRC constraints, which is a randomized one, our algorithm guarantees to generate a solution for satisfiable CRC constraint networks and it is applicable to solve large networks in real distributed systems. The experimental evaluations show that our algorithm outperforms the statc-of-Thc-Art algorithm in both practice and theory.
Li, S, Long, Z, Liu, W, Duckham, M & Both, A 2017, 'On redundant topological constraints', IJCAI International Joint Conference on Artificial Intelligence, International Joint Conference on Artificial Intelligence, International Joint Conference on Artificial Intelligence Organization, Melbourne, Australia, pp. 5020-5024.
View/Download from: Publisher's site
View description>>
Redundancy checking is an important task in AI subfields such as knowledge representation and constraint solving. This paper considers redundant topological constraints, defined in the region connection calculus RCC8. We say a constraint in a set Γ of RCC8 constraints is redundant if it is entailed by the rest of Γ. A prime subnetwork of Γ is a subset of Γ which contains no redundant constraints and has the same solution set as Γ. It is natural to ask how to compute such a prime subnetwork, and when it is unique. While this problem is in general intractable, we show that, if S is a subalgebra of RCC8 in which weak composition distributes over nonempty intersections, then Γ has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from Γ. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal.
Li, Y & Qiao, Y 2017, 'Linear algebraic analogues of the graph isomorphism problem and the erds-rényi model', Annual Symposium on Foundations of Computer Science - Proceedings, IEEE Annual Symposium on Foundations of Computer Science, IEEE, Berkeley, CA, USA, pp. 463-474.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. A classical difficult isomorphism testing problem is to test isomorphism of p-groups of class 2 and exponent p in time polynomial in the group order. It is known that this problem can be reduced to solving the alternating matrix space isometry problem over a finite field in time polynomial in the underlying vector space size. We propose a venue of attack for the latter problem by viewing it as a linear algebraic analogue of the graph isomorphism problem. This viewpointleads us to explore the possibility of transferring techniques for graph isomorphism to this long-believed bottleneck case of group isomorphism.In 1970s, Babai, Erds, and Selkow presented the first average-case efficient graph isomorphism testing algorithm (SIAM J Computing, 1980). Inspired by that algorithm, we devise an average-case efficient algorithm for the alternating matrix space isometry problem over a key range of parameters, in a random model of alternating matrix spaces in vein of the Erdos-R4;enyi model of random graphs. For this, we develop a linear algebraic analogue of the classical individualisation technique, a technique belonging to a set of combinatorial techniques that has been critical for the progress on the worst-case time complexity for graph isomorphism, but was missing in the group isomorphism context. This algorithm also enables us to improve Higmans 57-year-old lower bound on the number of p-groups (Proc. of the LMS, 1960). We finally show that Luks dynamic programming technique for graph isomorphism (STOC 1999) can be adapted to slightly improve the worst-case time complexity of the alternating matrix space isometry problem in a certain range of parameters.Most notable progress on the worst-case time complexity of graph isomorphism, including Babais recent breakthrough (STOC 2016) and Babai and Luks previous record (STOC 1983), has relied on both group theoretic and combinatorial techniques. By developing a linear algebraic analogue of the individualisation ...
Saqib, M, Daud Khan, S, Sharma, N & Blumenstein, M 2017, 'A study on detecting drones using deep convolutional neural networks', Proceedings of the 2017 14th IEEE International Conference on Advanced Video and Signal Based Surveillance, AVSS 2017, IEEE International Conference on Advanced Video and Signal Based Surveillance, IEEE, Lecce, Italy.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. The object detection is a challenging problem in computer vision with various potential real-world applications. The objective of this study is to evaluate the deep learning based object detection techniques for detecting drones. In this paper, we have conducted experiments with different Convolutional Neural Network (CNN) based network architectures namely Zeiler and Fergus (ZF), Visual Geometry Group (VGG16) etc. Due to sparse data available for training, networks are trained with pre-trained models using transfer learning. The snapshot of trained models is saved at regular interval during training. The best models having high mean Average Precision (mAP) for each network architecture are used for evaluation on the test dataset. The experimental results show that VGG16 with Faster R-CNN perform better than other architectures on the training dataset. Visual analysis of the test dataset is also presented.
Saqib, M, Khan, SD & Blumenstein, M 2016, 'Detecting dominant motion patterns in crowds of pedestrians', Proceedings of SPIE - The International Society for Optical Engineering, International Conference on Graphic and Image Processing, SPIE, Tokyo, Japan.
View/Download from: Publisher's site
View description>>
© 2017 SPIE. As the population of the world increases, urbanization generates crowding situations which poses challenges to public safety and security. Manual analysis of crowded situations is a tedious job and usually prone to errors. In this paper, we propose a novel technique of crowd analysis, the aim of which is to detect different dominant motion patterns in real-time videos. A motion field is generated by computing the dense optical flow. The motion field is then divided into blocks. For each block, we adopt an Intra-clustering algorithm for detecting different flows within the block. Later on, we employ Inter-clustering for clustering the flow vectors among different blocks. We evaluate the performance of our approach on different real-time videos. The experimental results show that our proposed method is capable of detecting distinct motion patterns in crowded videos. Moreover, our algorithm outperforms state-of-the-art methods.
Saqib, M, Khan, SD & Blumenstein, M 2016, 'Texture-based feature mining for crowd density estimation: A study', International Conference Image and Vision Computing New Zealand, International Conference on Image and Vision Computing New Zealand, IEEE, Palmerston North, New Zealand.
View/Download from: Publisher's site
View description>>
© 2016 IEEE. Texture feature is an important feature descriptor for many image analysis applications. The objectives of this research are to determine distinctive texture features for crowd density estimation and counting. In this paper, we have comprehensively reviewed different texture features and their different possible combinations to evaluate their performance on pedestrian crowds. A two-stage classification and regression based framework have been proposed for performance evaluation of all the texture features for crowd density estimation and counting. According to the framework, input images are divided into blocks and blocks into cells of different sizes, having varying crowd density levels. Due to perspective distortion, people appearing close to the camera contribute more to the feature vector than people far away. Therefore, features extracted are normalized using a perspective normalization map of the scene. At the first stage, image blocks are classified using multi-class SVM into different density level. At the second stage Gaussian Process Regression is used to re gress low-level features to count. Various texture features and their possible combinations are evaluated on publicly available dataset.
Su, G, Chen, T, Feng, Y & Rosenblum, DS 2017, 'ProEva: Runtime proactive performance evaluation based on continuous-time markov chains', Proceedings - 2017 IEEE/ACM 39th International Conference on Software Engineering, ICSE 2017, International Conference on Software Engineering, IEEE, Buenos Aires, Argentina, pp. 484-495.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. Software systems, especially service-based software systems, need to guarantee runtime performance. If their performance is degraded, some reconfiguration countermeasures should be taken. However, there is usually some latency before the countermeasures take effect. It is thus important not only to monitor the current system status passively but also to predict its future performance proactively. Continuous-Time Markov chains (CTMCs) are suitable models to analyze time-bounded performance metrics (e.g., how likely a performance degradation may occur within some future period). One challenge to harness CTMCs is the measurement of model parameters (i.e., transition rates) in CTMCs at runtime. As these parameters may be updated by the system or environment frequently, it is difficult for the model builder to provide precise parameter values. In this paper, we present a framework called ProEva, which extends the conventional technique of time-bounded CTMC model checking by admitting imprecise, interval-valued estimates for transition rates. The core method of ProEva computes asymptotic expressions and bounds for the imprecise model checking output. We also present an evaluation of accuracy and computational overhead for ProEva.
Sutter, D, Berta, M & Tomamichel, M 2017, 'Quantum Markov chains and logarithmic trace inequalities', IEEE International Symposium on Information Theory - Proceedings, IEEE International Symposium on Information Theory, IEEE, Aachen, Germany, pp. 1988-1992.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. A Markov chain is a tripartite quantum state ρABCwhere there exists a recovery map RB→BCsuch that ρABC= RB→BC(ρAB). More generally, an approximate Markov chain ρABCis a state whose distance to the closest recovered state RB→BC(ρAB) is small. Recently it has been shown that this distance can be bounded from above by the conditional mutual information I(A: C|B)ρof the state. We improve on this connection by deriving the first bound that is tight in the commutative case and features an explicit recovery map that only depends on the reduced state pBC. The key tool in our proof is a multivariate extension of the Golden-Thompson inequality, which allows us to extend logarithmic trace inequalities from two to arbitrarily many matrices.
Suwanwiwat, H, Das, A, Ferrer, MA, Pal, U & Blumenstein, M 2017, 'An Automatic Student Verification System Utilising Off-line Thai Name Components', 2017 International Conference on Digital Image Computing - Techniques and Applications, International Conference on Digital Image Computing - Techniques and Applications, IEEE, Sydney, Australia, pp. 826-831.
View/Download from: Publisher's site
View description>>
This research proposed an automatic student identification and verification system utilising off-line Thai name components. The Thai name components consist of first and last names. Dense texture-based feature descriptors were able to yield encouraging results when applied to different handwritten text recognition scenarios. As a result, the authors employed such features in investigating their performance on Thai name component verification system. In this research, Dense-Local Binary Pattern, Dense-Local Directional Pattern, and Local Binary Pattern combined with Local Directional Pattern were employed. A base-line shape/feature i.e. Hidden Markov Model (HMM) was also utilised in this study. As there is no dataset on Thai name verification in the literature, a dataset is proposed for a Thai name verification system. The name component samples were collected from high school students. It consists of 8,400 name components (first and last names) from 100 students. Each student provided 60 genuine name components, and each of the name components was forged by 12 other students. An encouraging result was found employing the above-mentioned features on the proposed dataset.
Suwanwiwat, H, Pal, U & Blumenstein, M 2016, 'An investigation of novel combined features for a handwritten short answer assessment system', Proceedings of International Conference on Frontiers in Handwriting Recognition, ICFHR, International Conference on Frontiers in Handwriting Recognition, IEEE, pp. 102-107.
View/Download from: Publisher's site
View description>>
© 2016 IEEE. This paper proposes an off-line automatic assessment system utilising novel combined feature extraction techniques. The proposed feature extraction techniques are 1) the proposed Water Reservoir, Loop, Modified Direction and Gaussian Grid Feature (WRL-MDGGF), 2) the proposed Gravity, Water Reservoir, Loop, Modified Direction and Gaussian Grid Feature (G-WRL-MDGGF). The proposed feature extraction techniques together with their original features and other combined feature extraction techniques were employed in an investigation of the efficiency of feature extraction techniques on an automatic off-line short answer assessment system. The proposed system utilised two classifiers namely, artificial neural networks and Support Vector Machines (SVMs), two type of datasets and two different thresholds in this investigation. Promising recognition rates of 94.85% and 94.88% were obtained when the proposed WRL-MDGGF and G-WRL-MDGGF were employed, respectively, using SVMs.
Tomamichel, M, Chubb, CT & Tan, V 2018, 'Moderate deviation analysis for classical communication over quantum channels', IEEE International Symposium on Information Theory - Proceedings, Vail, CO, USA, pp. 1544-1548.
View/Download from: Publisher's site
Wang, B, Gao, Y, Sun, C, Blumenstein, M & La Salle, J 2017, 'Can Walking and Measuring along Chord Bunches Better Describe Leaf Shapes?', Proceedings - 30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, 2017 IEEE Conference on Computer Vision and Pattern Recognition, Honolulu, HI, USA, pp. 2047-2056.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. Effectively describing and recognizing leaf shapes under arbitrary deformations, particularly from a large database, remains an unsolved problem. In this research, we attempted a new strategy of describing shape by walking along a bunch of chords that pass through the shape to measure the regions trespassed. A novel chord bunch walks (CBW) descriptor is developed through the chord walking that effectively integrates the shape image function over the walked chord to reflect the contour features and the inner properties of the shape. For each contour point, the chord bunch groups multiple pairs of chord walks to build a hierarchical framework for a coarse-to-fine description. The proposed CBW descriptor is invariant to rotation, scaling, translation, and mirror transforms. Instead of using the expensive optimal correspondence based matching, an improved Hausdorff distance encoded correspondence information is proposed for efficient yet effective shape matching. In experimental studies, the proposed method obtained substantially higher accuracies with low computational cost over the benchmarks, which indicates the research potential along this direction.
Wang, X, Xie, W & Duan, R 2017, 'Semidefinite programming converse bounds for classical communication over quantum channels', IEEE International Symposium on Information Theory - Proceedings, IEEE International Symposium on Information Theory, IEEE, Aachen, Germany, pp. 1728-1732.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. We study the classical communication over quantum channels when assisted by no-signalling (NS) and PPT-preserving (PPT) codes. We first show that both the optimal success probability of a given transmission rate and one-shot-error capacity can be formalized as semidefinite programs (SDPs) when assisted by NS or NS∩PPT codes. Based on this, we derive SDP finite blocklength converse bounds for general quantum channels, which also reduce to the converse bound of Polyanskiy, Poor, and Verdii for classical channels. Furthermore, we derive an SDP strong converse bound for the classical capacity of a general quantum channel: for any code with a rate exceeding this bound, the optimal success probability vanishes exponentially fast as the number of channel uses increases. In particular, applying our efficiently computable bound, we derive improved upper bounds to the classical capacity of the amplitude damping channels and also establish the strong converse property for a new class of quantum channels.
Wilde, MM, Tomamichel, M & Berta, M 2017, 'A meta-converse for private communication over quantum channels', IEEE International Symposium on Information Theory - Proceedings, IEEE International Symposium on Information Theory, IEEE, Aachen, Germany, pp. 291-295.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. We establish a converse bounds on the private transmission capabilities of a quantum channel. The main conceptual development builds firmly on the notion of a private state, which is a powerful, uniquely quantum method for simplifying the tripartite picture of privacy involving local operations and public classical communication to a bipartite picture of quantum privacy involving local operations and classical communication. This approach has previously led to some of the strongest upper bounds on secret key rates, including the squashed entanglement and the relative entropy of entanglement. Here we use this approach along with a "privacy test" to establish a general meta-converse bound for private communication.
Wu, D, Sharma, N & Blumenstein, M 2017, 'Recent Advances in Video Based Human Action Recognition Using Deep Learning: A Review', Proceedings of the 2017 International Joint Conference on Neural Networks (IJCNN), International Joint Conference on Neural Networks, IEEE, Anchorage, Alaska, USA, pp. 2865-2872.
View/Download from: Publisher's site
View description>>
In this work, we consider the problem of robust principal component analysis (RPCA) for streaming noisy data that has been highly compressed. This problem is prominent when one deals with high-dimensional and large-scale data and data compression is necessary. To solve this problem, we propose an online compressed RPCA algorithm to efficiently recover the low-rank components of raw data. Though data compression incurs severe information loss, we provide deep analysis on the proposed algorithm and prove that the low-rank component can be asymptotically recovered under mild conditions. Compared with other recent works on compressed RPCA, our algorithm reduces the memory cost significantly by processing data in an online fashion and reduces the communication cost by accepting sequential compressed data as input.
Ying, M, Ying, S & Wu, X 2917, 'Invariants of quantum programs: Characterisations and generation', Conference Record of the Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Symposium on Principles of Programming Languages, ACM, Paris, France, pp. 818-832.
View/Download from: Publisher's site
View description>>
© 2017 ACM. Program invariant is a fundamental notion widely used in program verification and analysis. The aim of this paper is twofold: (i) find an appropriate definition of invariants for quantum programs; and (ii) develop an effective technique of invariant generation for ver- ification and analysis of quantum programs. Interestingly, the no- tion of invariant can be defined for quantum programs in two d- ifferent ways - additive invariants and multiplicative invariants - corresponding to two interpretations of implication in a continuous valued logic: the £ukasiewicz implication and the Godel implica- tion. It is shown that both of them can be used to establish partial correctness of quantum programs. The problem of generating ad- ditive invariants of quantum programs is addressed by reducing it to an SDP (Semidefinite Programming) problem. This approach is applied with an SDP solver to generate invariants of two important quantum algorithms - quantum walk and quantum Metropolis sam- pling. Our examples show that the generated invariants can be used to verify correctness of these algorithms and are helpful in optimis- ing quantum Metropolis sampling. To our knowledge, this paper is the first attempt to define the notion of invariant and to develop a method of invariant generation for quantum programs.
Zhou, L & Ying, M 2017, 'Differential Privacy in Quantum Computation', Proceedings - IEEE Computer Security Foundations Symposium, IEEE Computer Security Foundations Symposium, IEEE, Santa Barbara, CA, USA, pp. 249-262.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. More and more quantum algorithms have been designed for solving problems in machine learning, database search and data analytics. An important problem then arises: how privacy can be protected when these algorithms are used on private data? For classical computing, the notion of differential privacy provides a very useful conceptual framework in which a great number of mechanisms that protect privacy by introducing certain noises into algorithms have been successfully developed. This paper defines a notion of differential privacy for quantum information processing. We carefully examine how the mechanisms using three important types of quantum noise, the amplitude/phase damping and depolarizing, can protect differential privacy. A composition theorem is proved that enables us to combine multiple privacy-preserving operations in quantum information processing.