JHJohn P. Hayes

John P. Hayes

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


John P. Hayes has a total of 11 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Testing Logic Circuits for Probabilistic Faults

    by Smita Krishnaswamy, Igor L. Markov, John P. Hayes

  • Robust Coupling Delay Test Sets

    by Joonhwan Yi, John P. Hayes

  • Recovery from Transition Errors in Sequential Circuits

    by Ramashis Das, John P. Hayes

    We consider the impact of one-cycle transient faults on the state behavior of sequential circuits. The resultant errors are broadly classified into non-critical output errors and critical (state) transition errors. We also study the time required for recovery (self-healing) from transition errors under random input sequences, and present some experimental data for benchmark circuits.


  • Open Access

    Checking Equivalence of Quantum Circuits and States

    by George F. Viamontes, Igor L. Markov, John P. Hayes

    Quantum computing promises exponential speed-ups for important simulation and optimization problems. It also poses new CAD problems that are similar to, but more challenging, than the related problems in classical (non-quantum) CAD, such as determining if two states or circuits are functionally equivalent. While differences in classical states are easy to detect, quantum states, which are represented by complex-valued vectors, exhibit subtle differences leading to several notions of equivalence. This provides flexibility in optimizing quantum circuits, but leads to difficult new equivalence-checking issues for simulation and synthesis. We identify several different equivalence-checking problems and present algorithms for practical benchmarks, including quantum communication and search circuits, which are shown to be very fast and robust for hundreds of qubits.

  • Open Access

    Is Quantum Search Practical?

    by George F. Viamontes, Igor L. Markov, John P. Hayes

    Quantum algorithms and circuits can, in principle, outperform the best non-quantum (classical) techniques for some hard computational problems. However, this does not necessarily lead to useful applications. To gauge the practical significance of a quantum algorithm, one must weigh it against the best conventional techniques applied to useful instances of the same problem. Grover's quantum search algorithm is one of the most widely studied. We identify requirements for Grover's algorithm to be useful in practice: (1) a search application S where classical methods do not provide sufficient scalability; (2) an instantiation of Grover's algorithm Q(S) for S that has a smaller asymptotic worst-case runtime than any classical algorithm C(S) for S; (3) Q(S) with smaller actual runtime for practical instances of S than that of any C(S). We show that several commonly-suggested applications fail to satisfy these requirements, and outline directions for future work on quantum search.

  • Open Access

    Improving Gate-Level Simulation of Quantum Circuits

    by George F. Viamontes, Igor L. Markov, John P. Hayes

    Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and the vectors modeling qubit states grow exponentially with an increase in the number of qubits. However, by using a novel data structure called the Quantum Information Decision Diagram (QuIDD) that exploits the structure of quantum operators, a useful subset of operator matrices and state vectors can be represented in a form that grows polynomially with the number of qubits. This subset contains, but is not limited to, any equal superposition of n qubits, any computational basis state, n-qubit Pauli matrices, and n-qubit Hadamard matrices. It does not, however, contain the discrete Fourier transform (employed in Shor's algorithm) and some oracles used in Grover's algorithm. We first introduce and motivate decision diagrams and QuIDDs. We then analyze the runtime and memory complexity of QuIDD operations. Finally, we empirically validate QuIDD-based simulation by means of a general-purpose quantum computing simulator QuIDDPro implemented in C++. We simulate various instances of Grover's algorithm with QuIDDPro, and the results demonstrate that QuIDDs asymptotically outperform all other known simulation techniques. Our simulations also show that well-known worst-case instances of classical searching can be circumvented in many specific cases by data compression techniques.

  • Improving Gate-Level Simulation of Quantum Circuits

    by George F. Viamontes, Igor L. Markov, John P. Hayes


  • Open Access

    Efficient Synthesis of Linear Reversible Circuits

    by K. N. Patel, I. L. Markov, J. P. Hayes

    In this paper we consider circuit synthesis for n-wire linear reversible circuits using the C-NOT gate library. These circuits are an important class of reversible circuits with applications to quantum computation. Previous algorithms, based on Gaussian elimination and LU-decomposition, yield circuits with O(n^2) gates in the worst-case. However, an information theoretic bound suggests that it may be possible to reduce this to as few as O(n^2/log n) gates. We present an algorithm that is optimal up to a multiplicative constant, as well as Theta(log n) times faster than previous methods. While our results are primarily asymptotic, simulation results show that even for relatively small n our algorithm is faster and yields more efficient circuits than the standard method. Generically our algorithm can be interpreted as a matrix decomposition algorithm, yielding an asymptotically efficient decomposition of a binary matrix into a product of elementary matrices.


  • Open Access

    Gate-Level Simulation of Quantum Circuits

    by George F. Viamontes, Manoj Rajagopalan, Igor L. Markov, John P. Hayes

    While thousands of experimental physicists and chemists are currently trying to build scalable quantum computers, it appears that simulation of quantum computation will be at least as critical as circuit simulation in classical VLSI design. However, since the work of Richard Feynman in the early 1980s little progress was made in practical quantum simulation. Most researchers focused on polynomial-time simulation of restricted types of quantum circuits that fall short of the full power of quantum computation. Simulating quantum computing devices and useful quantum algorithms on classical hardware now requires excessive computational resources, making many important simulation tasks infeasible. In this work we propose a new technique for gate-level simulation of quantum circuits which greatly reduces the difficulty and cost of such simulations. The proposed technique is implemented in a simulation tool called the Quantum Information Decision Diagram (QuIDD) and evaluated by simulating Grover's quantum search algorithm. The back-end of our package, QuIDD Pro, is based on Binary Decision Diagrams, well-known for their ability to efficiently represent many seemingly intractable combinatorial structures. This reliance on a well-established area of research allows us to take advantage of existing software for BDD manipulation and achieve unparalleled empirical results for quantum simulation.