Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTowards the Notion of an Abstract Quantum Automaton
57
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The main goal of this paper is to give a rigorous mathematical description of systems for processing quantum information. To do it authors consider abstract state machines as models of classical computational systems. This class of machines is refined by introducing constrains on a state structure, namely, it is assumed that state of computational process has two components: a control unit state and a memory state. Then authors modify the class of models by substituting the deterministic evolutionary mechanism for a stochastic evolutionary mechanism. This approach can be generalized to the quantum case: one can replace transformations of a classical memory with quantum operations on a quantum memory. Hence the authors come to the need to construct a mathematical model of an operation on the quantum memory. It leads them to the notion of an abstract quantum automaton. Further the authors demonstrate that a quantum teleportation process is described as evolutionary process for some abstract quantum automaton.
rate research
Read More
Signals are a classical tool used in cellular automata constructions that proved to be useful for language recognition or firing-squad synchronisation. Particles and collisions formalize this idea one step further, describing regular nets of colliding signals. In the present paper, we investigate the use of particles and collisions for constructions involving an infinite number of interacting particles. We obtain a high-level construction for a new smallest intrinsically universal cellular automaton with 4 states.
It has been known for almost three decades that many $mathrm{NP}$-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit $C$ with $n$ uninitialized inputs, $mathit{poly}(n)$ gates, and treewidth $t$, one can compute in time $(frac{n}{delta})^{exp(O(t))}$ a classical assignment $yin {0,1}^n$ that maximizes the acceptance probability of $C$ up to a $delta$ additive factor. In particular, our algorithm runs in polynomial time if $t$ is constant and $1/poly(n) < delta < 1$. For unrestricted values of $t$, this problem is known to be complete for the complexity class $mathrm{QCMA}$, a quantum generalization of MA. In contrast, we show that the same problem is $mathrm{NP}$-complete if $t=O(log n)$ even when $delta$ is constant. On the other hand, we show that given a $n$-input quantum circuit $C$ of treewidth $t=O(log n)$, and a constant $delta<1/2$, it is $mathrm{QMA}$-complete to determine whether there exists a quantum state $mid!varphirangle in (mathbb{C}^d)^{otimes n}$ such that the acceptance probability of $Cmid!varphirangle$ is greater than $1-delta$, or whether for every such state $mid!varphirangle$, the acceptance probability of $Cmid!varphirangle$ is less than $delta$. As a consequence, under the widely believed assumption that $mathrm{QMA} eq mathrm{NP}$, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.
A leading proposal for verifying near-term quantum supremacy experiments on noisy random quantum circuits is linear cross-entropy benchmarking. For a quantum circuit $C$ on $n$ qubits and a sample $z in {0,1}^n$, the benchmark involves computing $|langle z|C|0^n rangle|^2$, i.e. the probability of measuring $z$ from the output distribution of $C$ on the all zeros input. Under a strong conjecture about the classical hardness of estimating output probabilities of quantum circuits, no polynomial-time classical algorithm given $C$ can output a string $z$ such that $|langle z|C|0^nrangle|^2$ is substantially larger than $frac{1}{2^n}$ (Aaronson and Gunn, 2019). On the other hand, for a random quantum circuit $C$, sampling $z$ from the output distribution of $C$ achieves $|langle z|C|0^nrangle|^2 approx frac{2}{2^n}$ on average (Arute et al., 2019). In analogy with the Tsirelson inequality from quantum nonlocal correlations, we ask: can a polynomial-time quantum algorithm do substantially better than $frac{2}{2^n}$? We study this question in the query (or black box) model, where the quantum algorithm is given oracle access to $C$. We show that, for any $varepsilon ge frac{1}{mathrm{poly}(n)}$, outputting a sample $z$ such that $|langle z|C|0^nrangle|^2 ge frac{2 + varepsilon}{2^n}$ on average requires at least $Omegaleft(frac{2^{n/4}}{mathrm{poly}(n)}right)$ queries to $C$, but not more than $Oleft(2^{n/3}right)$ queries to $C$, if $C$ is either a Haar-random $n$-qubit unitary, or a canonical state preparation oracle for a Haar-random $n$-qubit state. We also show that when $C$ samples from the Fourier distribution of a random Boolean function, the naive algorithm that samples from $C$ is the optimal 1-query algorithm for maximizing $|langle z|C|0^nrangle|^2$ on average.
We show that any quantum circuit of treewidth $t$, built from $r$-qubit gates, requires at least $Omega(frac{n^{2}}{2^{O(rcdot t)}cdot log^4 n})$ gates to compute the element distinctness function. Our result generalizes a near-quadratic lower bound for quantum formula size obtained by Roychowdhury and Vatan [SIAM J. on Computing, 2001]. The proof of our lower bound follows by an extension of Nev{c}iporuks method to the context of quantum circuits of constant treewidth. This extension is made via a combination of techniques from structural graph theory, tensor-network theory, and the connected-component counting method, which is a classic tool in algebraic geometry.
The classical communication complexity of testing closeness of discrete distributions has recently been studied by Andoni, Malkin and Nosatzki (ICALP19). In this problem, two players each receive $t$ samples from one distribution over $[n]$, and the goal is to decide whether their two distributions are equal, or are $epsilon$-far apart in the $l_1$-distance. In the present paper we show that the quantum communication complexity of this problem is $tilde{O}(n/(tepsilon^2))$ qubits when the distributions have low $l_2$-norm, which gives a quadratic improvement over the classical communication complexity obtained by Andoni, Malkin and Nosatzki. We also obtain a matching lower bound by using the pattern matrix method. Let us stress that the samples received by each of the parties are classical, and it is only communication between them that is quantum. Our results thus give one setting where quantum protocols overcome classical protocols for a testing problem with purely classical samples.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
