We initiate the study of the relationship between two complexity classes, BQP
(Bounded-Error Quantum Polynomial-Time) and PPAD (Polynomial Parity Argument,
Directed). We first give a conjecture that PPAD is contained in BQP, and show
a necessary and sufficient condition for the conjecture to hold. Then we prove
that the conjecture ... more >>>

For each natural number $d$ we consider a finite structure $M_{d}$ whose
universe is the set of all $0,1$-sequence of length $n=2^{d}$, each
representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace
$ in binary form.
The operations included in the structure are the
constants $0,1,2^{n}-1,n$, multiplication and addition ... more >>>

In this paper, we study the problem of testing the conductance of a
given graph in the general graph model. Given distance parameter
$\varepsilon$ and any constant $\sigma>0$, there exists a tester
whose running time is $\mathcal{O}(\frac{m^{(1+\sigma)/2}\cdot\log
n\cdot\log\frac{1}{\varepsilon}}{\varepsilon\cdot\Phi^2})$, where
$n$ is the number of vertices and $m$ is the number ... more >>>