اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدQuantum Property Testing
274
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x is in L and x has large Hamming distance from all y in L. We define a similar notion of quantum property testing and show that there exist languages with quantum property testers but no good classical testers. We also show there exist languages which require a large number of queries even for quantumly testing.
قيم البحث
اقرأ أيضاً
We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound. For testing expansion, we also pr
ove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph structure.
To guarantee the normal functioning of quantum devices in different scenarios, appropriate benchmarking tool kits are quite significant. Inspired by the recent progress on quantum state verification, here we establish a general framework of verifying
a target unitary gate. In both the non-adversarial and adversarial scenarios, we provide efficient methods to evaluate the performance of verification strategies for any qudit unitary gate. Furthermore, we figure out the optimal strategy and its realization with local operations. Specifically, for the commonly-used quantum gates like single qubit and qudit gates, multi-qubit Clifford gates, and multi-qubit Controlled-Z(X) gates, we provide efficient verification protocols. Besides, we discuss the application of gate verification for the detection of entanglement-preserving property of quantum channels and further quantify the robustness measure of them. We believe that the gate verification is a promising way to benchmark a large-scale quantum circuit as well as to test its property.
We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with $P$ the Markov chain transition matrix and $D
= sqrt{Pcirc P^T}$ its discriminant matrix ($D=P$ if $P$ is symmetric), we construct a quantum walk algorithm that for any quantum state $|vrangle$ and integer $t$ returns a quantum state $epsilon$-close to the state $D^t|vrangle/|D^t|vrangle|$. The algorithm uses $OBig(|D^t|vrangle|^{-1}sqrt{tlog(epsilon|D^t|vrangle|)^{-1}}Big)$ expected quantum walk steps and $O(|D^t|vrangle|^{-1})$ expected reflections around $|vrangle$. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of $s$-$t$ connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.
The classical asymptotic equipartition property is the statement that, in the limit of a large number of identical repetitions of a random experiment, the output sequence is virtually certain to come from the typical set, each member of which is almo
st equally likely. In this paper, we prove a fully quantum generalization of this property, where both the output of the experiment and side information are quantum. We give an explicit bound on the convergence, which is independent of the dimensionality of the side information. This naturally leads to a family of Renyi-like quantum conditional entropies, for which the von Neumann entropy emerges as a special case.
The problem of quantum test is formally addressed. The presented method attempts the quantum role of classical test generation and test set reduction methods known from standard binary and analog circuits. QuFault, the authors software package genera
tes test plans for arbitrary quantum circuits using the very efficient simulator QuIDDPro[1]. The quantum fault table is introduced and mathematically formalized, and the test generation method explained.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
