Due to the decoherence of the state-of-the-art physical implementations of quantum computers, it is essential to parallelize the quantum circuits to reduce their depth. Two decades ago, Moore and Nilsson [1] demonstrated that additional qubits (or ancillae) could be used to design “shallow” parallel circuits for quantum operators. They proved that any n-qubit CNOT circuit could be parallelized to O(log n) depth, with O(n²) ancillae. However, the near-term quantum technologies can only support limited amount of qubits, making space-depth trade-off a fundamental research subject for quantum-circuit synthesis. In this work, we establish an asymptotically optimal space-depth trade-off for the design of CNOT circuits. We prove that for any m ≥ 0, any n-qubit CNOT circuit can be parallelized to depth, with m ancillae. We show that this bound is tight by a counting argument, and further show that even with arbitrary two-qubit quantum gates to approximate CNOT circuits, the depth lower bound still meets our construction, illustrating the robustness of our result. Our work improves upon two previous results, one by Moore and Nilsson [1] for O(log n)-depth quantum synthesis, and one by Patel, Markov, and Hayes [2] for m =0: for the former, we reduce the need for ancillae by a factor of log² n by showing that m = O(n² / log² n) additional qubits — which is asymptotically optimal — suffice to build O(log n)-depth, O(n² / log n)-size CNOT circuits; for the later, we reduce the depth by a factor of n to the asymptotically optimal bound . Our results can be directly extended to stabilizer circuits using an earlier result by Aaronson and Gottesman [3]. In addition, we provide relevant hardness evidence for synthesis optimization of CNOT circuits in term of both size and depth.

We consider algorithms with access to an unknown matrix M ε F ^n×d via matrix-vector products , namely, the algorithm chooses vectors v ¹ , ⃛ , v ^q , and observes Mv ¹ , ⃛ , Mv ^q . Here the v ⁱ can be randomized as well as chosen adaptively as a function of Mv ¹ , ⃛ , Mv ^i-1 . Motivated by applications of sketching in distributed computation, linear algebra, and streaming models, as well as connections to areas such as communication complexity and property testing, we initiate the study of the number q of queries needed to solve various fundamental problems. We study problems in three broad categories, including linear algebra, statistics problems, and graph problems. For example, we consider the number of queries required to approximate the rank, trace, maximum eigenvalue, and norms of a matrix M; to compute the AND/OR/Parity of each column or row of M, to decide whether there are identical columns or rows in M or whether M is symmetric, diagonal, or unitary; or to compute whether a graph defined by M is connected or triangle-free. We also show separations for algorithms that are allowed to obtain matrix-vector products only by querying vectors on the right, versus algorithms that can query vectors on both the left and the right. We also show separations depending on the underlying field the matrix-vector product occurs in. For graph problems, we show separations depending on the form of the matrix (bipartite adjacency versus signed edge-vertex incidence matrix) to represent the graph. Surprisingly, very few works discuss this fundamental model, and we believe a thorough investigation of problems in this model would be beneficial to a number of different application areas.

Since the core of talent training in modern society has changed from allowing students to master knowledge to adapting them to a lifelong learning society, this paper studied the innovation education in higher education by combining human comprehensive development theory and deep learning. First, this paper described the training needs of innovative education talents. Second, based on the human comprehensive development theory and deep learning, it puts forward views on innovative quality education in colleges and evaluates the students’ deep learning status by designing a deep learning evaluation model. From the perspective of students, a questionnaire for student-side use was designed according to the deep learning evaluation scale so that students could understand their deep learning status, make improvements based on their current situation, and improve the level of deep learning, thereby obtaining the inspiration of innovation education in higher education. The research shows that the students’ mastery of knowledge and skills is the highest, indicating that the mastery of students in this respect has reached the standard. Although the mean value obtained by the process and method is greater than the median, it is almost the same as the median, which indicates that the students’ mastery of the process and method is still lacking and further efforts are needed. In terms of psychology and values, the mean value is the lowest among the three dimensions and less than the median, indicating that students are the weakest in this respect and further improvement is required. In addition, a new teaching evaluation method was designed based on human comprehensive development theory and deep learning, contributing to innovation education in higher education in China.

In this paper, we study the local unitary (LU) classification for pairs (triples) of generalized Bell states, based on the local unitary equivalence of two sets. In detail, we first introduce some general unitary operators which give us more local unitary equivalent sets besides Clifford operators. And then we present two necessary conditions for local unitary equivalent sets which can be used to examine the local inequivalence. Following this approach, we completely classify all pairs in the $d\otimes d$ quantum system into ${\prod }_{j=1}^n(k_j+1)-1$ LU-inequivalent pairs when the prime factorization of $d={\prod }_{j=1}^n{p}_j^{k_j}$. Moreover, all triples in the $p^{\alpha }\otimes p^{\alpha }$ quantum system for prime $p$ can be partitioned into $\frac{(\alpha +3)}{6}{p}^{\alpha }+O\left(\alpha p^{\alpha -1}\right)$ LU-inequivalent triples; especially, when $\alpha =2$ and $p>2$, there are exactly $\lfloor \frac{5}{6}{p}^2\rfloor +\lfloor \frac{p-2}{6}+{(-1)}^{\lfloor \frac{p}{3}\rfloor }\frac{p}{3}\rfloor +3$ LU-inequivalent triples.

Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon T suffer from the regret of at least the square root of T. In this paper, we study MAB and SLB with quantum reward oracles and propose quantum algorithms for both models with the order of the polylog T regrets, exponentially improving the dependence in terms of T. To the best of our knowledge, this is the first provable quantum speedup for regrets of bandit problems and in general exploitation in reinforcement learning. Compared to previous literature on quantum exploration algorithms for MAB and reinforcement learning, our quantum input model is simpler and only assumes quantum oracles for each individual arm.

Given a coin with unknown bias $p\in [0,1]$, can we exactly simulate another coin with bias $f\left(p\right)$? The exact set of simulable functions has been well characterized 20 years ago. In this paper, we ask the quantum counterpart of this question: Given the quantum coin $|p\rangle =\sqrt{p}|0\rangle +\sqrt{1-p}|1\rangle$, can we exactly simulate another quantum coin $|f\left(p\right)\rangle =\sqrt{f\left(p\right)}|0\rangle +\sqrt{1-f\left(p\right)}|1\rangle$? We give the full characterization of simulable quantum state $k_0\left(p\right)|0\rangle +k_1\left(p\right)|1\rangle$ from quantum coin $|p\rangle =\sqrt{p}|0\rangle +\sqrt{1-p}|1\rangle$, and present an algorithm to transform it. Surprisingly, we show that simulable sets in the quantum-to-quantum case and classical-to-classical case have no inclusion relationship with each other.