Algebraic Topology Quantum Algorithms and BIG carusott/QUANTUMGEO17/SLIDES/ Topology , Quantum Algorithms and BIGDATA ... A new Buzzword: BIG DATA ZB=1,000,000,000,000,000,000,000 ... We live in the BIG DATA

  • Published on
    27-Mar-2018

  • View
    213

  • Download
    1

Transcript

  • Algebraic Topology, Quantum Algorithmsand BIG DATA

    Quantum Physics andGeometry" (2017) Paolo Zanardi,USC LosAngeles

  • AnewBuzzword: BIGDATA

    ZB=1,000,000,000,000,000,000,000 =10^21Bytes

  • WhatsBIGDATA?

  • AndWe(=QuantumInformationFolks)makenodifference..

  • TodaysTalkisaboutyetanotherBigQuantumDataapproach:

    The Bad The Good The Ugly

  • ExtractingSmallPatternsoutBigData:TOPOLOGY

    Classification ofvastsets ofcomplex objects intermsofsimple topological invariants

  • Topological Invariants:EulersCharacteristics

    E=2(1-g),g=genus

    Letsrefinethisconceptfortriangulable spaces(homeomorphictopolyhedra):SimplicialComplexes

  • BoundaryMap&ChainComplexes

    Cn=n-th ChainGroup=Formallinearcombinationsofsimplices ofthecomplex

    Boundary Map: sends asimplex toacombination ofitsfaces

    Nilpotency=boundary ofboundary is0

  • HomologyGroups

    k=#ofgeneratorsofHk=Betti Number

    0=#ofconnected components,

    1=#of holes,

    2=#voids,...

    E.Betti,1823-1892Eulers Characteristic

  • ComplexesfromPointCloudData(PCD)

    Foreachscaleof onebuildsasimplicialcomplexS outofthePCDincreasingmakesS growingVarying overarangeofscalesoneobtainsafamilyofnestedsimplicialcomplexesakaaFiltration

    Datacanberepresented by clouds ofpoints in ahigh dimensional space: howdowedotopologywiththat?!?

    ech complex Vietoris-Rips complex

  • ComplexFiltrationsandBarCodes

    Tracking how Betti numbers change as function of the scale reveals how topological features come into existence and go away as the data is analyzed at different

    Atopologicalfeaturethatpersistsovermanylengthscalescanbeidentifiedwithatruefeatureofthestructure:PersistentHomology

  • 2)FindthekerneloftheLaplacian togettheBetti Numbers(QuantumPhaseestimation Algorithm)

    0)Store(orcompute)distances betweendatapoints ina Q-RAM

    1)Fix,constructaquantumstateencodingsimplicial complexatthescale (GroverSearchAlgorithm)

    3)Iterateoverthe andlookforpersistent featuresacrossscales

    QuantumAlgorithm forPersistentHomology:TheSketch

    HowAboutcomputationalcomplexity?!?

  • ComputationalComplexity:Classical vsQuantum

    OurQuantumalgorithmprovidesandexponentialspeed-upovertheclassicalone!

    QUANTUM SUPREMACY....

  • GroversSearchAlgorithm:

    Spacegenerated bythek-simplex states inthe-Complex, --dimensional

    Letsk ak-simplexwemapitontoaquantumstate|sk>=|j1,j2,,jn>wherejp=1 iffp isinsk

    TheGutsoftheQuantumAlgorithm I

    Takes timewhereisfractionofsimplices actually present inthe-Complex; Classical time

    QuantumPipeline1:Encodingthe-Complex

  • TheGutsoftheQuantumAlgorithm II

    CombinatorialHodgeTheory:Betti numbersarethedimensions ofthekernelsofthe-complexLaplacian operators(0-eigenvectors=Harmonic forms toHomology classes)

    Ifthen ffisthe-complexDiracoperator

    RuntheQuantumPhaseAlgorithmfor overtheuniformmixture ofallsimplicesDetermines thedimensions ofi.e.,theBettis numbers

    Classically: Quantumly (n-sparsity)

    QuantumPipeline2

  • Summary&Conclusions

    QuantumInformationProcessing inkickinginBIGtime intheBigDATAsceneweareexcited!

    WeliveintheBIGDATAageANDintheQuantumInformationAge

    BigQuantumDataalgorithmswithexponential speedups e.g.,Q-machinelearning

    Wedescribed atopologicaldataanalysisquantumalgorithm forpersistenthomology

  • Well,someone@MIT alittleover-excited,perhaps.

    THANKSFORTHEATTENTION!!

    Seth Lloyd

    Universal PersistentQuantum theoryofEVERYTHING

Recommended

View more >