Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies

• URL: http://arxiv.org/abs/2204.10671v1
• Date: Fri, 22 Apr 2022 12:37:56 GMT
• Title: Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies
• Authors: Kamil Khadiev, Aliya Khadieva and Alexander Knop
• Abstract summary: We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
• Score: 68.93512627479197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study quantum Ordered Binary Decision Diagrams($OBDD$) model; it is a restricted version of read-once quantum branching programs, with respect to "width" complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present a new technique ("reordering") for proving lower bounds and upper bounds for OBDD with an arbitrary order of input variables if we have similar bounds for the natural order. Using this transformation, we construct a total function $REQ$ such that the deterministic $OBDD$ complexity of it is at least $2^{\Omega(n / \log n)}$, and the quantum $OBDD$ complexity of it is at most $O(n^2/\log n)$. It is the biggest known gap for explicit functions not representable by $OBDD$s of a linear width. Another function(shifted equality function) allows us to obtain a gap $2^{\Omega(n)}$ vs $O(n^2)$. Moreover, we prove the bounded error quantum and probabilistic $OBDD$ width hierarchies for complexity classes of Boolean functions. Additionally, using "reordering" method we extend a hierarchy for read-$k$-times Ordered Binary Decision Diagrams ($k$-$OBDD$) of polynomial width, for $k = o(n / \log^3 n)$. We prove a similar hierarchy for bounded error probabilistic $k$-$OBDD$s of polynomial, superpolynomial and subexponential width. The extended abstract of this work was presented on International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8 -- 12, 2017

Related papers

• Efficient Quantum State Synthesis with One Query [0.0]
  We present a time analogue quantum algorithm making a single query (in superposition) to a classical oracle. We prove that every $n$-qubit state can be constructed to within 0.01 error by an $On/n)$-size circuit over an appropriate finite gate set.
  arXiv  Detail & Related papers  (2023-06-02T17:49:35Z)
• Pauli-based model of quantum computation with higher-dimensional systems [0.0]
  Pauli-based computation (PBC) is a universal model for quantum computation with qubits. We generalize PBC for odd-prime-dimensional systems and demonstrate its universality.
  arXiv  Detail & Related papers  (2023-02-27T12:05:13Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
  arXiv  Detail & Related papers  (2020-12-03T14:03:20Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions [3.652509571098291]
  We first obtain optimal exact quantum query algorithms ($Q_algo(f)$) for a direct sum based class of $Omega left( 2fracsqrtn2 right)$ non-symmetric functions. We show that query complexity of $Q_algo$ is $lceil frac3n4 rceil$ whereas $D_oplus(f)$ varies between $n-1$ and $lceil frac3n4 rce
  arXiv  Detail & Related papers  (2020-08-14T12:17:48Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  We find an algorithm which finds. epsilon$-approximate stationary point (with $|nabla F(x)|le epsilon$) using. $(epsilon,gamma)$surimate random random points. Our lower bounds here are novel even in the noiseless case.
  arXiv  Detail & Related papers  (2020-06-24T04:41:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.