Ryuhei Mori
YOU?
Author Swipe
View article: Complexity of graph-state preparation by Clifford circuits
Complexity of graph-state preparation by Clifford circuits Open
In this work, we study the complexity of graph-state preparation. We consider general quantum algorithms consisting of Clifford operations acting on at most two qubits for graph-state preparations. We define the CZ-complexity of a graph st…
View article: Parameterized Quantum Query Algorithms for Graph Problems
Parameterized Quantum Query Algorithms for Graph Problems Open
In this paper, we consider the parameterized quantum query complexity for graph problems. We design parameterized quantum query algorithms for k-vertex cover and k-matching problems, and present lower bounds on the parameterized quantum qu…
View article: Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection
Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection Open
In this paper, we propose a quantum algorithm that supports a real-valued\nhigher-order unconstrained binary optimization (HUBO) problem. This algorithm\nis based on the Grover adaptive search that originally supported HUBO with\ninteger c…
View article: Lower bounds on the error probability of multiple quantum channel discrimination by the Bures angle and the trace distance
Lower bounds on the error probability of multiple quantum channel discrimination by the Bures angle and the trace distance Open
Quantum channel discrimination is a fundamental problem in quantum information science. In this study, we consider general quantum channel discrimination problems, and derive the lower bounds of the error probability. Our lower bounds are …
View article: Quantum speedups for dynamic programming on $n$-dimensional lattice graphs
Quantum speedups for dynamic programming on $n$-dimensional lattice graphs Open
Motivated by the quantum speedup for dynamic programming on the Boolean hypercube by Ambainis et al. (2019), we investigate which graphs admit a similar quantum advantage. In this paper, we examine a generalization of the Boolean hypercube…
View article: The numerical results for the complexity of the quantum algorithm for dynamic programming on n-dimensional lattice graph
The numerical results for the complexity of the quantum algorithm for dynamic programming on n-dimensional lattice graph Open
This is a data set for the paper "Quantum speedups for dynamic programming on n-dimensional lattice graphs", with the full version available at https://arxiv.org/abs/2104.14384. Each file SolverDAKB.nb contains the Mathematica code to find…
View article: The numerical results for the complexity of the quantum algorithm for dynamic programming on n-dimensional lattice graph
The numerical results for the complexity of the quantum algorithm for dynamic programming on n-dimensional lattice graph Open
This is a data set for the paper "Quantum speedups for dynamic programming on n-dimensional lattice graphs", with the full version available at https://arxiv.org/abs/2104.14384. Each file SolverDAKB.nb contains the Mathematica code to find…
View article: Fine-grained analysis and improved robustness of quantum supremacy for random circuit sampling
Fine-grained analysis and improved robustness of quantum supremacy for random circuit sampling Open
We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that estimating the output probabilities of random quantum circuits to within $\exp(-\Omega(m\log m))$ additive error is hard for any clas…
View article: Improved robustness of quantum supremacy for random circuit sampling
Improved robustness of quantum supremacy for random circuit sampling Open
Motivated by the recent experimental demonstrations of quantum supremacy, proving the hardness of the output of random quantum circuits is an imperative near term goal. We prove under the complexity theoretical assumption of the non-collap…
View article: Quantum supremacy and hardness of estimating output probabilities of quantum circuits
Quantum supremacy and hardness of estimating output probabilities of quantum circuits Open
Motivated by the recent experimental demonstrations of quantum supremacy, proving the hardness of the output of random quantum circuits is an imperative near term goal. We prove under the complexity theoretical assumption of the non-collap…
View article: A Simple and Fast Algorithm for Computing the <i>N</i>-th Term of a Linearly Recurrent Sequence
A Simple and Fast Algorithm for Computing the <i>N</i>-th Term of a Linearly Recurrent Sequence Open
We present a simple and fast algorithm for computing the N-th term of a given linearly recurrent sequence. Our new algorithm uses O(M(d) log N) arithmetic operations, where d is the order of the recurrence, and M(d) denotes the number of a…
View article: Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs
Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs Open
Motivated by the quantum speedup for dynamic programming on the Boolean hypercube by Ambainis et al. (2019), we investigate which graphs admit a similar quantum advantage. In this paper, we examine a generalization of the Boolean hypercube…
View article: A Simple and Fast Algorithm for Computing the $N$-th Term of a Linearly Recurrent Sequence
A Simple and Fast Algorithm for Computing the $N$-th Term of a Linearly Recurrent Sequence Open
We present a simple and fast algorithm for computing the $N$-th term of a given linearly recurrent sequence. Our new algorithm uses $O(\mathsf{M}(d) \log N)$ arithmetic operations, where $d$ is the order of the recurrence, and $\mathsf{M}(…
View article: Exponential-time quantum algorithms for graph coloring problems
Exponential-time quantum algorithms for graph coloring problems Open
The fastest known classical algorithm deciding the $k$-colorability of $n$-vertex graph requires running time $Ω(2^n)$ for $k\ge 5$. In this work, we present an exponential-space quantum algorithm computing the chromatic number with runnin…
View article: Periodic Fourier representation of Boolean functions
Periodic Fourier representation of Boolean functions Open
In this work, we consider a new type of Fourier-like representation of Boolean function $f\colon\{+1,-1\}^n\to\{+1,-1\}$ \[ f(x) = \cos\left(π\sum_{S\subseteq[n]}ϕ_S \prod_{i\in S} x_i\right). \] This representation, which we call the peri…
View article: Average Length of Cycles in Rectangular Lattice
Average Length of Cycles in Rectangular Lattice Open
We study the number of cycles and their average length in $L\times N$ lattice by using classical method of transfer matrix. In this work, we derive a bivariate generating function $G_3(y, z)$ in which a coefficient of $y^i z^j$ is the numb…
View article: Sum of squares lower bounds for refuting any CSP
Sum of squares lower bounds for refuting any CSP Open
Let P:{0,1}k → {0,1} be a nontrivial k-ary predicate. Consider a random instance of the constraint satisfaction problem (P) on n variables with Δ n constraints, each being P applied to k randomly chosen literals. Provided the constraint de…
View article: Sum of squares lower bounds for refuting any CSP
Sum of squares lower bounds for refuting any CSP Open
Let $P:\{0,1\}^k \to \{0,1\}$ be a nontrivial $k$-ary predicate. Consider a random instance of the constraint satisfaction problem $\mathrm{CSP}(P)$ on $n$ variables with $Δn$ constraints, each being $P$ applied to $k$ randomly chosen lite…
View article: Better Protocol for XOR Game using Communication Protocol and Nonlocal Boxes
Better Protocol for XOR Game using Communication Protocol and Nonlocal Boxes Open
Buhrman showed that an efficient communication protocol implies a reliable XOR game protocol. This idea rederives Linial and Shraibman's lower bounds of communication complexity, which was derived by using factorization norms, with worse c…
View article: Better Protocol for XOR Game using Communication Protocol.
Better Protocol for XOR Game using Communication Protocol. Open
Bri\et et al. showed that an efficient communication protocol implies a reliable XOR game protocol. In this work, we improve this relationship, and obtain a nontrivial lower bound $2\log3\approx 3.1699$ of XOR-amortized communication compl…
View article: Three-input majority function as the unique optimal function for the bias amplification using nonlocal boxes
Three-input majority function as the unique optimal function for the bias amplification using nonlocal boxes Open
Brassard et al. [Phys. Rev. Lett. 96, 250401 (2006)] showed that shared\nnonlocal boxes with the CHSH probability greater than $\\frac{3+\\sqrt{6}}6$\nyields trivial communication complexity. There still exists the gap with the\nmaximum CH…
View article: Lower bounds for CSP refutation by SDP hierarchies
Lower bounds for CSP refutation by SDP hierarchies Open
For a $k$-ary predicate $P$, a random instance of CSP$(P)$ with $n$ variables and $m$ constraints is unsatisfiable with high probability when $m \gg n$. The natural algorithmic task in this regime is \emph{refutation}: finding a proof that…
View article: Average Shortest Path Length of Graphs of Diameter 3
Average Shortest Path Length of Graphs of Diameter 3 Open
A network topology with low average shortest path length (ASPL) provides efficient data transmission while the number of nodes and the number of links incident to each node are often limited due to physical constraints. In this paper, we c…
View article: Lower Bounds for CSP Refutation by SDP Hierarchies
Lower Bounds for CSP Refutation by SDP Hierarchies Open
For a k-ary predicate P, a random instance of CSP(P) with n variables and m constraints is unsatisfiable with high probability when m >= O(n). The natural algorithmic task in this regime is refutation: finding a proof that a given random i…
View article: Peeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges
Peeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges Open
When we try to solve a system of linear equations, we can consider a simple iterative algorithm in which an equation including only one variable is chosen at each step, and the variable is fixed to the value satisfying the equation. The dy…
View article: Holographic Transformation, Belief Propagation and Loop Calculus for Generalized Probabilistic Theories
Holographic Transformation, Belief Propagation and Loop Calculus for Generalized Probabilistic Theories Open
The holographic transformation, belief propagation and loop calculus are generalized to problems in generalized probabilistic theories including quantum mechanics. In this work, the partition function of classical factor graph is represent…
View article: Holographic Transformation, Belief Propagation and Loop Calculus for Quantum Information Science.
Holographic Transformation, Belief Propagation and Loop Calculus for Quantum Information Science. Open
The holographic transformation, belief propagation and loop calculus are generalized to problems in generalized probabilistic theories including quantum mechanics. In this work, the partition function of classical factor graph is represent…