Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum Property Testing
274
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 prove 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 almost 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 generates 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
