Vi definierar en ny modell för kvantinlärning som vi kallar Predictive Quantum (PQ). Detta är en kvantanalog av PAC, där studenten under testfasen endast krävs för att svara på ett polynomtal testfrågor. Vi demonstrerar en relationell koncept klass som är effektivt lärbar i PQ, medan i någon "rimlig" klassisk modell exponentiellt mängd träningsdata skulle krävas. Detta är den första ovillkorliga åtskillnaden mellan kvant och klassiskt lärande. Vi visar att vår separation är den bästa möjliga på flera sätt; i synnerhet, det finns inget jämförbart resultat för en funktionell klass, liksom för flera svagare versioner av kvantinlärning. För att visa täthet av vår separation anser vi att ett specialfall av enkelriktad kommunikation som vi kallar enkelinmatningsläge, där Bob inte får någon ingång. Något överraskande, denna inställning blir icke-trivial när relationskommunikation uppgifter beaktas. I synnerhet kan alla problem med tvåsidig inmatning omvandlas till ett enda input relationsproblem med lika klassiska enkelriktade kostnader. Vi visar att situationen är annorlunda i kvantfallet, där samma omvandling kan göra kommunikationens komplexitet exponentiellt större. Detta händer om och endast om det ursprungliga problemet har exponentiellt gap mellan kvant och klassiska enkelriktade kommunikationskostnader. Vi tror att dessa kompletterande resultat kan vara av oberoende intresse.
Gavinsky REF introducerade en modell av lärande som kallas "Predictive Quantum" (PQ), en variation av kvant PAC lärande, och visade en relationell koncept klass som är polynom-tid lärbar i PQ, medan någon "rimlig" klassisk modell kräver ett exponentiellt antal klassiska exempel för att lära sig konceptklassen.
Quantum Predictive Learning and Communication Complexity with Single Input
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Physics']}