Time/Space Trade-Offs for Reversible Computation
Abstract
A reversible Turing machine is one whose transition function is $1:1$, so that no instantaneous description (ID) has more than one predecessor. Using a pebbling argument, this paper shows that, for any $\varepsilon > 0$, ordinary multitape Turing machines using time T and space S can be simulated by reversible ones using time $O(T^{1 + \varepsilon } )$ and space $O(S\log T)$ or in linear time and space $O(ST^\varepsilon )$. The former result implies in particular that reversible machines can simulate ordinary ones in quadratic space. These results refer to reversible machines that save their input, thereby insuring a global $1:1$ relation between initial and final IDs, even when the function being computed is many-to-one. Reversible machines that instead erase their input can of course compute only $1:1$ partial recursive functions and indeed provide a Godel numbering of such functions. The time/space cost of computing a $1:1$ function on such a machine is equal within a small polynomial to the cost of computing the function and its inverse on an ordinary Turing machine.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Cites
Theory of Self-Reproducing Automata
Schwartz, J. T., von Neumann, J., & Burks, A. W. (1967) · Mathematics of Computation · doi:10.2307/2005041 · Cited by 5,468 · see citing works
Irreversibility and heat generation in the computing process
Landauer, R. (1961) · IBM Journal of Research and Development · doi:10.1147/rd.53.0183 · Cited by 4,980 · see citing works
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679 · see citing works
Self-citationIrreversibility and heat generation in the computing process
Landauer, R. W. (2000) · IBM Journal of Research and Development · doi:10.1147/rd.441.0261 · Cited by 2,617 · see citing works
The thermodynamics of computation—a review
Bennett, C. H. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02084158 · Cited by 2,006 · see citing works
Self-citationFredkin, E., & Toffoli, T. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf01857727 · Cited by 1,896 · see citing works
Physics-like models of computation
Margolus, N. (1984) · Physica D Nonlinear Phenomena · doi:10.1016/0167-2789(84)90252-5 · Cited by 411 · see citing works
Randomness conservation inequalities; information and independence in mathematical theories
Levin, L. A. (1984) · Information and Control · doi:10.1016/s0019-9958(84)80060-1 · Cited by 246 · see citing works
Computation and construction universality of reversible cellular automata
Toffoli, T. (1977) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(77)80007-x · Cited by 210 · see citing works
The Inversion of Functions Defined by Turing Machines
McCarthy, J. (1956) · Princeton University Press eBooks · doi:10.1515/9781400882618-009 · Cited by 116 · see citing works
Generators for Certain Alternating Groups with Applications to Cryptography
Coppersmith, D., & Grossman, E. (1975) · SIAM Journal on Applied Mathematics · doi:10.1137/0129051 · Cited by 73 · see citing works
ON A SIMPLE COMBINATORIAL STRUCTURE SUFFICIENT FOR SYBLYING NONTRIVIAL SELF-REPRODUCTION
Priese, L. (1976) · Journal of Cybernetics · doi:10.1080/01969727608927527 · Cited by 25 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472 · see citing works
Elementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311 · see citing works
Self-citationPolynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904 · see citing works
Bernstein, E., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300921 · Cited by 1,503 · see citing works
Quantum computation and Shor's factoring algorithm
Ekert, A., & Jozsa, R. (1996) · Reviews of Modern Physics · doi:10.1103/revmodphys.68.733 · Cited by 1,354 · see citing works
Bernstein, E., & Vazirani, U. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167097 · Cited by 1,284 · see citing works
Quantum Algorithms for Quantum Chemistry and Quantum Materials Science
Bauer, B., Bravyi, S., Motta, M., & Chan, G. K.-L. (2020) · Chemical Reviews · doi:10.1021/acs.chemrev.9b00829 · Cited by 848 · see citing works
Quantum networks for elementary arithmetic operations
Vedral, V., Barenco, A., & EKERT, A. K. (1996) · Physical Review A · doi:10.1103/physreva.54.147 · Cited by 799 · see citing works
Quantum Computers Can Search Rapidly by Using Almost Any Transformation
Grover, L. K. (1998) · Physical Review Letters · doi:10.1103/physrevlett.80.4329 · Cited by 608 · see citing works
Low-power digital systems based on adiabatic-switching principles
Athas, W. C., Svensson, L. J., Koller, J. G., Tzartzanis, N., & Chou, E. Y. (1994) · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · doi:10.1109/92.335009 · Cited by 583 · see citing works
Bennett, C. H., Gács, P., Li, M., Vitanyi, P. M. B., & Zurek, W. H. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.681318 · Cited by 511 · see citing works
Self-citationNotes on Landauer's principle, reversible computation, and Maxwell's Demon
Bennett, C. H. (2003) · Studies in History and Philosophy of Science Part B Studies in History and Philosophy of Modern Physics · doi:10.1016/s1355-2198(03)00039-x · Cited by 493 · see citing works
Self-citationQuantum Computers Can Search Arbitrarily Large Databases by a Single Query
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.4709 · Cited by 432 · see citing works
Grand Unification of Quantum Algorithms
Martyn, J. M., Rossi, Z. M., Tan, A. K., & Chuang, I. L. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.040203 · Cited by 377 · see citing works
Thermodynamic cost of computation, algorithmic complexity and the information metric
Zurek, W. H. (1989) · Nature · doi:10.1038/341119a0 · Cited by 272 · see citing works
Efficient networks for quantum factoring
Beckman, D., Chari, A. N., Devabhaktuni, S., & Preskill, J. (1996) · Physical Review A · doi:10.1103/physreva.54.1034 · Cited by 268 · see citing works
Quantum Computer Systems for Scientific Discovery
Alexeev, Y., Bacon, D., Brown, K. R., Calderbank, R., Carr, L. D., Chong, F. T., DeMarco, B., Englund, D. R., Farhi, E., Fefferman, B., et al. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.017001 · Cited by 311 · see citing works
A framework for fast quantum mechanical algorithms
Grover, L. K. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276712 · Cited by 236 · see citing works
Quantum Computer Systems for Scientific Discovery
Alexeev, Y., Bacon, D., Brown, K. R., Calderbank, R., Carr, L. D., Chong, F. T., DeMarco, B., Englund, D., Farhi, E., Fefferman, B., et al. (2021) · DSpace@MIT (Massachusetts Institute of Technology) · doi:10.6082/h7fqg-6vt65 · Cited by 257 · see citing works
Gupta, S., & Zia, R. K. P. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1769 · Cited by 196 · see citing works
Reversible electronic logic using switches
Merkle, R. C. (1993) · Nanotechnology · doi:10.1088/0957-4484/4/1/002 · Cited by 178 · see citing works
Introduction to reversible computing
Frank, M. P. (2005) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/1062261.1062324 · Cited by 161 · see citing works
The stochastic thermodynamics of computation
Wolpert, D. H. (2019) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/ab0850 · Cited by 157 · see citing works
Vedral, V., & Plenio, M. B. (1998) · Progress in Quantum Electronics · doi:10.1016/s0079-6727(98)00004-4 · Cited by 154 · see citing works
Two types of mechanical reversible logic
Merkle, R. C. (1993) · Nanotechnology · doi:10.1088/0957-4484/4/2/007 · Cited by 139 · see citing works
Reversible computing and cellular automata—A survey
Morita, K. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.01.041 · Cited by 138 · see citing works
Principles of a reversible programming language
Yokoyama, T., Axelsen, H. B., & Glück, R. (2008) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/1366230.1366239 · Cited by 128 · see citing works
Estimating the Cost of Generic Quantum Pre-image Attacks on SHA-2 and SHA-3
Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., & Schanck, J. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-69453-5_18 · Cited by 128 · see citing works
Barenco, A. (1996) · Contemporary Physics · doi:10.1080/00107519608217543 · Cited by 121 · see citing works
Efficient Turing-Universal Computation with DNA Polymers
Qian, L., Soloveichik, D., & Winfree, E. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-18305-8_12 · Cited by 115 · see citing works
Reversible Space Equals Deterministic Space
Lange, K.-J., McKenzie, P., & Tapp, A. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1672 · Cited by 115 · see citing works
Quantum Security Analysis of CSIDH
Bonnetain, X., & Schrottenloher, A. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-45724-2_17 · Cited by 110 · see citing works
Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”
Flake, G. W., & Baum, E. B. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00173-6 · Cited by 109 · see citing works
Aharonov, D. (1999) · WORLD SCIENTIFIC eBooks · doi:10.1142/9789812815569_0007 · Cited by 113 · see citing works
Quantum Physics and ComputersPreprint
Barenco, A. (1996) · Cited by 100 · see citing works
On the Cryptographic Hardness of Finding a Nash Equilibrium
Bitansky, N., Paneth, O., & Rosen, A. (2015) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.94 · Cited by 96 · see citing works
The EPFL Logic Synthesis LibrariesPreprint
Soeken, M., Riener, H., Haaswijk, W., Testa, E., Schmitt, B., Meuli, G., Mozafari, F., Lee, S.-Y., Calvino, A. T., Marakkalage, D. S., et al. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.05121 · Cited by 91 · see citing works
Continuous Verifiable Delay Functions
Ephraim, N., Freitag, C., Komargodski, I., & Pass, R. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-45727-3_5 · Cited by 87 · see citing works
High Parallel Complexity Graphs and Memory-Hard Functions
Alwen, J., & Serbinenko, V. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746622 · Cited by 84 · see citing works
One complexity theorist's view of quantum computing
Fortnow, L. (2003) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00377-2 · Cited by 77 · see citing works
LESS is More: Code-Based Signatures Without Syndromes
Biasse, J., Micheli, G., Persichetti, E., & Santini, P. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-51938-4_3 · Cited by 79 · see citing works
Improved Quantum Circuits for Elliptic Curve Discrete Logarithms
Häner, T., Jaques, S., Naehrig, M., Roetteler, M., & Soeken, M. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-44223-1_23 · Cited by 76 · see citing works
A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
Levine, R. Y., & Sherman, A. T. (1990) · SIAM Journal on Computing · doi:10.1137/0219046 · Cited by 71 · see citing works
Common Knowledge and Update in Finite Environments
van der Meyden, R. (1998) · Information and Computation · doi:10.1006/inco.1997.2679 · Cited by 71 · see citing works
The thermodynamic efficiency of computations made in cells across the range of life
Kempes, C. P., Wolpert, D., Cohen, Z., & Pérez-Mercader, J. (2017) · Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rsta.2016.0343 · Cited by 68 · see citing works
Factoring in a dissipative quantum computer
Miquel, C., Paz, J. P., & Perazzo, R. P. J. (1996) · Physical Review A · doi:10.1103/physreva.54.2605 · Cited by 67 · see citing works
Hanson, R. (2016) · doi:10.1093/oso/9780198754626.001.0001 · Cited by 66 · see citing works
Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks
Boneh, D., Corrigan-Gibbs, H., & Schechter, S. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53887-6_8 · Cited by 64 · see citing works
Williams, C. P. (2010) · Texts in computer science · doi:10.1007/978-1-84628-887-6_2 · Cited by 61 · see citing works
A Survey of Continuous-Time Computation Theory
Orponen, P. (1997) · Springer eBooks · doi:10.1007/978-1-4613-3394-4_11 · Cited by 61 · see citing works
Reversibility and adiabatic computation: trading time and space for energy
Li, M., & Vitanyi, P. M. B. (1996) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.1996.0039 · Cited by 64 · see citing works
Space-Bounded Quantum Complexity
Watrous, J. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1655 · Cited by 59 · see citing works
The Structure of Complete Degrees
Kurtz, S. A., Mahaney, S. R., & Royer, J. S. (1990) · Springer eBooks · doi:10.1007/978-1-4612-4478-3_7 · Cited by 56 · see citing works
Optimizing Quantum Circuits for ArithmeticPreprint
Häner, T., Roetteler, M., & Svore, K. M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.12445 · Cited by 84 · see citing works
Quantum algorithms and circuits for scientific computing
Bhaskar, M. K., Hadfield, S., Papageorgiou, A., & Petras, I. (2016) · Quantum Information and Computation · doi:10.26421/qic16.3-4-2 · Cited by 55 · see citing works
Breaking the Sub-Exponential Barrier in Obfustopia
Garg, S., Pandey, O., Srinivasan, A., & Zhandry, M. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-56617-7_6 · Cited by 52 · see citing works
An Electroid Switching Model For Reversible Computer Architectures
Hall, J. S. (2005) · Workshop on Physics and Computation (PhysComp) · doi:10.1109/phycmp.1992.615549 · Cited by 52 · see citing works
Signal entropy and the thermodynamics of computation
Gershenfeld, N. (1996) · IBM Systems Journal · doi:10.1147/sj.353.0577 · Cited by 51 · see citing works
Counting, fanout and the complexity of quantum ACC
Green, F., Homer, S., Moore, C., & Pollett, C. (2002) · Quantum Information and Computation · doi:10.26421/qic2.1-3 · Cited by 51 · see citing works
Schumacher’s quantum data compression as a quantum computation
Cleve, R., & Divincenzo, D. P. (1996) · Physical Review A · doi:10.1103/physreva.54.2636 · Cited by 49 · see citing works
Time, space, and energy in reversible computing
Vitanyi, P. M. B. (2005) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/1062261.1062335 · Cited by 50 · see citing works
NREVERSAL of fortune — The thermodynamics of garbage collection
Baker, H. G. (2005) · Springer eBooks · doi:10.1007/bfb0017210 · Cited by 48 · see citing works
Time and Space Bounds for Reversible Simulation
Buhrman, H., Tromp, J., & Vitanyi, P. M. B. (2001) · Lecture notes in computer science · doi:10.1007/3-540-48224-5_82 · Cited by 49 · see citing works
Fundamentals of reversible flowchart languages
Yokoyama, T., Axelsen, H. B., & Glück, R. (2015) · Theoretical Computer Science · doi:10.1016/j.tcs.2015.07.046 · Cited by 48 · see citing works
Classically verifiable quantum advantage from a computational Bell test
Kahanamoku–Meyer, G. D., Choi, S., Vazirani, U. V., & Yao, N. Y. (2022) · Nature Physics · doi:10.1038/s41567-022-01643-7 · Cited by 49 · see citing works
Verified Compilation of Space-Efficient Reversible Circuits
Amy, M., Rötteler, M., & Svore, K. (2016) · International Conference on Computer Aided Verification · doi:10.1007/978-3-319-63390-9_1 · Cited by 54 · see citing works
Concrete quantum cryptanalysis of binary elliptic curves
Banegas, G., Bernstein, D. J., van Hoof, I., & Lange, T. (2020) · IACR Transactions on Cryptographic Hardware and Embedded Systems · doi:10.46586/tches.v2021.i1.451-472 · Cited by 48 · see citing works
Computability and complexity of ray tracing
Reif, J. H., Tygar, J. D., & Yoshida, A. (1994) · Discrete & Computational Geometry · doi:10.1007/bf02574009 · Cited by 47 · see citing works
Reversible simulation of irreversible computation
Li, M., Tromp, J., & Vitanyi, P. M. B. (1998) · Physica D Nonlinear Phenomena · doi:10.1016/s0167-2789(98)00052-9 · Cited by 46 · see citing works
Adaptively Secure Proxy Re-encryption
Fuchsbauer, G., Kamath, C., Klein, K., & Pietrzak, K. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-17259-6_11 · Cited by 43 · see citing works
Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
Choudhuri, A. R., Hubáček, P., Kamath, C., Pietrzak, K., Rosen, A., & Rothblum, G. N. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316400 · Cited by 41 · see citing works
LUT-Based Hierarchical Reversible Logic Synthesis
Soeken, M., Roetteler, M., Wiebe, N., & Micheli, G. D. (2019) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2018.2859251 · Cited by 44 · see citing works
Logic Synthesis for Established and Emerging Computing
Testa, E., Soeken, M., Amar, L. G., & Micheli, G. D. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2869760 · Cited by 40 · see citing works
Ding, Y., Wu, X.-C., Holmes, A., Wiseth, A., Franklin, D., Martonosi, M., & Chong, F. T. (2020) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca45697.2020.00054 · Cited by 42 · see citing works
Quantum computing and quadratically signed weight enumerators
Knill, E. H., & Laflamme, R. (2001) · Information Processing Letters · doi:10.1016/s0020-0190(00)00222-2 · Cited by 43 · see citing works
Quantum convolutional error-correcting codes
Chau, H. F. (1998) · Physical Review A · doi:10.1103/physreva.58.905 · Cited by 40 · see citing works
Quantum circuit optimization with AlphaTensor
Ruiz, F. J. R., Laakkonen, T., Bausch, J., Balog, M., Barekatain, M., Heras, F. J. H., Novikov, A., Fitzpatrick, N., Romera‐Paredes, B., van de Wetering, J., et al. (2025) · Nature Machine Intelligence · doi:10.1038/s42256-025-01001-1 · Cited by 44 · see citing works
Reversible Flowchart Languages and the Structured Reversible Program Theorem
Yokoyama, T., Axelsen, H. B., & Glück, R. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70583-3_22 · Cited by 37 · see citing works
Partially Reversible Pipelined QCA Circuits: Combining Low Power With High Throughput
Ottavi, M. L., Pontarelli, S., DeBenedictis, E. P., Salsano, A., Frost, S. E., Kogge, P. M., & Lombardi, F. (2011) · IEEE Transactions on Nanotechnology · doi:10.1109/tnano.2011.2147796 · Cited by 36 · see citing works
Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
Gall, F. L., & Magniez, F. (2018) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/3212734.3212744 · Cited by 36 · see citing works
Reversible Pebbling Game for Quantum Memory Management
Meuli, G., Soeken, M., Roetteler, M., Bjørner, N., & Micheli, G. D. (2019) · Design, Automation, and Test in Europe · doi:10.23919/date.2019.8715092 · Cited by 37 · see citing works
Adiabatic Logic Circuits: A Review
Staroselskii, V. I. (2001) · Russian Microelectronics · doi:10.1023/a:1013857006906 · Cited by 36 · see citing works
Reversible Agents Need Robots Waste Bits To See, Talk, And Achieve?
Hanson, R. (2005) · Workshop on Physics and Computation (PhysComp) · doi:10.1109/phycmp.1992.615558 · Cited by 35 · see citing works
Demaine, E. D., Lynch, J., Mirano, G. J., & Tyagi, N. (2016) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2840728.2840756 · Cited by 35 · see citing works
PSPACE-complete problems for subgroups of free groups and inverse finite automata
Birget, J.-C., Margolis, S., Meakin, J. C., & Weil, P. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(98)00225-4 · Cited by 35 · see citing works
Probabilities to Accept Languages by Quantum Finite Automata
Ambainis, A., Bonner, R., Freivalds, R., & Ķikusts, A. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48686-0_17 · Cited by 35 · see citing works
Reversible computer engineering and architecture
Vieri, C. J., & Knight, T. F. (1999) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 36 · see citing works
Quantum Algorithms for Scientific Computing and Approximate OptimizationPreprint
Hadfield, S. (2018) · arXiv (Cornell University) · doi:10.7916/d8x650c9 · Cited by 63 · see citing works
Thermodynamic costs of Turing machines
Kolchinsky, A., & Wolpert, D. H. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.033312 · Cited by 35 · see citing works
Space and Time-Efficient Quantum Multiplier in Post Quantum Cryptography Era
Putranto, D. S. C., Wardhani, R. W., Larasati, H. T., & Kim, H. (2023) · IEEE Access · doi:10.1109/access.2023.3252504 · Cited by 34 · see citing works
Bio‐Inspired and Nanoscale Integrated Computing
Eshaghian‐Wilner, M. M., & service), W. I. (. (2009) · Wiley eBooks · doi:10.1002/9780470429983 · Cited by 34 · see citing works
Beyond Quadratic Speedups in Quantum Attacks on Symmetric Schemes
Bonnetain, X., Schrottenloher, A., & Sibleyras, F. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-07082-2_12 · Cited by 33 · see citing works
Merkle, R. C., & Drexler, K. E. (1996) · Nanotechnology · doi:10.1088/0957-4484/7/4/004 · Cited by 32 · see citing works
Ultimate theoretical models of nanocomputers
Frank, M. P., & Knight, T. F. (1998) · Nanotechnology · doi:10.1088/0957-4484/9/3/005 · Cited by 31 · see citing works
Quantum Circuits: Fanout, Parity, and CountingPreprint
Moore, C. (1999) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9903046 · Cited by 31 · see citing works
Reductions and functors from problems to word problems
Birget, J.-C. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(98)00131-5 · Cited by 30 · see citing works
Bounds on Monotone Switching Networks for Directed Connectivity
Potechin, A. H. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.58 · Cited by 30 · see citing works
Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement
Klein, K., Pascual-Perez, G., Walter, M., Kamath, C., Capretto, M., Noval, M. C., Markov, I., Yeo, M., Alwen, J., & Pietrzak, K. (2021) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp40001.2021.00035 · Cited by 30 · see citing works
Quantum-classical complexity-security tradeoff in secure multiparty computations
Chau, H. F. (2000) · Physical Review A · doi:10.1103/physreva.61.032308 · Cited by 30 · see citing works
Explicit Lower Bounds on Strong Quantum Simulation
Huang, C., Newman, M., & Szegedy, M. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.3004427 · Cited by 30 · see citing works
- Authors
- Bennett, C. H.
- Affiliations
- IBM Research - Thomas J. Watson Research Center (US)
- Corresponding author
- Bennett, Charles H.
- ORCID
- Bennett, Charles H.
- Venue
- SIAM Journal on Computing
- Published
- 1989-08
- Volume
- 18
- Issue
- 4
- Pages
- 766-776
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2061073612
- Cited by
- 405
- References
- 12
- Citations by year
- 2026: 11 · 2025: 20 · 2024: 13 · 2023: 10 · 2022: 18 · 2021: 24 · 2020: 26 · 2019: 15 · 2018: 21 · 2017: 16 · 2016: 43 · 2015: 14 · 2014: 5 · 2013: 6 · 2012: 6
- FWCI
- 2.52
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Computing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- reversible computation, reversible Turing machines, space-time tradeoff, pebbling, multitape Turing machines, one-to-one functions, partial recursive functions, inverse functions, space complexity, time complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
