Asaad, S, Dickel, C, Langford, NK, Poletto, S, Bruno, A, Rol, MA, Deurloo, D & DiCarlo, L 2016, 'Independent, extensible control of same-frequency superconducting qubits by selective broadcasting', npj Quantum Information, vol. 2, no. 1, pp. 1-6.
View/Download from: Publisher's site
View description>>
AbstractA critical ingredient for realising large-scale quantum information processors will be the ability to make economical use of qubit control hardware. We demonstrate an extensible strategy for reusing control hardware on same-frequency transmon qubits in a circuit QED chip with surface-code-compatible connectivity. A vector switch matrix enables selective broadcasting of input pulses to multiple transmons with individual tailoring of pulse quadratures for each, as required to minimise the effects of leakage on weakly anharmonic qubits. Using randomised benchmarking, we compare multiple broadcasting strategies that each pass the surface-code error threshold for single-qubit gates. In particular, we introduce a selective broadcasting control strategy using five pulse primitives, which allows independent, simultaneous Clifford gates on arbitrary numbers of qubits.
Asaad, S, Dickel, C, Langford, NK, Poletto, S, Bruno, A, Rol, MA, Deurloo, D & Dicarlo, L 2016, 'Independent, extensible control of same-frequency superconducting qubits by selective broadcasting(npj Quantum Information (2017) 3, 17001, 10.1038/npjqi.2017.1)', npj Quantum Information, vol. 2, no. 1.
View/Download from: Publisher's site
View description>>
The original version of this Article contained an error in one of the calculations within the Results section. Although the authors note that this leakage rate is per Clifford, they actually quote the value per nanosecond: 'We extract per Clifford leakage rates ? of 4.1(2) × 10-6 (QT)and 1.3(4) × 10-6 (QB) by fitting the following simple model to the data'. Now reads: 'We extract per Clifford leakage rates k of 1.4(2) × 10-4 (QT) and 3.9(4) × 10-5 (QB) by fitting the following simple model to the data'. This error has now been corrected in the PDF and HTML versions of the Article.
Berta, M, Scholz, VB & Tomamichel, M 2016, 'Rényi divergences as weighted non-commutative vector valued $L_p$-spaces', e, vol. 19, no. 6, pp. 1843-1867.
View/Download from: Publisher's site
View description>>
We show that Araki and Masuda's weighted non-commutative vector valued$L_p$-spaces [Araki \& Masuda, Publ. Res. Inst. Math. Sci., 18:339 (1982)]correspond to an algebraic generalization of the sandwiched R\'enyi divergenceswith parameter $\alpha = \frac{p}{2}$. Using complex interpolation theory, weprove various fundamental properties of these divergences in the setup of vonNeumann algebras, including a data-processing inequality and monotonicity in$\alpha$. We thereby also give new proofs for the correspondingfinite-dimensional properties. We discuss the limiting cases $\alpha\to\{\frac{1}{2},1,\infty\}$ leading to minus the logarithm of Uhlmann's fidelity,Umegaki's relative entropy, and the max-relative entropy, respectively. As acontribution that might be of independent interest, we derive a Riesz-Thorintheorem for Araki-Masuda $L_p$-spaces and an Araki-Lieb-Thirring inequality forstates on von Neumann algebras.
Boixo, S, Isakov, SV, Smelyanskiy, VN, Babbush, R, Ding, N, Jiang, Z, Bremner, MJ, Martinis, JM & Neven, H 2016, 'Characterizing Quantum Supremacy in Near-Term Devices', Nature Physics, vol. 14, no. 6, pp. 595-600.
View/Download from: Publisher's site
View description>>
A critical question for the field of quantum computing in the near future iswhether quantum devices without error correction can perform a well-definedcomputational task beyond the capabilities of state-of-the-art classicalcomputers, achieving so-called quantum supremacy. We study the task of samplingfrom the output distributions of (pseudo-)random quantum circuits, a naturaltask for benchmarking quantum computers. Crucially, sampling this distributionclassically requires a direct numerical simulation of the circuit, withcomputational cost exponential in the number of qubits. This requirement istypical of chaotic systems. We extend previous results in computationalcomplexity to argue more formally that this sampling task must take exponentialtime in a classical computer. We study the convergence to the chaotic regimeusing extensive supercomputer simulations, modeling circuits with up to 42qubits - the largest quantum circuits simulated to date for a computationaltask that approaches quantum supremacy. We argue that while chaotic states areextremely sensitive to errors, quantum supremacy can be achieved in thenear-term with approximately fifty superconducting qubits. We introduce crossentropy as a useful benchmark of quantum circuits which approximates thecircuit fidelity. We show that the cross entropy can be efficiently measuredwhen circuit simulations are available. Beyond the classically tractableregime, the cross entropy can be extrapolated and compared with theoreticalestimates of circuit fidelity to define a practical quantum supremacy test.
Bremner, MJ, Montanaro, A & Shepherd, DJ 2016, '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 quantumpolynomial-time) has been shown to be hard to simulate classically, assumingcertain complexity-theoretic conjectures. Here we study the power of IQPcircuits in the presence of physically motivated constraints. First, we showthat there is a family of sparse IQP circuits that can be implemented on asquare lattice of n qubits in depth O(sqrt(n) log n), and which is likely hardto simulate classically. Next, we show that, if an arbitrarily small constantamount of noise is applied to each qubit at the end of any IQP circuit whoseoutput probability distribution is sufficiently anticoncentrated, there is apolynomial-time classical algorithm that simulates sampling from the resultingdistribution, up to constant accuracy in total variation distance. However, weshow that purely classical error-correction techniques can be used to designIQP circuits which remain hard to simulate classically, even in the presence ofarbitrary amounts of noise of this form. These results demonstrate thechallenges faced by experiments designed to demonstrate quantum supremacy overclassical computation, and how these challenges can be overcome.
Bremner, MJ, Montanaro, A & Shepherd, DJ 2016, 'Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations', PHYSICAL REVIEW LETTERS, vol. 117, no. 8.
View/Download from: Publisher's site
View description>>
© 2016 American Physical Society. We use the class of commuting quantum computations known as IQP (instantaneous quantum polynomial time) to strengthen the conjecture that quantum computers are hard to simulate classically. We show that, if either of two plausible average-case hardness conjectures holds, then IQP computations are hard to simulate classically up to constant additive error. One conjecture relates to the hardness of estimating the complex-temperature partition function for random instances of the Ising model; the other concerns approximating the number of zeroes of random low-degree polynomials. We observe that both conjectures can be shown to be valid in the setting of worst-case complexity. We arrive at these conjectures by deriving spin-based generalizations of the boson sampling problem that avoid the so-called permanent anticoncentration conjecture. 2016 UK.
Chapman, RJ, Ferrie, C & Peruzzo, A 2016, 'Experimental Demonstration of Self-Guided Quantum Tomography', Physical Review Letters, vol. 117, no. 4.
View/Download from: Publisher's site
Chen, J, Guo, C, Ji, Z, Poon, Y-T, Yu, N, Zeng, B & Zhou, J 2016, 'Joint product numerical range and geometry of reduced density matrices', Sci. China Phys. Mech. Astron., vol. 60, no. 2, p. 020312.
View/Download from: Publisher's site
View description>>
The reduced density matrices of a many-body quantum system form a convex set,whose three-dimensional projection $\Theta$ is convex in $\mathbb{R}^3$. Theboundary $\partial\Theta$ of $\Theta$ may exhibit nontrivial geometry, inparticular ruled surfaces. Two physical mechanisms are known for the origins ofruled surfaces: symmetry breaking and gapless. In this work, we study theemergence of ruled surfaces for systems with local Hamiltonians in infinitespatial dimension, where the reduced density matrices are known to be separableas a consequence of the quantum de Finetti's theorem. This allows us toidentify the reduced density matrix geometry with joint product numerical range$\Pi$ of the Hamiltonian interaction terms. We focus on the case where theinteraction terms have certain structures, such that ruled surface emergenaturally when taking a convex hull of $\Pi$. We show that, a ruled surface on$\partial\Theta$ sitting in $\Pi$ has a gapless origin, otherwise it has asymmetry breaking origin. As an example, we demonstrate that a famous ruledsurface, known as the oloid, is a possible shape of $\Theta$, with two boundarypieces of symmetry breaking origin separated by two gapless lines.
Chen, J-Y, Ji, Z, Liu, Z-X, Qi, X, Yu, N, Zeng, B & Zhou, D 2016, 'Physical origins of ruled surfaces on the reduced density matrices geometry', Sci. China Phys. Mech. Astron. (2017) 60: 020311, vol. 60, no. 2.
View/Download from: Publisher's site
View description>>
The reduced density matrices (RDMs) of many-body quantum states form a convexset. The boundary of low dimensional projections of this convex set may exhibitnontrivial geometry such as ruled surfaces. In this paper, we study thephysical origins of these ruled surfaces for bosonic systems. The emergence ofruled surfaces was recently proposed as signatures of symmetry-breaking phase.We show that, apart from being signatures of symmetry-breaking, ruled surfacescan also be the consequence of gapless quantum systems by demonstrating anexplicit example in terms of a two-mode Ising model. Our analysis was largelysimplified by the quantum de Finetti's theorem---in the limit of large systemsize, these RDMs are the convex set of all the symmetric separable states. Todistinguish ruled surfaces originated from gapless systems from those caused bysymmetry-breaking, we propose to use the finite size scaling method for thecorresponding geometry. This method is then applied to the two-mode XY model,successfully identifying a ruled surface as the consequence of gapless systems.
Chen, J-Y, Ji, Z, Yu, N & Zeng, B 2016, 'Dichotomy of entanglement depth for symmetric states', Phys. Rev. A, vol. 94, no. 4, p. 042333.
View/Download from: Publisher's site
View description>>
Entanglement depth characterizes the minimal number of particles in a systemthat are mutually entangled. For symmetric states, we show that there is adichotomy for entanglement depth: an $N$-particle symmetric state is eitherfully separable, or fully entangled---the entanglement depth is either $1$ or$N$. This property is even stable under non-symmetric noise. We propose anexperimentally accessible method to detect entanglement depth in atomicensembles based on a bound on the particle number population of Dicke states,and demonstrate that the entanglement depth of some Dicke states, for examplethe twin Fock state, is very stable even under a large arbitrary noise. Ourobservation can be applied to atomic Bose-Einstein condensates to infer thatthese systems can be highly entangled with the entanglement depth that is ofthe order of the system size (i.e. several thousands of atoms).
Cheng, HC, Hsieh, MH & Yeh, PC 2016, 'The learnability of unknown quantum measurements', Quantum Information and Computation, vol. 16, no. 7-8, pp. 615-656.
View description>>
In this work, we provide an elegant framework to analyze learning matrices in the Schatten class by taking advantage of a recently developed methodology—matrix concentration inequalities. We establish the fat-shattering dimension, Rademacher/Gaussian complexity, and the entropy number of learning bounded operators and trace class operators. By characterising the tasks of learning quantum states and two-outcome quantum measurements into learning matrices in the Schatten-1 and ∞ classes, our proposed approach directly solves the sample complexity problems of learning quantum states and quantum measurements. Our main result in the paper is that, for learning an unknown quantum measurement, the upper bound, given by the fat-shattering dimension, is linearly proportional to the dimension of the underlying Hilbert space. Learning an unknown quantum state becomes a dual problem to ours, and as a byproduct, we can recover Aaronson’s famous result [Proc. R. Soc. A 463, 3089–3144 (2007)] solely using a classical machine learning technique. In addition, other famous complexity measures like covering numbers and Rademacher/Gaussian complexities are derived explicitly under the same framework. We are able to connect measures of sample complexity with various areas in quantum information science, e.g. quantum state/measurement tomography, quantum state discrimination and quantum random access codes, which may be of independent interest. Lastly, with the assistance of general Bloch-sphere representation, we show that learning quantum measurements/states can be mathematically formulated as a neural network. Consequently, classical ML algorithms can be applied to efficiently accomplish the two quantum learning tasks.
Devitt, SJ 2016, 'Performing Quantum Computing Experiments in the Cloud', Phys. Rev. A, vol. 94, no. 3, p. 032329.
View/Download from: Publisher's site
View description>>
Quantum computing technology has reached a second renaissance in the pastfive years. Increased interest from both the private and public sector combinedwith extraordinary theoretical and experimental progress has solidified thistechnology as a major advancement in the 21st century. As anticipated by many,the first realisation of quantum computing technology would occur over thecloud, with users logging onto dedicated hardware over the classical internet.Recently IBM has released the {\em Quantum Experience} which allows users toaccess a five qubit quantum processor. In this paper we take advantage of thisonline availability of actual quantum hardware and present four quantuminformation experiments that have never been demonstrated before. We utilisethe IBM chip to realise protocols in Quantum Error Correction, QuantumArithmetic, Quantum graph theory and Fault-tolerant quantum computation, byaccessing the device remotely through the cloud. While the results are subjectto significant noise, the correct results are returned from the chip. Thisdemonstrates the power of experimental groups opening up their technology to awider audience and will hopefully allow for the next stage development inquantum information technology.
Devitt, SJ 2016, 'Programming quantum computers using 3-D puzzles, coffee cups, and doughnuts', XRDS, vol. 23, no. 1, pp. 45-50.
View/Download from: Publisher's site
View description>>
The task of programming a quantum computer is just as strange as quantummechanics itself. But it now looks like a simple 3D puzzle may be the futuretool of quantum software engineers.
Guan, J, Feng, Y & Ying, M 2016, 'Decomposition of Quantum Markov Chains and Its Applications', Journal of Computer and System Sciences, vol. 95, pp. 55-68.
View/Download from: Publisher's site
View description>>
Markov chains have been widely employed as a fundamental model in the studiesof probabilistic and stochastic communicating and concurrent systems. It iswell-understood that decomposition techniques play a key role in reachabilityanalysis and model-checking of Markov chains. (Discrete-time) quantum Markovchains have been introduced as a model of quantum communicating systems [1] andalso a semantic model of quantum programs [2]. The BSCC (Bottom StronglyConnected Component) and stationary coherence decompositions of quantum Markovchains were introduced in [3, 4, 5]. This paper presents a new decompositiontechnique, namely periodic decomposition, for quantum Markov chains. We furtherestablish a limit theorem for them. As an application, an algorithm to find amaximum dimensional noiseless subsystem of a quantum communicating system isgiven using decomposition techniques of quantum Markov chains.
Hiai, F, Koenig, R & Tomamichel, M 2016, 'Generalized Log-Majorization and Multivariate Trace Inequalities', Annales Henri Poincare, vol. 18, no. 7, pp. 7-2521.
View/Download from: Publisher's site
View description>>
We show that recent multivariate generalizations of the Araki-Lieb-Thirringinequality and the Golden-Thompson inequality [Sutter, Berta, and Tomamichel,Comm. Math. Phys. (2016)] for Schatten norms hold more generally for allunitarily invariant norms and certain variations thereof. The main technicalcontribution is a generalization of the concept of log-majorization whichallows us to treat majorization with regards to logarithmic integral averagesof vectors of singular values.
Jerger, M, Reshitnyk, Y, Oppliger, M, Potočnik, A, Mondal, M, Wallraff, A, Goodenough, K, Wehner, S, Juliusson, K, Langford, NK & Fedorov, A 2016, 'Contextuality without nonlocality in a superconducting quantum system', Nature Communications, vol. 7, no. 1, p. 12930.
View/Download from: Publisher's site
View description>>
AbstractClassical realism demands that system properties exist independently of whether they are measured, while noncontextuality demands that the results of measurements do not depend on what other measurements are performed in conjunction with them. The Bell–Kochen–Specker theorem states that noncontextual realism cannot reproduce the measurement statistics of a single three-level quantum system (qutrit). Noncontextual realistic models may thus be tested using a single qutrit without relying on the notion of quantum entanglement in contrast to Bell inequality tests. It is challenging to refute such models experimentally, since imperfections may introduce loopholes that enable a realist interpretation. Here we use a superconducting qutrit with deterministic, binary-outcome readouts to violate a noncontextuality inequality while addressing the detection, individual-existence and compatibility loopholes. This evidence of state-dependent contextuality also demonstrates the fitness of superconducting quantum circuits for fault-tolerant quantum computation in surface-code architectures, currently the most promising route to scalable quantum computing.
Knee, GC, Combes, J, Ferrie, C & Gauger, EM 2016, 'Weak-value amplification: state of play', Quantum Measurements and Quantum Metrology, vol. 3, no. 1, pp. 32-37.
View/Download from: Publisher's site
View description>>
AbstractWeak values arise in quantum theory when the result of a weak measurement is conditioned on a subsequent strong measurement. The majority of the trials are discarded, leaving only very few successful events. Intriguingly those can display a substantial signal amplification. This raises the question of whether weak values carry potential to improve the performance of quantum sensors, and indeed a number of impressive experimental results suggested this may be the case. By contrast, recent theoretical studies have found the opposite: using weak-values to obtain an amplification generally worsens metrological performance. This survey summarises the implications of those studies, which call for a reappraisal of weak values’ utility and for further work to reconcile theory and experiment.
Lancia, G, Mathieson, L & Moscato, P 2016, 'Separating Sets of Strings by Finding Matching Patterns is Almost Always Hard', Theoretical Computer Science, vol. 665, pp. 73-86.
View/Download from: Publisher's site
View description>>
We study the complexity of the problem of searching for a set of patternsthat separate two given sets of strings. This problem has applications in awide variety of areas, most notably in data mining, computational biology, andin understanding the complexity of genetic algorithms. We show that the basicproblem of finding a small set of patterns that match one set of strings but donot match any string in a second set is difficult (NP-complete, W[2]-hard whenparameterized by the size of the pattern set, and APX-hard). We then perform adetailed parameterized analysis of the problem, separating tractable andintractable variants. In particular we show that parameterizing by the size ofpattern set and the number of strings, and the size of the alphabet and thenumber of strings give FPT results, amongst others.
Lee, T, Leonardos, N, Saks, M & Wang, F 2016, 'Hellinger volume and number-on-the-forehead communication complexity', Journal of Computer and System Sciences, vol. 82, no. 6, pp. 1064-1074.
View/Download from: Publisher's site
Li, Y, Qiao, Y, Wang, X & Duan, R 2016, 'Tripartite-to-bipartite Entanglement Transformation by Stochastic Local Operations and Classical Communication and the Structure of Matrix Spaces', Communications in Mathematical Physics, vol. 358, no. 2, pp. 791-814.
View/Download from: Publisher's site
View description>>
We study the problem of transforming a tripartite pure state to a bipartiteone using stochastic local operations and classical communication (SLOCC). Itis known that the tripartite-to-bipartite SLOCC convertibility is characterizedby the maximal Schmidt rank of the given tripartite state, i.e. the largestSchmidt rank over those bipartite states lying in the support of the reduceddensity operator. In this paper, we further study this problem and exhibitnovel results in both multi-copy and asymptotic settings. In the multi-copyregime, we observe that the maximal Schmidt rank is strictlysuper-multiplicative, i.e. the maximal Schmidt rank of the tensor product oftwo tripartite pure states can be strictly larger than the product of theirmaximal Schmidt ranks. We then provide a full characterization of thosetripartite states whose maximal Schmidt rank is strictly super-multiplicativewhen taking tensor product with itself. In the asymptotic setting, we focus ondetermining the tripartite-to-bipartite SLOCC entanglement transformation rate,which turns out to be equivalent to computing the asymptotic maximal Schmidtrank of the tripartite state, defined as the regularization of its maximalSchmidt rank. Despite the difficulty caused by the super-multiplicativeproperty, we provide explicit formulas for evaluating the asymptotic maximalSchmidt ranks of two important families of tripartite pure states, by resortingto certain results of the structure of matrix spaces, including the study ofmatrix semi-invariants. These formulas give a sufficient and necessarycondition to determine whether a given tripartite pure state can be transformedto the bipartite maximally entangled state under SLOCC, in the asymptoticsetting. Applying the recent progress on the non-commutative rank problem, wecan verify this condition in deterministic polynomial time.
Long, Z, Duckham, M, Li, S & Schockaert, S 2016, 'Indexing large geographic datasets with compact qualitative representation', International Journal of Geographical Information Science, vol. 30, no. 6, pp. 1072-1094.
View/Download from: Publisher's site
View description>>
© 2015 Taylor & Francis. This paper develops a new mechanism to efficiently compute and compactly store qualitative spatial relations between spatial objects, focusing on topological and directional relations for large datasets of region objects. The central idea is to use minimum bounding rectangles (MBRs) to approximately represent region objects with arbitrary shape and complexity and only store spatial relations that cannot be unambiguously inferred from the relations of corresponding MBRs. We demonstrate, both in theory and practice, that our approach requires considerably less construction time and storage space, and can answer queries more efficiently than the state-of-the-art methods.
Luccio, F, Mans, B, Mathieson, L & Pagli, L 2016, 'Complete Balancing via Rotation', The Computer Journal, vol. 59, no. 8, pp. 1252-1263.
View/Download from: Publisher's site
Ma, X, Jackson, T, Zhou, H, Chen, J, Lu, D, Mazurek, MD, Fisher, KAG, Peng, X, Kribs, D, Resch, KJ, Ji, Z, Zeng, B & Laflamme, R 2016, 'Pure State Tomography with Pauli Measurements', Phys. Rev. A, vol. 93, no. 3, p. 032140.
View/Download from: Publisher's site
View description>>
We examine the problem of finding the minimum number of Pauli measurementsneeded to uniquely determine an arbitrary $n$-qubit pure state among allquantum states. We show that only $11$ Pauli measurements are needed todetermine an arbitrary two-qubit pure state compared to the full quantum statetomography with $16$ measurements, and only $31$ Pauli measurements are neededto determine an arbitrary three-qubit pure state compared to the full quantumstate tomography with $64$ measurements. We demonstrate that our protocol isrobust under depolarizing error with simulated random pure states. Weexperimentally test the protocol on two- and three-qubit systems with nuclearmagnetic resonance techniques. We show that the pure state tomography protocolsaves us a number of measurements without considerable loss of fidelity. Wecompare our protocol with same-size sets of randomly selected Pauli operatorsand find that our selected set of Pauli measurements significantly outperformsthose random sampling sets. As a direct application, our scheme can also beused to reduce the number of settings needed for pure-state tomography inquantum optical systems.
Mathieson, L 2016, 'Synergies in critical reflective practice and science: Science as reflection and reflection as science', Journal of University Teaching and Learning Practice, vol. 13, no. 2, pp. 1-13.
View description>>
The conceptions of reflective practice in education have their roots at least partly in the work of Dewey, who describes reflection as “the active, persistent, and careful consideration of any belief or supposed form of knowledge in the light of the grounds that support it and the further conclusions to which it tends” (Dewey 1933, p.9). This conception of reflection has carried on into more-focused efforts to describe critical reflection as a tool for improving professional practice (where academic and educational practice is the particular interest of this study); “… some puzzling or troubling or interesting phenomenon” allows the practitioner to access “the understandings which have been implicit in his action, understandings which he surfaces, criticizes, restructures, and embodies in further action” (Schön 1983, p. 50). Both of these descriptions embody a central idea of critical reflective practice: that the examination of practice involves the divination (in a rational, critical sense) of order and perhaps meaning from the facts at hand (which, in turn, are brought to light by the events that occur as the results of implementation of theory). As part of a lecture series, Gottlieb defined science as “an intellectual activity carried out by humans to understand the structure and functions of the world in which they live” (Gottlieb 1997). While science and critical reflective practice attempt to build models about different parts of our world – the natural world and the world of professional (educational) practice respectively – both embody certain underlying aims and methodologies. Indeed, it is striking that in these definitions the simple replacement of the terminology of reflective practice with the terminology of science (or vice versa) leads to a perfectly comprehensible definition of either.It is this confluence that this paper studies, building from two separate foundations, critical reflective practice and science. Via their models and exem...
Meter, RV & Devitt, SJ 2016, 'Local and Distributed Quantum Computation', IEEE Computer 49(9), 31-42, Sept. 2016, vol. 49, no. 9, pp. 31-42.
View/Download from: Publisher's site
View description>>
Experimental groups are now fabricating quantum processors powerful enough toexecute small instances of quantum algorithms and definitively demonstratequantum error correction that extends the lifetime of quantum data, addingurgency to architectural investigations. Although other options continue to beexplored, effort is coalescing around topological coding models as the mostpractical implementation option for error correction on realizablemicroarchitectures. Scalability concerns have also motivated architects topropose distributed memory multicomputer architectures, with experimentalefforts demonstrating some of the basic building blocks to make such designspossible. We compile the latest results from a variety of different systemsaiming at the construction of a scalable quantum computer.
Motes, KR, Mann, RL, Olson, JP, Studer, NM, Bergeron, EA, Gilchrist, A, Dowling, JP, Berry, DW & Rohde, PP 2016, 'Efficient recycling strategies for preparing large Fock states from single-photon sources --- Applications to quantum metrology', Phys. Rev. A, vol. 94, no. 1, p. 012344.
View/Download from: Publisher's site
View description>>
Fock states are a fundamental resource for many quantum technologies such asquantum metrology. While much progress has been made in single-photon sourcetechnologies, preparing Fock states with large photon number remainschallenging. We present and analyze a bootstrapped approach fornon-deterministically preparing large photon-number Fock states by iterativelyfusing smaller Fock states on a beamsplitter. We show that by employing staterecycling we are able to exponentially improve the preparation rate overconventional schemes, allowing the efficient preparation of large Fock states.The scheme requires single-photon sources, beamsplitters, number-resolvedphoto-detectors, fast-feedforward, and an optical quantum memory.
Nagayama, S, Choi, B-S, Devitt, S, Suzuki, S & Van Meter, R 2016, 'Interoperability in encoded quantum repeater networks', Physical Review A, vol. 93, no. 4.
View/Download from: Publisher's site
View description>>
The future of quantum repeater networking will require interoperability between various error-correcting codes. A few specific code conversions and even a generalized method are known, however, no detailed analysis of these techniques in the context of quantum networking has been performed. In this paper we analyze a generalized procedure to create Bell pairs encoded heterogeneously between two separate codes used often in error-corrected quantum repeater network designs. We begin with a physical Bell pair and then encode each qubit in a different error-correcting code, using entanglement purification to increase the fidelity. We investigate three separate protocols for preparing the purified encoded Bell pair. We calculate the error probability of those schemes between the Steane [[7,1,3]] code, a distance-3 surface code, and single physical qubits by Monte Carlo simulation under a standard Pauli error model and estimate the resource efficiency of the procedures. A local gate error rate of 10-3 allows us to create high-fidelity logical Bell pairs between any of our chosen codes. We find that a postselected model, where any detected parity flips in code stabilizers result in a restart of the protocol, performs the best.
Nagayama, S, Fowler, AG, Horsman, D, Devitt, SJ & Meter, RV 2016, 'Surface Code Error Correction on a Defective Lattice', New Journal of Physics, 19(2):023050, 2017, vol. 19, no. 2, pp. 1-29.
View/Download from: Publisher's site
View description>>
The yield of physical qubits fabricated in the laboratory is much lower thanthat of classical transistors in production semiconductor fabrication. Actualimplementations of quantum computers will be susceptible to loss in the form ofphysically faulty qubits. Though these physical faults must negatively affectthe computation, we can deal with them by adapting error correction schemes. Inthis paper We have simulated statically placed single-fault lattices andlattices with randomly placed faults at functional qubit yields of 80%, 90% and95%, showing practical performance of a defective surface code by employingactual circuit constructions and realistic errors on every gate, includingidentity gates. We extend Stace et al.'s superplaquettes solution againstdynamic losses for the surface code to handle static losses such as physicallyfaulty qubits. The single-fault analysis shows that a static loss at theperiphery of the lattice has less negative effect than a static loss at thecenter. The randomly-faulty analysis shows that 95% yield is good enough tobuild a large scale quantum computer. The local gate error rate threshold is$\sim 0.3\%$, and a code distance of seven suppresses the residual error ratebelow the original error rate at $p=0.1\%$. 90% yield is also good enough whenwe discard badly fabricated quantum computation chips, while 80% yield does notshow enough error suppression even when discarding 90% of the chips. Weevaluated several metrics for predicting chip performance, and found that theaverage of the product of the number of data qubits and the cycle time of astabilizer measurement of stabilizers gave the strongest correlation withpost-correction residual error rates. Our analysis will help with selectingusable quantum computation chips from among the pool of all fabricated chips.
Nemoto, K, Trupke, M, Devitt, SJ, Scharfenberger, B, Buczak, K, Schmiedmayer, J & Munro, WJ 2016, 'Photonic Quantum Networks formed from NV− centers', Scientific Reports, vol. 6, no. 1, p. 26284.
View/Download from: Publisher's site
View description>>
AbstractIn this article we present a simple repeater scheme based on the negatively-charged nitrogen vacancy centre in diamond. Each repeater node is built from modules comprising an optical cavity containing a single NV−, with one nuclear spin from 15N as quantum memory. The module uses only deterministic processes and interactions to achieve high fidelity operations (>99%) and modules are connected by optical fiber. In the repeater node architecture, the processes between modules by photons can be in principle deterministic, however current limitations on optical components lead the processes to be probabilistic but heralded. Our resource-modest repeater architecture contains two modules at each node and the repeater nodes are then connected by entangled photon pairs. We discuss the performance of such a quantum repeater network with modest resources and then incorporate more resource-intense strategies step by step. Our architecture should allow large-scale quantum information networks with existing or near future technology.
Paler, A, Devitt, SJ & Fowler, AG 2016, 'Synthesis of Arbitrary Quantum Circuits to Topological Assembly', Scientific Reports 6, Article number: 30600 (2016), vol. 6, no. 1, p. 30600.
View/Download from: Publisher's site
View description>>
Given a quantum algorithm, it is highly nontrivial to devise an efficientsequence of physical gates implementing the algorithm on real hardware andincorporating topological quantum error correction. In this paper, we present afirst step towards this goal, focusing on generating correct and simplearrangements of topological structures that correspond to a given quantumcircuit and largely neglecting their efficiency. We detail the many challengesthat will need to be tackled in the pursuit of efficiency. The software sourcecode can be consulted at https://github.com/alexandrupaler/tqec.
Paler, A, Wille, R & Devitt, SJ 2016, 'Wire Recycling for Quantum Circuit Optimization', Phys. Rev. A, vol. 94, no. 4, p. 042337.
View/Download from: Publisher's site
View description>>
Quantum information processing is expressed using quantum bits (qubits) andquantum gates which are arranged in the terms of quantum circuits. Here, eachqubit is associated to a quantum circuit wire which is used to conduct thedesired operations. Most of the existing quantum circuits allocate a singlequantum circuit wire for each qubit and, hence, introduce a significantoverhead. In fact, qubits are usually not needed during the entire computationbut only between their initialization and measurement. Before and after that,corresponding wires may be used by other qubits. In this work, we propose asolution which exploits this fact in order to optimize the design of quantumcircuits with respect to the required wires. To this end, we introduce arepresentation of the lifetimes of all qubits which is used to analyze therespective need for wires. Based on this analysis, a method is proposed which'recycles' the available wires and, by this, reduces the size of the resultingcircuit. Experimental evaluations based on established reversible andfault-tolerant quantum circuits confirm that the proposed solution reduces theamount of wires by more than 90% compared to unoptimized quantum circuits.
Pfister, C, Rol, MA, Mantri, A, Tomamichel, M & Wehner, S 2016, 'Capacity estimation and verification of quantum channels with arbitrarily correlated errors', Nature Communications, vol. 9, no. 1, pp. 27-27.
View/Download from: Publisher's site
View description>>
One of the main figures of merit for quantum memories and quantumcommunication devices is their quantum capacity. It has been studied forarbitrary kinds of quantum channels, but its practical estimation has so farbeen limited to devices that implement independent and identically distributed(i.i.d.) quantum channels, where each qubit is affected by the same noiseprocess. Real devices, however, typically exhibit correlated errors. Here, we overcome this limitation by presenting protocols that estimate achannel's one-shot quantum capacity for the case where the device acts on (anarbitrary number of) qubits. The one-shot quantum capacity quantifies adevice's ability to store or communicate quantum information, even if there arecorrelated errors across the different qubits. We present a protocol which is easy to implement and which comes in twoversions. The first version estimates the one-shot quantum capacity bypreparing and measuring in two different bases, where all involved qubits areused as test qubits. The second version verifies on-the-fly that a channel'sone-shot quantum capacity exceeds a minimal tolerated value while storing orcommunicating data, therefore combining test qubits and data qubits in oneprotocol. We discuss the performance of our method using simple examples, suchas the dephasing channel for which our method is asymptotically optimal.Finally, we apply our method to estimate the one-shot capacity in an experimentusing a transmon qubit.
Sanders, YR, Wallman, JJ & Sanders, BC 2016, 'Bounding quantum gate error rate based on reported average fidelity', New Journal of Physics, vol. 18, no. 1, pp. 012002-012002.
View/Download from: Publisher's site
View description>>
Remarkable experimental advances in quantum computing are exemplified by recent announcements of impressive average gate fidelities exceeding 99.9% for single-qubit gates and 99% for two-qubit gates. Although these high numbers engender optimism that fault-tolerant quantum computing is within reach, the connection of average gate fidelity with fault-tolerance requirements is not direct. Here we use reported average gate fidelity to determine an upper bound on the quantum-gate error rate, which is the appropriate metric for assessing progress towards fault-tolerant quantum computation, and we demonstrate that this bound is asymptotically tight for general noise. Although this bound is unlikely to be saturated by experimental noise, we demonstrate using explicit examples that the bound indicates a realistic deviation between the true error rate and the reported average fidelity. We introduce the Pauli distance as a measure of this deviation, and we show that knowledge of the Pauli distance enables tighter estimates of the error rate of quantum gates.
Sutter, D, Berta, M & Tomamichel, M 2016, 'Multivariate Trace Inequalities', Communications in Mathematical Physics: Volume 352, Number 1 (2017), Page 37-58, vol. 352, no. 1, pp. 37-58.
View/Download from: Publisher's site
View description>>
We prove several trace inequalities that extend the Golden-Thompson and theAraki-Lieb-Thirring inequality to arbitrarily many matrices. In particular, westrengthen Lieb's triple matrix inequality. As an example application of ourfour matrix extension of the Golden-Thompson inequality, we prove remainderterms for the monotonicity of the quantum relative entropy and strongsub-additivity of the von Neumann entropy in terms of recoverability. We findthe first explicit remainder terms that are tight in the commutative case. Ourproofs rely on complex interpolation theory as well as asymptotic spectralpinching, providing a transparent approach to treat generic multivariate traceinequalities.
Wang, H, Zheng, W, Yu, N, Li, K, Lu, D, Xin, T, Li, C, Ji, Z, Kribs, D, Zeng, B, Peng, X & Du, J 2016, 'Quantum State and Process Tomography via Adaptive Measurements', Science China: Physics, Mechanics and Astronomy, vol. 59, no. 10.
View/Download from: Publisher's site
View description>>
We investigate quantum state tomography (QST) for pure states and quantumprocess tomography (QPT) for unitary channels via $adaptive$ measurements. Fora quantum system with a $d$-dimensional Hilbert space, we first propose anadaptive protocol where only $2d-1$ measurement outcomes are used to accomplishthe QST for $all$ pure states. This idea is then extended to study QPT forunitary channels, where an adaptive unitary process tomography (AUPT) protocolof $d^2+d-1$ measurement outcomes is constructed for any unitary channel. Weexperimentally implement the AUPT protocol in a 2-qubit nuclear magneticresonance system. We examine the performance of the AUPT protocol when appliedto Hadamard gate, $T$ gate ($\pi/8$ phase gate), and controlled-NOT gate,respectively, as these gates form the universal gate set for quantuminformation processing purpose. As a comparison, standard QPT is alsoimplemented for each gate. Our experimental results show that the AUPT protocolthat reconstructing unitary channels via adaptive measurements significantlyreduce the number of experiments required by standard QPT without considerableloss of fidelity.
Wilde, MM, Tomamichel, M & Berta, M 2016, 'Converse bounds for private communication over quantum channels', IEEE Transactions on Information Theory, vol. 63, no. 3, pages 1792-1817, March 2017, vol. 63, no. 3, pp. 1792-1817.
View/Download from: Publisher's site
View description>>
This paper establishes several converse bounds on the private transmissioncapabilities of a quantum channel. The main conceptual development buildsfirmly on the notion of a private state, which is a powerful, uniquely quantummethod for simplifying the tripartite picture of privacy involving localoperations and public classical communication to a bipartite picture of quantumprivacy involving local operations and classical communication. This approachhas 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 generalmeta-converse bound for private communication, which has a number ofapplications. The meta-converse allows for proving that any quantum channel'srelative entropy of entanglement is a strong converse rate for privatecommunication. For covariant channels, the meta-converse also leads tosecond-order expansions of relative entropy of entanglement bounds for privatecommunication rates. For such channels, the bounds also apply to the privatecommunication setting in which the sender and receiver are assisted byunlimited public classical communication, and as such, they are relevant forestablishing various converse bounds for quantum key distribution protocolsconducted over these channels. We find precise characterizations for severalchannels of interest and apply the methods to establish several converse boundson the private transmission capabilities of all phase-insensitive bosonicchannels.
Wilde, MM, Tomamichel, M, Lloyd, S & Berta, M 2016, 'Gaussian hypothesis testing and quantum illumination', Physical Review Letters, vol. 119, no. 12, p. 12.
View/Download from: Publisher's site
View description>>
Quantum hypothesis testing is one of the most basic tasks in quantuminformation theory and has fundamental links with quantum communication andestimation theory. In this paper, we establish a formula that characterizes thedecay rate of the minimal Type-II error probability in a quantum hypothesistest of two Gaussian states given a fixed constraint on the Type-I errorprobability. This formula is a direct function of the mean vectors andcovariance matrices of the quantum Gaussian states in question. We give anapplication to quantum illumination, which is the task of determining whetherthere is a low-reflectivity object embedded in a target region with a brightthermal-noise bath. For the asymmetric-error setting, we find that a quantumillumination transmitter can achieve an error probability exponent strongerthan a coherent-state transmitter of the same mean photon number, andfurthermore, that it requires far fewer trials to do so. This occurs when thebackground thermal noise is either low or bright, which means that a quantumadvantage is even easier to witness than in the symmetric-error setting becauseit occurs for a larger range of parameters. Going forward from here, we expectour formula to have applications in settings well beyond those considered inthis paper, especially to quantum communication tasks involving quantumGaussian channels.
XIA, M & JI, Z 2016, 'The limits of computation', Chinese Science Bulletin, vol. 61, no. 4-5, pp. 404-408.
View/Download from: Publisher's site
View description>>
The powerful idea of computation has accompanied the development of human civilization, has deeply changed the way we live and work, and has accelerated the advancement of many areas of sciences. In this article, we explore the power and limits of computation from several different perspectives. We will discuss topics from the models of computation and Church-Turing thesis, to the impact of the P versus NP problem and quantum computing on our understanding of the limits of computation. More concretely, we will explore the computability and the halting problem, the efficiency problem of computation, the P versus NP problem. We then move on to the discussion of quantum computation, quantum algorithm for factoring and its implications, quantum simulation and the relation between quantum and classical computations.
Xin, T, Lu, D, Klassen, J, Yu, N, Ji, Z, Chen, J, Ma, X, Long, G, Zeng, B & Laflamme, R 2016, 'Quantum state tomography via reduced density matrices', Phys. Rev. Lett., 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 forcharacterizing quantum states. However it requires that the original globalstate 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 bytheir RDMs under the assumption that the global state is pure, but fail to beUD in the absence of that assumption. This discovery allows us to classifyquantum states according to their UD properties, with the requirement that eachclass be treated distinctly in the practice of simplifying quantum statetomography. Additionally we experimentally test the feasibility and stabilityof performing quantum state tomography via the measurement of local RDMs foreach class. These theoretical and experimental results advance the project ofperforming efficient and accurate quantum state tomography in practice.
Ying, M 2016, 'Introduction', ASIAN WOMEN, vol. 28, no. 4, pp. 3-9.
View/Download from: Publisher's site
Ambainis, A, Balodis, K, Belovs, A, Lee, T, Santha, M & Smotrovs, J 1970, 'Separations in query complexity based on pointer functions', Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, STOC '16: Symposium on Theory of Computing, ACM, pp. 800-813.
View/Download from: Publisher's site
Anshu, A, Belovs, A, Ben-David, S, Goos, M, Jain, R, Kothari, R, Lee, T & Santha, M 1970, 'Separations in Communication Complexity Using Cheat Sheets and Information Complexity', 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 555-564.
View/Download from: Publisher's site
Berta, M, Fawzi, O & Tomamichel, M 1970, 'Exploiting variational formulas for quantum relative entropy', 2016 IEEE International Symposium on Information Theory (ISIT), 2016 IEEE International Symposium on Information Theory (ISIT), IEEE, Barcelona, Spain, pp. 2844-2848.
View/Download from: Publisher's site
View description>>
The relative entropy is the basic concept underlying various information measures like entropy, conditional entropy and mutual information. Here, we discuss how to make use of variational formulas for measured relative entropy and quantum relative entropy for understanding the additivity properties of various entropic quantities that appear in quantum information theory. In particular, we show that certain lower bounds on quantum conditional mutual information are superadditive.
Bremner, MJ, Montanaro, A & Shepherd, D 1970, 'Average-case complexity versus approximate simulation of commuting quantum computations', 19th Conference on Quantum Information Processing, Banff, Canada.
Broadbent, A, Ji, Z, Song, F & Watrous, J 1970, 'Zero-Knowledge Proof Systems for QMA', 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, New Brunswick, NJ, pp. 31-40.
View/Download from: Publisher's site
Cui, SX, Ji, Z, Yu, N & Zeng, B 1970, 'Quantum capacities for entanglement networks', 2016 IEEE International Symposium on Information Theory (ISIT), 2016 IEEE International Symposium on Information Theory (ISIT), IEEE, Barcelona, Spain, pp. 1685-1689.
View/Download from: Publisher's site
View description>>
We discuss quantum capacities for two types of entanglement networks: Q for the quantum repeater network with free classical communication, and R for the tensor network as the rank of the linear operation represented by the tensor network. We find that Q always equals R in the regularized case for the same network graph. However, the relationships between the corresponding one-shot capacities Q1 and R1 are more complicated, and the min-cut upper bound is in general not achievable. We show that the tensor network can be viewed as a stochastic protocol with the quantum repeater network, such that R1 is a natural upper bound of Q1. We analyze the possible gap between R1 and Q1 for certain networks, and compare them with the one-shot classical capacity of the corresponding classical network.
de Vries, NJ, Arefin, AS, Mathieson, L, Lucas, B & Moscato, P 1970, 'Relative Neighborhood Graphs Uncover the Dynamics of Social Media Engagement', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), International Conference on Advanced Data Mining and Applications, Springer International Publishing, Gold Coast, Queensland, Australia, pp. 283-297.
View/Download from: Publisher's site
View description>>
In this paper, we examine if the Relative Neighborhood Graph (RNG) can reveal related dynamics of page-level social media metrics. A statistical analysis is also provided to illustrate the application of the method in two other datasets (the Indo-European Language dataset and the Shakespearean Era Text dataset). Using social media metrics on the world’s ‘top check-in locations’ Facebook pages dataset, the statistical analysis reveals coherent dynamical patterns. In the largest cluster, the categories ‘Gym’, ‘Fitness Center’, and ‘Sports and Recreation’ appear closely linked together in the RNG. Taken together, our study validates our expectation that RNGs can provide a “parameter-free" mathematical formalization of proximity. Our approach gives useful insights on user behaviour in social media page-level metrics as well as other applications.
Grochow, JA, Mulmuley, KD & Qiao, Y 1970, 'Boundaries of VP and VNP', Leibniz International Proceedings in Informatics Lipics, International Colloquium on Automata Languages and Programming, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Rome, Italy.
View/Download from: Publisher's site
View description>>
One fundamental question in the context of the geometric complexity theory approach to the VP vs. VNP conjecture is whether VP = VP, where VP is the class of families of polynomials that can be computed by arithmetic circuits of polynomial degree and size, and VP is the class of families of polynomials that can be approximated infinitesimally closely by arithmetic circuits of polynomial degree and size. The goal of this article is to study the conjecture in (Mulmuley, FOCS 2012) that VP is not contained in VP. Towards that end, we introduce three degenerations of VP (i.e., sets of points in VP), namely the stable degeneration Stable-VP, the Newton degeneration Newton-VP, and the p-definable one-parameter degeneration VP∗. We also introduce analogous degenerations of VNP. We show that Stable-VP ⊆ Newton-VP ⊆ VP∗ ⊆ VNP, and Stable-VNP = Newton-VNP = VNP∗ = VNP. The three notions of degenerations and the proof of this result shed light on the problem of separating VP from VP. Although we do not yet construct explicit candidates for the polynomial families in VP \VP, we prove results which tell us where not to look for such families. Specifically, we demonstrate that the families in Newton-VP \VP based on semi-invariants of quivers would have to be nongeneric by showing that, for many finite quivers (including some wild ones), Newton degeneration of any generic semi-invariant can be computed by a circuit of polynomial size. We also show that the Newton degenerations of perfect matching Pfaffians, monotone arithmetic circuits over the reals, and Schur polynomials have polynomial-size circuits.
Haah, J, Harrow, AW, Ji, Z, Wu, X & Yu, N 1970, 'Sample-optimal tomography of quantum states', Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, STOC '16: Symposium on Theory of Computing, ACM, Cambridge, MA, USA, pp. 913-925.
View/Download from: Publisher's site
View description>>
It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. This is the quantum analogue of the problem of estimating a probability distribution given some number of samples.
Previously, it was known only that estimating states to error є in trace distance required O(dr2/є2) copies for a d-dimensional density matrix of rank r. Here, we give a measurement scheme (POVM) that uses O( (dr/ δ ) ln(d/δ) ) copies to estimate ρ to error δ in infidelity. This implies O( (dr / є2)· ln(d/є) ) copies suffice to achieve error є in trace distance. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.
We also use the Holevo bound from quantum information theory to prove a lower bound of Ω(dr/є2)/ log(d/rє) copies needed to achieve error є in trace distance. This implies a lower bound Ω(dr/δ)/log(d/rδ) for the estimation error δ in infidelity. These match our upper bounds up to log factors.
Our techniques can also show an Ω(r2d/δ) lower bound for measurement strategies in which each copy is measured individually and then the outcomes are classically post-processed to produce an estimate. This matches the known achievability results and proves for the first time that such “product” measurements have asymptotically suboptimal scaling with d and r.
Ji, Z 1970, 'Classical verification of quantum proofs', Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, STOC '16: Symposium on Theory of Computing, ACM, Cambridge, MA, USA, pp. 885-898.
View/Download from: Publisher's site
View description>>
We present a classical interactive protocol that verifies the validity of a quantum witness state for the local Hamiltonian problem. It follows from this protocol that approximating the non-local value of a multi-player one-round game to inverse polynomial precision is QMA-hard. Our work makes an interesting connection between the theory of QMA-completeness and Hamiltonian complexity on one hand and the study of non-local games and Bell inequalities on the other.
Lanese, I & Devitt, S 1970, 'Preface', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).
Lee Jae Hee, Li Sanjiang, Long Zhiguo & Sioutis Michael 1970, 'On Redundancy in Simple Temporal Networks', Frontiers in Artificial Intelligence and Applications, European Conference on Artificial Intelligence, IOS Press, Netherlands, pp. 828-836.
View/Download from: Publisher's site
View description>>
The Simple Temporal Problem (STP) has been widely used in various applications to schedule tasks. For dynamical systems, scheduling needs to be efficient and flexible to handle uncertainty and perturbation. To this end, modern approaches usually encode the temporal information as an STP instance. This representation contains redundant information, which can not only take a significant amount of storage space, but also make scheduling inefficient due to the non-concise representation. In this paper, we investigate the problem of simplifying an STP instance by removing redundant information. We show that such a simplification can result in a unique minimal representation without loss of temporal information, and present an efficient algorithm to achieve this task. Evaluation on a large benchmark dataset of STP exhibits a significant reduction in redundant information for the involved instances.
Lee, T, Prakash, A, Wolf, RD & Yuen, H 1970, 'On the sum-of-squares degree of symmetric quadratic functions', Leibniz International Proceedings in Informatics, LIPIcs, p. 17:1-17:31.
View/Download from: Publisher's site
View description>>
We study how well functions over the boolean hypercube of the form$f_k(x)=(|x|-k)(|x|-k-1)$ can be approximated by sums of squares of low-degreepolynomials, obtaining good bounds for the case of approximation in$\ell_{\infty}$-norm as well as in $\ell_1$-norm. We describe threecomplexity-theoretic applications: (1) a proof that the recent breakthroughlower bound of Lee, Raghavendra, and Steurer on the positive semidefiniteextension complexity of the correlation and TSP polytopes cannot be improvedfurther by showing better sum-of-squares degree lower bounds on$\ell_1$-approximation of $f_k$; (2) a proof that Grigoriev's lower bound onthe degree of Positivstellensatz refutations for the knapsack problem isoptimal, answering an open question from his work; (3) bounds on the querycomplexity of quantum algorithms whose expected output approximates suchfunctions.
Long, Z, Schockaert, S & Li, S 1970, 'Encoding large RCC8 scenarios using rectangular pseudo-solutions', Proceedings of the International Conference on Knowledge Representation and Reasoning, International Conference on Principles of Knowledge Representation and Reasoning, Association for the Advancement of Artificial Intelligence, Cape Town, South Africa, pp. 463-472.
View description>>
Most approaches in the field of qualitative spatial reasoning (QSR) use constraint networks to encode spatial scenarios. The size of these networks is quadratic in the number of variables, which has severely limited the real-world application of QSR. In this paper, we propose another representation of spatial scenarios, in which each variable is associated with one or more rectangles. Instead of requiring these rectangles to define a solution of the corresponding constraint network, we construct sequences of rectangles that define partial solutions to progressively weaker constraint networks. We present experimental results that illustrate the effectiveness of this strategy.
Long, Z, Sioutis, M & Li, S 1970, 'Efficient path consistency algorithm for large qualitative constraint networks', Ijcai International Joint Conference on Artificial Intelligence, International Joint Conference on Artificial Intelligence, AAAI Press, New York City, USA, pp. 1202-1208.
View description>>
We propose a new algorithm called DPC+ to enforce partial path consistency (PPC) on qualitative constraint networks. PPC restricts path consistency (PC) to a triangulation of the underlying constraint graph of a network. As PPC retains the sparseness of a constraint graph, it can make reasoning tasks such as consistency checking and minimal labelling of large qualitative constraint networks much easier to tackle than PC. For qualitative constraint networks defined over any distributive subalgebra of well-known spatio-temporal calculi, such as the Region Connection Calculus and the Interval Algebra, we show that DPC+ can achieve PPC very fast. Indeed, the algorithm enforces PPC on a qualitative constraint network by processing each triangle in a triangulation of its underlying constraint graph at most three times. Our experiments demonstrate significant improvements of DPC+ over the state-of-the-art PPC enforcing algorithm.
Sioutis, M, Long, Z & Li, S 1970, 'Efficiently Reasoning about Qualitative Constraints through Variable Elimination', Proceedings of the 9th Hellenic Conference on Artificial Intelligence, SETN '16: 9th Hellenic Conference on Artificial Intelligence, ACM, Thessaloniki, Greece, pp. 1-10.
View/Download from: Publisher's site
View description>>
© 2016 ACM.We introduce, study, and evaluate a novel algorithm in the context of qualitative constraint-based spatial and temporal reasoning, that is based on the idea of variable elimination, a simple and general exact inference approach in probabilistic graphical models. Given a qualitative constraint network M, our algorithm enforces a particular directional local consistency on M, which we denote by ←-consistency. Our discussion is restricted to distributive subclasses of relations, i.e., sets of relations closed under converse, intersection, and weak composition and for which weak composition distributes over non-empty intersections for all of their relations. We demonstrate that enforcing ←-consistency on a given qualitative constraint network defined over a distributive subclass of relations allows us to decide its satisfiability. The experimentation that we have conducted with random and real-world qualitative constraint networks defined over a distributive subclass of relations of the Region Connection Calculus, shows that our approach exhibits unparalleled performance against competing state-of-the-art approaches for checking the satisfiability of such constraint networks.
Sutter, D, Tomamichel, M & Harrow, AW 1970, 'Strengthened monotonicity of relative entropy via pinched Petz recovery map', 2016 IEEE International Symposium on Information Theory (ISIT), 2016 IEEE International Symposium on Information Theory (ISIT), IEEE, Barcelona, pp. 760-764.
View/Download from: Publisher's site
Tomamichel, M & Hayashi, M 1970, 'Operational interpretation of Rényi conditional mutual information via composite hypothesis testing against Markov distributions', 2016 IEEE International Symposium on Information Theory (ISIT), 2016 IEEE International Symposium on Information Theory (ISIT), IEEE, Barcelona, Spain, pp. 585-589.
View/Download from: Publisher's site
View description>>
We revisit the problem of asymmetric binary hypothesis testing against a composite alternative hypothesis. We introduce a general framework to treat such problems when the alternative hypothesis adheres to certain axioms. In this case we find the threshold rate, the optimal error and strong converse exponents (at large deviations from the threshold) and the second-order asymptotics (at small deviations from the threshold). We apply our results to find operational interpretations of Rényi information measures. In particular, in case the alternative hypothesis consists of certain tripartite distributions satisfying the Markov property, we find that the optimal exponents are determined by the Rényi conditional mutual information
