John P. Hayes
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
John P. Hayes has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Igor L. Markov
Department of EECS University of Michigan 48109-2121 Ann Arbor MI
7 shared publications - George F. Viamontes
Advanced Computer Architecture Laboratory Ann Arbor The University of Michigan 48109-2122 MI USA
4 shared publications - Brian T. Murray
Delphi Automotive Systems
1 shared publication - George F. Viamontes
Department of EECS Lockheed Martin Advanced Technology Laboratories University of Michigan Cherry Hill 08002 48109-2121 Ann Arbor NJ MI
1 shared publication - Joonhwan Yi
Department of Computer Engineering, Kwangwoon University, Seoul 01897, Korea
1 shared publication - Joonhwan Yi
Samsung Electronics Corporation
1 shared publication
Latest Publications
- 22 September 2012
- Published by Springer Nature
- p. 53-61
Testing Logic Circuits for Probabilistic Faults
- 22 September 2012
- Published by Springer Nature
- p. 53-61
Testing Logic Circuits for Probabilistic Faults
- 13 April 2012
- Published by Springer Nature in Journal of Electronic Testing
- Vol. 28 (3) , 375-388
Robust Coupling Delay Test Sets
- 13 April 2012
- Published by Springer Nature in Journal of Electronic Testing
- Vol. 28 (3) , 375-388
Robust Coupling Delay Test Sets
- 1 December 2007
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21620601,p. 105-110
Recovery from Transition Errors in Sequential Circuits
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.
- 1 December 2007
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21620601,p. 105-110
Recovery from Transition Errors in Sequential Circuits
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
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 AccessChecking Equivalence of Quantum Circuits and States
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.
- 1 December 2005
- Published by Springer Nature in Journal of Electronic Testing
- Vol. 21 (6) , 631-649
The Coupling Model for Function and Delay Faults
- 1 December 2005
- Published by Springer Nature in Journal of Electronic Testing
- Vol. 21 (6) , 631-649
The Coupling Model for Function and Delay Faults
- Open Access
Is Quantum Search Practical?
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 AccessIs Quantum Search Practical?
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
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.
Open AccessImproving Gate-Level Simulation of Quantum Circuits
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.
- 1 October 2003
- Published by Springer Nature in Quantum Information Processing
- Vol. 2 (5) , 347-380
Improving Gate-Level Simulation of Quantum Circuits
- 1 October 2003
- Published by Springer Nature in Quantum Information Processing
- Vol. 2 (5) , 347-380
Improving Gate-Level Simulation of Quantum Circuits
- Open Access
Efficient Synthesis of Linear Reversible Circuits
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 AccessEfficient Synthesis of Linear Reversible Circuits
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
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.
Open AccessGate-Level Simulation of Quantum Circuits
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.