The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem of size n into smaller subproblems (say, a copies of size \(n/b\) each), along with some auxiliary work of cost \(C^{\mathrm{aux}}(n)\) , to give a recurrence relation \(\begin{equation*} C(n) \le a \, C(n/b) + C^{\mathrm{aux}}(n) \end{equation*}\) for the classical complexity \(C(n)\) . We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation \(\begin{equation*} C_Q(n) \le \sqrt {a} \, C_Q(n/b) + O(C^{\mathrm{aux}}_Q(n)) \end{equation*}\) that characterizes the quantum query complexity. We apply this framework to obtain near-optimal quantum query complexities for various string problems, such as (i) recognizing the regular language \(\Sigma ^* 2 0^* 2 \Sigma ^*\) over the alphabet \(\Sigma = \lbrace 0,1,2\rbrace\) ; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence.

The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH do not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, $$\rm{QCPH}$$ , uses classical proofs, and the second, $$\rm{QPH}$$ , uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, $$\rm{Q\Sigma_3}$$ , into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for $$\rm{QMA(2)}$$ , the variant of Quantum Merlin-Arthur ( $$\rm{QMA}$$ ) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if $$\rm{QCPH = QPH}$$ (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs ``equivalent''), then QMA(2) is in the counting hierarchy (specifically, in $${\rm P}^{{\rm pp}^{{\rm pp}}}$$ ). Second, because $$\rm{QMA(2)}\subseteq \rm{Q\Sigma_3}$$ , $$\rm{QMA(2)}$$ is strictly contained in NEXP unless $$\rm{QMA(2)}=\rm{Q\Sigma_3}$$ (i.e., alternating quantifiers do not help in the presence of ``unentanglement'').

SUMMARY Object detection from image is more challenging and integral part in the inter‐discipline area of computer vision. The computer vision is highly attractive in many applications like human pose estimation, instance segmentation, recognizing action, disease predictions object prediction and many more applications. The traditional method of detecting objects from the images is done using bounding boxes with labels. It suffers from the overlapping of the boxes with various smaller objects, which leads to accuracy issues in detection problems. Hence, machine learning techniques are used to detect the relevant objects from the image using center point to avoid the nonmaximal suppression in bounding box. To accurately identify images, an U‐Net architecture based object detection method is proposed. In this model, it effectively uses semantic level segmentation and instance segmentation. This system effectively identifies all the objects present in the given image using the efficient hybrid segmentation models and Gromov Hausdroff distance measure. For experimentation, two data sets are used for evaluation of the model to identify all categories of objects from the image. The proposed model achieves an accuracy of 91.8% and reliable when compared to existing effective object detection algorithms like fully convolution network (FCN), YOLO (you only look once) and mask region based‐convolutional neural network (mask R‐CNN) model.

We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let$\mathfrak{C}$be a class of polynomial-size concepts, and suppose that$\mathfrak{C}$can be PAC-learned with membership queries under the uniform distribution with error$1/2 -\gamma$by a time$T$quantum algorithm. We prove that if$\gamma^{2}\cdot T \ll 2^{n} /n$, then$\mathsf{BQE}\not\subset \mathfrak{C}$, where$\mathsf{BQE} = \mathsf{BQTIME}[2^{O(n)}]$is an exponential-time analogue of$\mathsf{BQP}$. This result is optimal in both$\gamma$and$T$, since it is not hard to learn any class$\mathfrak{C}$of functions in (classical) time$T=2^{n}$(with no error), or in quantum time$T= \mathsf{poly}(n)$with error at most$1/2-\Omega(2^{-n/2})$via Fourier sampling. In other words, even a marginal quantum speedup over these generic learning algorithms would lead to major consequences in complexity lower bounds. As a consequence, our result shows that the study of quantum learning speedups is intimately connected to fundamental open problems about algorithms, quantum computing, and complexity theory. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and on a connection between non-trivial classical learning algorithms and circuit lower bounds established by Oliveira and Santhanam (CCC 2017). Extending their approach to quantum learning algorithms turns out to create significant challenges, since extracting computational hardness from a quantum computation is inherently more complicated. To achieve that, we show among other results how pseudorandom generators imply learning-to-lower-bound connections in a generic fashion, construct the first conditional pseudorandom generator secure against uniform quantum computations, and extend the local list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP 2010) to quantum circuits via a delicate analysis. We believe that these contributions are of independent interest and might find other applications.

