Sample-size-reduction of quantum states for the noisy linear problem

Abstract

Quantum supremacy poses that a realistic quantum computer can perform a calculation that classical computers cannot in any reasonable amount of time. It has become a topic of significant research interest since the birth of the field, and it is intrinsically based on the efficient construction of quantum algorithms. It has been shown that there exists an expeditious way to solve the noisy linear (or learning with errors) problems in quantum machine learning theory via a well-posed quantum sampling over pure quantum states. In this paper, we propose an advanced method to reduce the sample size in the noisy linear structure, through a technique of randomizing quantum states, namely, $\epsilon$-random technique. Particularly, we show that it is possible to reduce a quantum sample size in a quantum random access memory (QRAM) to the linearithmic order, in terms of the dimensions of the input-data. Thus, we achieve a shorter run-time for the noisy linear problem.

arXiv comment11 pages, 2 figures, 1 table; Close to published version

References in corpus (29)

• Quantum Machine Learning
• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum algorithm for solving linear systems of equations
• Supervised learning with quantum enhanced feature spaces
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum random access memory
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Superadditivity of communication capacity using entangled inputs
• Toward the first quantum simulation with quantum speedup
• Randomizing quantum states: Constructions and applications
• Architectures for a quantum random access memory
• Superdense coding of quantum states
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• On the robustness of bucket brigade quantum RAM
• Counterexamples to the maximal p-norm multiplicativity conjecture for all p > 1
• Quantum learning robust to noise
• Reexamination of optimal quantum state estimation of pure states
• Learning with Errors is easy with quantum samples
• On almost randomizing channels with a short Kraus decomposition
• Approximate Randomization of Quantum States With Fewer Bits of Key
• Universal compressive characterization of quantum dynamics
• On the Optimality of Quantum Encryption Schemes
• Continuous variable private quantum channel
• Gaussian private quantum channel with squeezed coherent states
• Optimality of private quantum channels
• Quantum solvability of noisy linear problems by divide-and-conquer strategy
• Secure sequential transmission of quantum information
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation