Quantum Oracles and Computational Complexity (Algebraic Systems,Formal Languages and Computations)

Jozef Gruska, Roland Vollmar

Harumichi Nishimura, Masanao Ozawa

In this paper, we consider the following problem (the subroutine problem).If the operation performed by an oracle is efficiently computable, can a non-oracle quantum computer simulate a quantum computer with this oracle efficiently ?Bennett et al. and Aharonov et al. respectively solved the subroutine problem when their oracles evaluate deterministic and probabilistic functions.However, both of them considered only the case where machines enter the query mode deterministically.We extend the notion of an oracle of a quantum computer to a device for performing a unitary transformation, and solve the subroutine problem in the general setting where a query state and a nonquery state may superpose.Using this result, we show that EQP and BQP are robust in the general setting, which extends the robustness of BQP shown by Bennett et al. in the case where machines enter the query mode deterministically.Moreover, we prove the robustness of ZQP by improving.themethod of Bennett et al. employed for the above BQP result.

Marco O. Lanzagorta, Jeffrey K. Uhlmann

A. Yu. Volkov, G. A. Koroteev, Yu. S. Volkov

We introduce Quantum Index Algebra (QIA) as a finite, index-based algebraic framework for representing and manipulating quantum operators on Hilbert spaces of dimension $2^m$. In QIA, operators are expressed as structured combinations of basis elements indexed by Boolean codes, allowing products, commutators, and conjugations to be computed through finite rules on discrete indices rather than through dense matrix arithmetic. This representation unifies combinatorial index structure, explicit matrix realization, and transformation properties under Walsh-Hadamard-type transforms within a single formalism. Using QIA and its associated block-matrix realization, we reformulate the Bernstein-Vazirani hidden-string problem in its phase-oracle form entirely within a real, finite-dimensional algebraic setting. We show that, under structured oracle access, the QIA procedure reproduces the Bernstein-Vazirani algorithm exactly and achieves the same asymptotic query complexity and circuit depth as the standard quantum algorithm. In particular, the hidden string is recovered by symbolic manipulation of a sparse algebraic representation of the oracle rather than by numerical simulation of quantum amplitudes. Our results demonstrate that the apparent quantum speed-up in this setting is a consequence of operator structure rather than Hilbert-space dimensionality alone. QIA thus provides a precise language for separating genuinely quantum resources from those arising from algebraic and combinatorial structures and offers a new perspective on the classical simulability of structured quantum circuits.

Yiwei Li, Edison Tsai, Marek A. Perkowski +1 more

Functional decomposition plays a key role in several areas such as system design, digital circuits, database systems, and Machine Learning. This paper presents a novel quantum computing approach based on Grover’s search algorithm for a generalized Ashenhurst-Curtis decomposition. The method models the decomposition problem as a search problem and constructs the oracle circuit based on the set-theoretic partition algebra. A hybrid quantum-based algorithm takes advantage of the quadratic speedup achieved by Grover’s search algorithm with quantum oracles for finding the minimum-cost decomposition. The method is implemented and simulated in the quantum programming language Quipper. This work constitutes the first attempt to apply quantum computing to functional decomposition.

Christino Tamon, Tomoyuki Yamakami