Abstract In this paper, we introduce classically time-controlled quantum automata or classically time-controlled quantum automaton (CTQA), which is a reasonable modification of Moore–Crutchfield quantum finite automata that uses time-dependent evolution and a ‘scheduler’ defining how long each Hamiltonian will run. Surprisingly enough, time-dependent evolution provides a significant change in the computational power of quantum automata with respect to a discrete quantum model. Indeed, we show that if a scheduler is not computationally restricted, then a CTQA could even decide the Halting problem. In order to unearth the computational capabilities of CTQAs, we study the case of a computationally restricted scheduler. In particular, we showed that depending on the type of restriction imposed on the scheduler, a CTQA can (i) recognize non-regular languages with cut-point, even in the presence of Karp–Lipton advice, and (ii) recognize non-regular promise languages with bounded-error. Furthermore, we study the cutpoint-union of cutpoint languages by introducing a new model of Moore–Crutchfield quantum finite automata with a rotating tape head. CTQA presents itself as a new model of computation that provides a different approach to a formal study of ‘classical control, quantum data’ schemes in quantum computing.

A tromino tiling problem is a packing puzzle where we are given a region of connected lattice squares and we want to decide whether there exists a tiling of the region using trominoes with the shape of an L. In this work we study a slight variation of the tromino tiling problem where some positions of the region have pegs and each tromino comes with a hole that can only be placed on top of the pegs. We present a characterization of this tiling problem with pegs using flow networks and show that (i) there exists a linear-time parsimonious reduction to the maximum-flow problem, and (ii) counting the number of such tilings can be done in linear-time. The proofs of both results contain algorithms that can then be used to decide the tiling of a region with pegs in O(n) time.

Quantum Computing is a field of study in computer science based on the laws of quantum physics.Quantum computing is an attractive subject considering that quantum algorithms proved to be more efficient than classical algorithms and the advent of large-scale quantum computation.In particular, Grover's search algorithm is a quantum algorithm that is asymptotically faster than any classical search algorithm and it is relevant for the design of fast optimization algorithms.This article proposes two algorithms based on Grover's adaptative search for biobjective optimization problems where access to the objective functions is given via two different quantum oracles.The proposed algorithms, considering both types of oracles, are compared against NSGA-II, a highly cited multiobjective optimization evolutionary algorithm.Experimental evidence suggests that the quantum optimization methods proposed in this work are at least as effective as NSGA-II in average, considering an equal number of executions.Experimental results showed which oracle required less iterations for similar effectiveness.