Reinforcement learning studies how an agent should interact with an environment to maximize its cumulative reward. A standard way to study this question abstractly is to ask how many samples an agent needs from the environment to learn an optimal policy for a $\gamma$-discounted Markov decision process (MDP). For such an MDP, we design quantum algorithms that approximate an optimal policy ($\pi^*$), the optimal value function ($v^*$), and the optimal $Q$-function ($q^*$), assuming the algorithms can access samples from the environment in quantum superposition. This assumption is justified whenever there exists a simulator for the environment; for example, if the environment is a video game or some other program. Our quantum algorithms, inspired by value iteration, achieve quadratic speedups over the best-possible classical sample complexities in the approximation accuracy ($\epsilon$) and two main parameters of the MDP: the effective time horizon ($\frac{1}{1-\gamma}$) and the size of the action space ($A$). Moreover, we show that our quantum algorithm for computing $q^*$ is optimal by proving a matching quantum lower bound.

In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of probably approximately correct (PAC) learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1. Hardness of PAC learning ${AC}^0$ and ${TC}^0$ under the uniform distribution. Our first result concerns the concept class ${TC}^0$ (resp., ${AC}^0$), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp., ${AND}, {OR}, {NOT}$ gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors (${RLWE}$) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for ${TC}^0$; and if there exists no $2^{O(d^{1/\eta})}$-time quantum algorithm to solve ${RLWE}$ with dimension $d = O(polylog n)$ (for every constant $\eta > 2$), then there exists no $O(n^{ \log^{\nu} n} )$-time quantum learning algorithm for $poly(n)$-sized ${AC}^0$ circuits (for a constant $\nu>0$), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607--620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning ${TC}^0_2$ in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the ${LWE}$ problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class ${TC}^0_2$, i.e., depth-2 ${TC}^0$ circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.

In 2013 Bei, Chen and Zhang introduced a trial and error model of computing, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if the assignment is not satisfying. In this paper we initiate a systematic study of constraint satisfaction problems in the trial and error model, by adopting a formal framework for CSPs, and defining several types of revealing oracles. Our main contribution is to develop a transfer theorem for each type of the revealing oracle. To any hidden CSP with a specific type of revealing oracle, the transfer theorem associates another CSP in the normal setting, such that their complexities are polynomial-time equivalent. This in principle transfers the study of a large class of hidden CSPs to the study of normal CSPs. We apply the transfer theorems to get polynomial-time algorithms or hardness results for several families of concrete problems.

A canonical result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors Q_{ij} on a system of n qubits, and the task is to decide whether the Hamiltonian H = sum Q_{ij} has a 0-eigenvalue, or it is larger than 1/n^c for some c = O(1). The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding the ground state of 2-local frustration-free Hamiltonians of spin 1/2, a well-studied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is O(n^4). In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.

What is the minimum amount of information and time needed to solve 2SAT? When the instance is known, it can be solved in polynomial time, but is this also possible without knowing the instance? Bei, Chen and Zhang (STOC'13) considered a model where the input is accessed by proposing possible assignments to a special oracle. This oracle, on encountering some constraint unsatisfied by the proposal, returns only the constraint index. It turns out that, in this model, even 1SAT cannot be solved in polynomial time unless P=NP. Hence, we consider a model in which the input is accessed by proposing probability distributions over assignments to the variables. The oracle then returns the index of the constraint that is most likely to be violated by this distribution. We show that the information obtained this way is sufficient to solve 1SAT in polynomial time, even when the clauses can be repeated. For 2SAT, as long as there are no repeated clauses, in polynomial time we can even learn an equivalent formula for the hidden instance and hence also solve it. Furthermore, we extend these results to the quantum regime. We show that in this setting 1QSAT can be solved in polynomial time up to constant precision, and 2QSAT can be learnt in polynomial time up to inverse polynomial precision.