×

zbMATH — the first resource for mathematics

Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results. (English) Zbl 07285766
Summary: Quantum annealers (QAs) are specialized quantum computers that minimize objective functions over discrete variables by physically exploiting quantum effects. Current QA platforms allow for the optimization of quadratic objectives defined over binary variables (qubits), also known as Ising problems. In the last decade, QA systems as implemented by D-Wave have scaled with Moore-like growth. Current architectures provide 2048 sparsely-connected qubits, and continued exponential growth is anticipated, together with increased connectivity.
We explore the feasibility of such architectures for solving SAT and MaxSAT problems as QA systems scale. We develop techniques for effectively encoding SAT -and, with some limitations, MaxSAT- into Ising problems compatible with sparse QA architectures. We provide the theoretical foundations for this mapping, and present encoding techniques that combine offline Satisfiability and Optimization Modulo Theories with on-the-fly placement and routing. Preliminary empirical tests on a current generation 2048-qubit D-Wave system support the feasibility of the approach for certain SAT and MaxSAT problems.
MSC:
68Q Theory of computing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Shor, P. W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26, 5, 1484-1509 (1997) · Zbl 1005.11065
[2] Grover, L. K., A fast quantum mechanical algorithm for database search, (Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96 (1996), ACM: ACM New York, NY, USA), 212-219 · Zbl 0922.68044
[3] Finnila, A.; Gomez, M.; Sebenik, C.; Stenson, C.; Doll, J., Quantum annealing: a new method for minimizing multidimensional functions, Chem. Phys. Lett., 219, 5, 343-348 (1994)
[4] Kadowaki, T.; Nishimori, H., Quantum annealing in the transverse Ising model, Phys. Rev. E, 58, 5355-5363 (1998)
[5] Farhi, E.; Goldstone, J.; Gutmann, S.; Sipser, M., Quantum computation by adiabatic evolution, arXiv preprint · Zbl 1187.81063
[6] Bunyk, P. I.; Hoskinson, E. M.; Johnson, M. W.; Tolkacheva, E.; Altomare, F.; Berkley, A. J.; Harris, R.; Hilton, J. P.; Lanting, T.; Przybysz, A. J.; Whittaker, J., Architectural considerations in the design of a superconducting quantum annealing processor, IEEE Trans. Appl. Supercond., 24, 4, 1-10 (2014)
[7] Selman, B.; Kautz, H.; Cohen, B., Local search strategies for satisfiability testing, (Cliques, Coloring, and Satisfiability. Cliques, Coloring, and Satisfiability, DIMACS, vol. 26 (1996)), 521-532 · Zbl 0864.90093
[8] Spears, W. M., Simulated annealing for hard satisfiability problems, (Cliques, Coloring, and Satisfiability. Cliques, Coloring, and Satisfiability, DIMACS, vol. 26 (1996), American Mathematical Society), 533-558 · Zbl 0864.90094
[9] Tompkins, D. A.D.; Hoos, H. H., UBCSAT: an implementation and experimentation environment for SLS algorithms for SAT and MAX-SAT, (Hoos, H.; Mitchell, D., Revised Selected Papers from the Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT 2004). Revised Selected Papers from the Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT 2004), Lecture Notes in Computer Science, vol. 3542 (2005), Springer: Springer Berlin, Heidelberg), 306-320 · Zbl 1122.68620
[10] Denchev, V. S.; Boixo, S.; Isakov, S. V.; Ding, N.; Babbush, R.; Smelyanskiy, V.; Martinis, J.; Neven, H., What is the computational value of finite-range tunneling?, Phys. Rev. X, 6, Article 031015 pp. (2016)
[11] King, J.; Yarkoni, S.; Raymond, J.; Ozfidan, I.; King, A. D.; Nevisi, M. M.; Hilton, J. P.; McGeoch, C. C., Quantum annealing amid local ruggedness and global frustration, arXiv preprint
[12] (Biere, A.; Heule, M. J.H.; van Maaren, H.; Walsh, T., Handbook of Satisfiability (2009), IOS Press)
[13] Li, C. M.; Manyà, F., MaxSAT, hard and soft constraints, (Biere, A.; Heule, M. J.H.; van Maaren, H.; Walsh, T., Handbook of Satisfiability (2009), IOS Press), 613-631, Ch. 19
[14] Massacci, F.; Marraro, L., Logical cryptanalysis as a sat problem, J. Autom. Reason., 24, 1, 165-203 (2000) · Zbl 0968.68052
[15] Mironov, I.; Zhang, L., Applications of SAT solvers to cryptanalysis of hash functions, (Biere, A.; Gomes, C. P., Theory and Applications of Satisfiability Testing - SAT 2006 (2006), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 102-115 · Zbl 1187.94028
[16] Lafitte, F.; Jr., J. N.; Heule, D. V., Applications of SAT solvers in cryptanalysis: finding weak keys and preimages, J. Satisf. Boolean Model. Comput. - JSAT, 9, 1, 1-25 (2013)
[17] Fréchette, A.; Newman, N.; Leyton-Brown, K., Solving the station repacking problem, (Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI’16 (2016), AAAI Press), 702-709
[18] Barrett, C. W.; Sebastiani, R.; Seshia, S. A.; Tinelli, C., Satisfiability modulo theories, (Biere, A.; Heule, M. J.H.; van Maaren, H.; Walsh, T., Handbook of Satisfiability (2009), IOS Press), 980
[19] Sebastiani, R.; Tomasi, S., Optimization modulo theories with linear rational costs, ACM Trans. Comput. Log., 16, 2, 12:1-12:43 (2015) · Zbl 1354.68233
[20] Sebastiani, R.; Trentin, P., OptiMathSAT: a tool for optimization modulo theories, J. Autom. Reason., 64, 423-460 (2020) · Zbl 07176604
[21] Bian, Z.; Chudak, F.; Macready, W.; Roy, A.; Sebastiani, R.; Varotti, S., Solving SAT and MaxSAT with a quantum annealer: foundations and a preliminary report, (Dixon, C.; Finger, M., Frontiers of Combining Systems (2017), Springer International Publishing: Springer International Publishing Cham), 153-171 · Zbl 06821632
[22] Harris, R.; Johansson, J.; Berkley, A. J.; Johnson, M. W.; Lanting, T.; Han, S.; Bunyk, P.; Ladizinsky, E.; Oh, T.; Perminov, I., Experimental demonstration of a robust and scalable flux qubit, Phys. Rev. B, 81, 13 (2010)
[23] Johnson, M. W.; Amin, M. H.S.; Gildert, S.; Lanting, T.; Hamze, F.; Dickson, N.; Harris, R.; Berkley, A. J.; Johansson, J.; Bunyk, P.; Chapple, E. M.; Enderud, C.; Hilton, J. P.; Karimi, K.; Ladizinsky, E.; Ladizinsky, N.; Oh, T.; Perminov, I.; Rich, C.; Thom, M. C.; Tolkacheva, E.; Truncik, C. J.S.; Uchaikin, S.; Wang, J.; Wilson, B.; Rose, G., Quantum annealing with manufactured spins, Nature, 473, 7346, 194-198 (2011)
[24] Lanting, T.; Harris, R.; Johansson, J.; Amin, M. H.S.; Berkley, A. J.; Gildert, S.; Johnson, M. W.; Bunyk, P.; Tolkacheva, E.; Ladizinsky, E.; Ladizinsky, N.; Oh, T.; Perminov, I.; Chapple, E. M.; Enderud, C.; Rich, C.; Wilson, B.; Thom, M. C.; Uchaikin, S.; Rose, G., Cotunneling in pairs of coupled flux qubits, Phys. Rev. B, 82, 6, Article 060512 pp. (2010)
[25] Amin, M. H., Searching for quantum speedup in quasistatic quantum annealers, Phys. Rev. A, 92, 5, Article 052323 pp. (2015)
[26] Amin, M. H.; Andriyash, E.; Rolfe, J.; Kulchytskyy, B.; Melko, R., Quantum Boltzmann machine, Phys. Rev. X, 8, Article 021050 pp. (2018)
[27] Raymond, J.; Yarkoni, S.; Andriyash, E., Global warming: temperature estimation in annealers, Front. ICT, 3, 23 (2016)
[28] Marques-Silva, J. P.; Lynce, I.; Malik, S., Conflict-driven clause learning SAT solvers, (Biere, A.; Heule, M. J.H.; van Maaren, H.; Walsh, T., Handbook of Satisfiability (2009), IOS Press), 131-153, Ch. 4
[29] Tseitin, G. S., On the Complexity of Derivation in Propositional Calculus, 466-483 (1983), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg
[30] Cook, S. A., The complexity of theorem proving procedures, (3rd Annual ACM Symposium on the Theory of Computation (1971)), 151-158
[31] Majercik, S. M., Stochastic Boolean satisfiability, (Biere, A.; Heule, M. J.H.; van Maaren, H.; Walsh, T., Handbook of Satisfiability (2009), IOS Press), 887-925, Ch. 27
[32] Cimatti, A.; Griggio, A.; Schaafsma, B. J.; Sebastiani, R., The MathSAT 5 SMT solver, (Tools and Algorithms for the Construction and Analysis of Systems, TACAS’13. Tools and Algorithms for the Construction and Analysis of Systems, TACAS’13, LNCS, vol. 7795 (2013), Springer), 95-109
[33] Sebastiani, R.; Trentin, P., Optimathsat: a tool for optimization modulo theories, (Kroening, D.; Păsăreanu, C. S., Computer Aided Verification (2015), Springer International Publishing: Springer International Publishing Cham), 447-454
[34] Bian, Z.; Chudak, F.; Israel, R.; Lackey, B.; Macready, W. G.; Roy, A., Discrete optimization using quantum annealing on sparse Ising models, Front. Phys., 2, 56 (2014)
[35] Correia, V. P.; Reis, A. I.; Porto, C.; Brasil, A. R., Classifying n-input Boolean functions, (Proc. IWS (2001), Citeseer)
[36] Huang, Z.; Wang, L.; Nasikovskiy, Y.; Mishchenko, A., Fast Boolean matching based on NPN classification, (2013 International Conference on Field-Programmable Technology (FPT) (2013)), 310-313
[37] Choi, V., Minor-embedding in adiabatic quantum computation: I. The parameter setting problem, Quantum Inf. Process., 7, 5, 193-209 (2008) · Zbl 1160.81326
[38] Choi, V., Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design, Quantum Inf. Process., 10, 3, 343-353 (2011) · Zbl 1216.81048
[39] Adler, I.; Dorn, F.; Fomin, F. V.; Sau, I.; Thilikos, D. M., Faster parameterized algorithms for minor containment, (Proceedings of the 12th Scandinavian Conference on Algorithm Theory, SWAT’10 (2010), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 322-333 · Zbl 1285.68206
[40] Boothby, T.; King, A. D.; Roy, A., Fast clique minor generation in Chimera qubit connectivity graphs, Quantum Inf. Process., 15, 1, 495-508 (2016) · Zbl 1333.81098
[41] Zaribafiyan, A.; Marchand, D. J.J.; Changiz Rezaei, S. S., Systematic and deterministic graph minor embedding for Cartesian products of graphs, Quantum Inf. Process., 16, 5, 136 (2017) · Zbl 1373.81160
[42] Cai, J.; Macready, W. G.; Roy, A., A practical heuristic for finding graph minors, arXiv preprint
[43] Dechter, R., Bucket Elimination: A Unifying Framework for Probabilistic Inference, 75-104 (1998), Springer Netherlands: Springer Netherlands Dordrecht · Zbl 0910.68209
[44] McKay, B. D.; Piperno, A., Practical graph isomorphism, II, J. Symb. Comput., 60, 94-112 (2014) · Zbl 1394.05079
[45] Bian, Z.; Chudak, F.; Israel, R. B.; Lackey, B.; Macready, W. G.; Roy, A., Mapping constrained optimization problems to quantum annealing with application to fault diagnosis, Front. ICT 2016
[46] Su, J.; Tu, T.; He, L., A quantum annealing approach for Boolean satisfiability problem, (2016 53rd ACM/EDAC/IEEE Design Automation Conference (DAC) (2016)), 1-6
[47] Mishchenko, A.; Chatterjee, S.; Brayton, R., Dag-aware AIG rewriting a fresh look at combinational logic synthesis, (Proceedings of the 43rd Annual Design Automation Conference, DAC ’06 (2006), ACM: ACM New York, NY, USA), 532-535
[48] Mishchenko, A.; Chatterjee, S.; Jiang, R.; Brayton, R. K., FRAIGs: a unifying representation for logic synthesis and verification (2005), Tech. rep., ERL Technical Report
[49] Een, N.; Mishchenko, A.; Sörensson, N., Applying logic synthesis for speeding up sat, (Marques-Silva, J.; Sakallah, K. A., Theory and Applications of Satisfiability Testing - SAT 2007 (2007), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 272-286 · Zbl 1214.68351
[50] Mishchenko, A.; Chatterjee, S.; Brayton, R.; Wang, X.; Kam, T., Technology mapping with Boolean matching, supergates and choices (2005)
[51] Betz, V.; Rose, J., VPR: a new packing, placement and routing tool for FPGA research, (International Workshop on Field Programmable Logic and Applications (1997), Springer), 213-222
[52] Kahng, A. B.; Lienig, J.; Markov, I. L.; Hu, J., VLSI Physical Design: From Graph Partitioning to Timing Closure (2011), Springer Netherlands: Springer Netherlands Dordrecht · Zbl 1213.68009
[53] Sun, W.-J.; Sechen, C., Efficient and effective placement for very large circuits, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 14, 3, 349-359 (1995)
[54] Chan, T. F.; Cong, J.; Kong, T.; Shinnerl, J. R., Multilevel optimization for large-scale circuit placement, (IEEE/ACM International Conference on Computer Aided Design, ICCAD - 2000 (2000)), 171-176, IEEE/ACM Digest of Technical Papers (Cat. No. 00CH37140)
[55] Roy, J. A.; Papa, D. A.; Adya, S. N.; Chan, H. H.; Ng, A. N.; Lu, J. F.; Markov, I. L., Capo: robust and scalable open-source min-cut floorplacer, (Proceedings of the 2005 International Symposium on Physical Design, ISPD ’05 (2005), ACM: ACM New York, NY, USA), 224-226
[56] Byrka, J.; Grandoni, F.; Rothvoss, T.; Sanità, L., Steiner tree approximation via iterative randomized rounding, J. ACM, 60, 1, 6:1-6:33 (2013) · Zbl 1281.68234
[57] Gester, M.; Müller, D.; Nieberg, T.; Panten, C.; Schulte, C.; Vygen, J., BonnRoute: algorithms and data structures for fast and good VLSI routing, ACM Trans. Des. Autom. Electron. Syst., 18, 2, 32:1-32:24 (2013)
[58] Xu, Y.; Zhang, Y.; Chu, C., Fastroute 4.0: global router with efficient via minimization, (Proceedings of the 2009 Asia and South Pacific Design Automation Conference, ASP-DAC ’09 (2009), IEEE Press: IEEE Press Piscataway, NJ, USA), 576-581
[59] Roy, J. A.; Markov, I. L., High-performance routing at the nanometer scale, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 27, 6, 1066-1077 (2008)
[60] Chen, H.; Hsu, C.; Chang, Y., High-performance global routing with fast overflow reduction, (2009 Asia and South Pacific Design Automation Conference (2009)), 582-587
[61] Cho, M.; Lu, K.; Yuan, K.; Pan, D. Z., Boxrouter 2.0: architecture and implementation of a hybrid and robust global router, (2007 IEEE/ACM International Conference on Computer-Aided Design (2007)), 503-508
[62] Chang, Y. J.; Lee, Y. T.; Wang, T. C., NTHU-route 2.0: a fast and stable global router, (2008 IEEE/ACM International Conference on Computer-Aided Design (2008)), 338-343
[63] Byrka, J.; Grandoni, F.; Rothvoß, T.; Sanità, L., An improved LP-based approximation for Steiner tree, (Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010. Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA (5-8 June 2010)), 583-592 · Zbl 1293.05039
[64] Klein, P.; Ravi, R., A nearly best-possible approximation algorithm for node-weighted Steiner trees, J. Algorithms, 19, 1, 104-115 (1995) · Zbl 0836.68046
[65] Vazirani, V. V., Approximation Algorithms (2001), Springer-Verlag: Springer-Verlag Berlin, Germany · Zbl 1138.90417
[66] Gester, M.; Müller, D.; Nieberg, T.; Panten, C.; Schulte, C.; Vygen, J., BonnRoute: algorithms and data structures for fast and good VLSI routing, ACM Trans. Des. Autom. Electron. Syst., 18, 2, 32 (2013)
[67] Müller, D.; Radke, K.; Vygen, J., Faster min-max resource sharing in theory and practice, Math. Program. Comput., 3, 1, 1-35 (2011) · Zbl 1242.90200
[68] Lucas, A., Ising formulations of many NP problems, Front. Phys., 2, 5 (2014)
[69] Chancellor, N.; Zohren, S.; Warburton, P. A.; Benjamin, S. C.; Roberts, S., A direct mapping of max k-sat and high order parity checks to a Chimera graph, Sci. Rep., 6, Article 37107 pp. (2016)
[70] Pakin, S., A quantum macro assembler, (2016 IEEE High Performance Extreme Computing Conference, HPEC 2016. 2016 IEEE High Performance Extreme Computing Conference, HPEC 2016, Waltham, MA, USA, September 13-15, 2016 (2016)), 1-8
[71] Pakin, S., Performing fully parallel constraint logic programming on a quantum annealer, Theory Pract. Log. Program., 18, 5-6, 928-949 (2018) · Zbl 1452.68039
[72] Venturelli, D.; Marchand, D. J.J.; Rojo, G., Quantum annealing implementation of job-shop scheduling
[73] Rosenberg, G.; Haghnegahdar, P.; Goddard, P.; Carr, P.; Wu, K.; de Prado, M. L., Solving the optimal trading trajectory problem using a quantum annealer, (Proceedings of the 8th Workshop on High Performance Computational Finance, WHPCF ’15 (2015), ACM: ACM New York, NY, USA), 7:1-7:7
[74] Dridi, R.; Alghassi, H., Prime factorization using quantum annealing and computational algebraic geometry, Sci. Rep., 7, 1 (2017)
[75] Perdomo-Ortiz, A.; Fluegemann, J.; Narasimhan, S.; Biswas, R.; Smelyanskiy, V., A quantum annealing approach for fault detection and diagnosis of graph-based systems, Eur. Phys. J. Spec. Top., 224, 1, 131-148 (2015)
[76] Rieffel, E. G.; Venturelli, D.; O’Gorman, B.; Do, M. B.; Prystay, E. M.; Smelyanskiy, V. N., A case study in programming a quantum annealer for hard operational planning problems, Quantum Inf. Process., 14, 1, 1-36 (2015) · Zbl 1311.81084
[77] O’Gorman, B.; Rieffel, E. G.; Do, M.; Venturelli, D.; Frank, J., Comparing planning problem compilation approaches for quantum annealing, Knowl. Eng. Rev., 31, 5, 465-474 (2016)
[78] Zick, K. M.; Shehab, O.; French, M., Experimental quantum annealing: case study involving the graph isomorphism problem, Sci. Rep., 5, Article 11168 pp. (2015)
[79] Bian, Z.; Chudak, F.; Macready, W. G.; Clark, L.; Gaitan, F., Experimental determination of Ramsey numbers, Phys. Rev. Lett., 111, Article 130505 pp. (2013)
[80] Jiang, S.; Britt, K. A.; McCaskey, A. J.; Humble, T. S.; Kais, S., Quantum annealing for prime factorization
[81] Trummer, I.; Koch, C., Multiple query optimization on the d-wave 2x adiabatic quantum computer, Proc. VLDB Endow., 9, 9, 648-659 (2016)
[82] Andriyash, E.; Bian, Z.; Chudak, F.; Drew-Brook, M.; King, A. D.; Macready, W. G.; Roy, A., Boosting integer factoring performance via quantum annealing offsets
[83] McGeoch, C. C.; Wang, C., Experimental evaluation of an adiabatic quantum system for combinatorial optimization, (Proceedings of the ACM International Conference on Computing Frontiers, CF ’13 (2013), ACM: ACM New York, NY, USA), 23:1-23:11
[84] Santra, S.; Quiroz, G.; Steeg, G. V.; Lidar, D. A., Max 2-sat with up to 108 qubits, New J. Phys., 16, 4, Article 045006 pp. (2014)
[85] Douglass, A.; King, A. D.; Raymond, J., Constructing SAT Filters with a Quantum Annealer, 104-120 (2015), Springer International Publishing: Springer International Publishing Cham · Zbl 06512568
[86] Pudenz, K. L.; Tallant, G. S.; Belote, T. R.; Adachi, S. H., Quantum annealing and the satisfiability problem
[87] Farhi, E.; Gosset, D.; Hen, I.; Sandvik, A. W.; Shor, P.; Young, A. P.; Zamponi, F., Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs, Phys. Rev. A, 86, Article 052334 pp. (2012)
[88] Hen, I.; Young, A. P., Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems, Phys. Rev. E, 84, Article 061152 pp. (2011)
[89] Choi, V., Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3SAT problems, Quantum Inf. Comput., 11, 7-8, 638-648 (2011) · Zbl 1241.81040
[90] King, A. D.; Lanting, T.; Harris, R., Performance of a quantum annealer on range-limited constraint satisfaction problems
[91] Brayton, R.; Mishchenko, A., ABC: an academic industrial-strength verification tool, (International Conference on Computer Aided Verification (2010), Springer), 24-40
[92] Spence, I., Sgen1: a generator of small but difficult satisfiability benchmarks, ACM J. Exp. Algorithmics, 15, Article 1.2 pp. (2010) · Zbl 1284.68527
[93] Gelder, A. V.; Spence, I., Zero-one designs produce small hard SAT instances, (Strichman, O.; Szeider, S., Theory and Applications of Satisfiability Testing - SAT 2010. Theory and Applications of Satisfiability Testing - SAT 2010, Lecture Notes in Computer Science (2010), Springer Berlin Heidelberg), 388-397 · Zbl 1306.68177
[94] Spence, I., Weakening cardinality constraints creates harder satisfiability benchmarks, ACM J. Exp. Algorithmics, 20, Article 1.4 pp. (2015)
[95] Li, C. M.; Huang, W. Q., Diversification and determinism in local search for satisfiability, (Bacchus, F.; Walsh, T., Theory and Applications of Satisfiability Testing: 8th International Conference, SAT 2005, St Andrews, UK, June 19-23, 2005, Proceedings (2005), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 158-172 · Zbl 1128.68472
[96] Smyth, K.; Hoos, H. H.; Stützle, T., Iterated robust tabu search for max-sat, (Proceedings of the 16th Canadian Society for Computational Studies of Intelligence Conference on Advances in Artificial Intelligence, AI’03 (2003), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 129-144
[97] McAllester, D.; Selman, B.; Kautz, H., Evidence for invariants in local search, (Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Conference on Innovative Applications of Artificial Intelligence, AAAI’97/IAAI’97 (1997), AAAI Press), 321-326
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.