Recently, the entanglement dynamics of two harmonic oscillators initially prepared in a separable-coherent state was demonstrated to offer a pathway for prime number identification. This article presents a generalized approach and outlines a deterministic algorithm making possible the implementation of this theoretical concept on scalable fault-tolerant qubit-based quantum computers. We prove that the diagonal unitary operations employed in our algorithm exhibit a polynomial-time complexity of degree two, contrasting with the previously reported exponential complexity of general diagonal unitaries.
Recently, the entanglement dynamics of two harmonic oscillators initially prepared in a separable-coherent state was demonstrated to offer a pathway for prime number identification. This article presents a generalized approach and outlines a deterministic algorithm making possible the implementation of this theoretical concept on scalable fault-tolerant qubit-based quantum computers. We prove that the diagonal unitary operations employed in our algorithm exhibit a polynomial-time complexity of degree two, contrasting with the previously reported exponential complexity of general diagonal unitaries.
The identification of prime numbers is an ancient area of study with applications in cryptography and fundamental mathematical problems, such as the Riemann Hypothesis (RH). Classical algorithms, like the Sieve of Eratosthenes and the AKS Primality Test, are efficient examples for this purpose. However, quantum computing (QC), with its superior theoretical capacity, has inspired the development of quantum algorithms, many of which are probabilistic or rely on the RH. In this dissertation, we propose a deterministic and efficient quantum algorithm that generalizes a recent method from quantum optics to identify prime numbers through entanglement dynamics. We adapted this method for QC, removing several constraints from the original work, and showed that discrete bipartite quantum systems prepared in certain initial states can be used to identify prime numbers through the Fourier modes of the reduced purity of one of the subsystems. The proposed algorithm is viable for implementation in future fault-tolerant QC systems. The initial steps involve encoding the system in qubits and preparing a maximally superposed state. In the state evolution step, we use Walsh matrices to efficiently prepare diagonal unitary gates. The reduced purity is measured using a modified controlled-SWAP test, and the Fourier modes are obtained via the numerical calculation of a one-dimensional integral. Subsequently, we present the simulations performed in Qiskit, which demonstrate the validity of the algorithm in all its stages. Finally, we discuss the computational cost, quantifying the number of elementary gates as a function of the number of qubits and speculating the total computational complexity of the algorithm.
A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 \times 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations, and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. In other words it is possible that quantum phenomena can be used in a scalable fashion to make computers but that they do not have superpolynomial speedups compared to Turing machines for any problem. The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent will one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.
The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this reduction has proved to be useful for studying SAT solvers, large integers have not been factored via such a reduction. Shor's quantum factoring algorithm factors integers in expected polynomial time. Large-scale fault-tolerant quantum computers capable of implementing Shor's algorithm are not yet available, preventing relevant benchmarking experiments. Recently, several authors have attempted quantum factorizations via reductions to SAT or similar NP-hard problems. While this approach may shed light on algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question its practicality. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware.
Quantum entanglement represents a fundamental resource for quantum information processing, yet the dynamics of multi-photon entangled systems remain inadequately characterized for practical quantum computing applications. This research investigates the generation, manipulation, and characterization of entangled states involving two to eight photons using spontaneous parametric down-conversion techniques. Through theoretical analysis and numerical simulations, we developed a comprehensive framework that quantifies entanglement fidelity, decoherence rates, and Bell inequality violations across various multi-photon configurations. Our findings reveal that entanglement fidelity decreases exponentially with increasing photon number, exhibiting a decay constant of 0.087±0.012 per additional qubit in optical systems. The research demonstrates significant variations in decoherence times across different physical implementations, with ion trap systems maintaining coherence 1.7 times longer than photonic platforms for equivalent qubit numbers. We established mathematical relationships between system parameters and entanglement quality metrics, identifying critical thresholds for fault-tolerant quantum gate operations. The theoretical framework incorporates realistic noise models, environmental coupling mechanisms, and measurement-induced perturbations that affect practical implementations. Our analysis indicates that five-photon entangled states maintain sufficient fidelity (>83.5%) for error-corrected quantum algorithms when decoherence times exceed 75 microseconds. These results provide essential guidelines for designing scalable quantum processors and establishing benchmarks for experimental validation of multi-qubit entanglement protocols.
Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree−d polynomial, using circuits with logarithmic depth in the number n of qubits and only O(n) ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only n terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state ∣1⟩. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using 14 qubits and more than 500 primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.
Abstract An important part of reaping computational advantage from a quantum computer is to reduce the quantum resources needed to implement a desired quantum algorithm. Quantum algorithms that are too large to be practical on noisy intermediate scale quantum devices will require fault-tolerant error correction. This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the T gate consumes vastly more resources than the other gates in the gate set. More specifically, in this paper we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford + T gate set. The Clifford + T gate set is a universal gate set and in this group, using state-of-the-art surface codes, the T gate is by far the most expensive component to implement fault-tolerantly. So it is important to minimize the number of T gates necessary for a fault-tolerant implementation. Our primary interest is to compute a circuit for a given n -qubit unitary U , using the minimum possible number of T gates (called the T-count of unitary U ). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of U . In its decision version the goal is to decide if the T-count is at most some positive integer m . Given an oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial in the T-count and dimension of U . We give a provable classical algorithm that solves COUNT-T (decision) in time O N 2 ( c − 1 ) ⌈ m c ⌉ p o l y ( m , N ) and space O N 2 ⌈ m c ⌉ p o l y ( m , N ) , where N = 2 n and c ⩾ 2. This gives a space-time trade-off for solving this problem with variants of meet-in-the-middle techniques. We also introduce an asymptotically faster multiplication method that shaves a factor of N 0.7457 off of the overall complexity. Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that outputs a T-count-optimal circuit and has space and time complexity poly( m , N ), under some assumptions. In our heuristic algorithm we developed a novel way of pruning the search space. While our heuristic method still scales exponentially with the number of qubits (though with a lower exponent), there is a large improvement by going from exponential to polynomial scaling with m . We implemented our heuristic algorithm with up to 4 qubit unitaries and obtained a significant improvement in time. For all benchmark and random unitaries we studied, the T-count returned by our algorithm is at most the T-count of their circuits shown in previous papers.